Transfinite recursion, collection and replacement in KP and KF

Question

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$?

Answer 1

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.

Answer 2

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.