# Transfinite recursion, collection and replacement in KP and KF

Kripke Platek set theory has collection instead of replacement, and it is a weakening of KP if one has replacement instead of collection. Call KP minus collection plus replacement KF for Kripke Fraenkel. Is KF weaker than KP in that some transfinite recursion can be done by KP which cannot be done by KF? If so, is that a difference inherited by strengthened theories as $\Sigma _{n} KP$ and $\Sigma _{n} KF$ for $n>1$?

-
I don't think substituting Fraenkel for Platek like that is appropriate since Platek's contribution to KP was not just the collection axiom. –  François G. Dorais Aug 3 '13 at 15:23
"KF" has also been used occasionally elsewhere to abbreviate "Kaye-Forster". –  Philip Welch Aug 3 '13 at 15:31

The main deficit of KF over KP is that one cannot prove that the set of formulae equivalent to a $\Sigma_1$ or $\Pi_1$ formula is closed under bounded quantification. (And this persists up through the $KF_n/KP_n$ you define.)

Therefore recursions involving schemes defined by a formula of the form $\forall u \in v \varphi$ cannot in general be effected in KF.

At the level n=1: Mathias in: Weak Systems of Gandy, Jensen and Devlin'', (Trends in Mathematics, Ed. Bagaria, Todorcevic, Birkhäuser Press) states that methods of Zarach should be sufficient to give an example showing that $\Delta_0$-collection cannot be substituted by $\Delta_0$-replacement, but does not give an example (and I don't have one).

At levels > 1: See Gitman, Johnstone, Hamkins What is the theory ZFC without Power Set". (Archive for Math.Logic, 2012) where they give examples (some derived from Zarach) of failures of even low levels of $\Sigma_n$-Collection even in models of full $\Sigma_\omega$-Replacement. They observe that one can inductively define in one such model a family of bijective functions $f:\omega \longrightarrow \aleph_k$ for $k\leq n$, but not altogether for all $n<\omega$. Thus strengthening the replacement scheme does not help.

-
By $\aleph_k$ here, one should understand the $\aleph_k$'s of a ground model, which have all been collapsed to $\omega$ by forcing. The old $\aleph_\omega$ becomes the new $\omega_1$, which is singular in our model, even though it satisfies ZFC- and, in particular, the axiom of choice. –  Joel David Hamkins Aug 3 '13 at 16:59
I am concerned with a construction which is strongly related to your infinite time Turing machines. Are they affected? –  Frode Bjørdal Aug 3 '13 at 19:41
The recursion defining the operation of ITTMs does not seem to be affected by the replacement/collection issue, since one may undertake it inside the constructible universe $L$. –  Joel David Hamkins Aug 4 '13 at 0:19
I agree with Joel's comment concerning ITTM's in L. In L the Collection vis a vis Replacement concern is not an issue as there is a global wellorder of L. @Joel: thanks for clarifying the status of the $\aleph_n$'s in my answer. –  Philip Welch Aug 4 '13 at 6:21

In our paper, V. Gitman, J. D. Hamkins, T.A. Johnstone, What is the theory ZFC without powerset?, which arose also in one of your previous questions, we prove that there is a model of ZFC-powerset using only replacement and not collection (and so it satisfies your theory KF and indeed $\Sigma_n$-KF for every $n$), which has sets of reals of size $\aleph_n$ for every finite $n$, yet no set of reals of size $\aleph_\omega$, even though this model has $\aleph_\omega$ and indeed satisfies Hartog's theorem "$\forall\alpha\aleph_\alpha$ exists". Thus, in this model, which has the axiom of choice, there is no largest well-ordered set of real numbers.

One can view this as a failure of transfinite recursion. Specifically, KP proves that if if every set of reals is well-orderable, and for every $n$ there is a set of reals of size $\aleph_n$, then there is a set of reals of size $\aleph_\omega$. One simply collects the smaller sets, takes the union, and well-orders it. But KF and indeed $\bigcup_n\Sigma_n$-KF does not prove this, because of our model.

But perhaps you had a more specific kind or instance of recursion in mind? If so, please describe in more detail what forms of recursion you are considering.

-
See my comment to Phillip Welch below. –  Frode Bjørdal Aug 3 '13 at 19:17