5
$\begingroup$

ZF is sufficient to construct the von Neumann hierarchy, and prove that every set appears at some stage $V_\alpha$. This is the basis for Scott's trick, for instance. But how much of ZF is needed? Is bounded Zermelo/Mac Lane set theory enough, no Choice assumed? I know Foundation is necessary, and I'm not getting rid of that. I've seen something called the "rank axiom" in discussion of second-order version of original Zermelo (these notes), but I'm sure people have finely calibrated what precisely is needed.

To be honest, all I really want is an ordinal-valued rank function such that sets of rank at most $\alpha$ form a set, for all $\alpha$, and all sets have a rank. So if the von Neumann hierarchy doesn't work, I'm happy to work with something else (and for 'ordinals', I don't need von Neumann ordinals).

$\endgroup$
  • $\begingroup$ You need some Replacement, at least in the von Neumann case. If you are willing to work with "Fregean ordinals", there might be a way to resolve this without too much Replacement. $\endgroup$ – Asaf Karagila Jun 20 at 8:10
  • $\begingroup$ @AsafKaragila In fact it requires considerable amount of Replacement. In particular even $(\mathsf{ZFC}-\mathsf{Replacement})+\Delta_0\text{-}\mathsf{Replacement}$ couldn't prove that for every ordinal $\alpha$ there is $V_\alpha$, i.e. the set of all elements of the rank $\alpha$. This is because $H\aleph_\omega$ (the set of all sets $x$ s.t. the transitive closure of $x$ is of the cardinality $<\aleph_\omega$) is a model of this theory. $\endgroup$ – Fedor Pakhomov Jun 20 at 9:05
  • $\begingroup$ @Fedor: If you read closely, I was referring to the remark at the end of the question, foregoing the von Neumann hierarchy and the von Neumann ordinals. $\endgroup$ – Asaf Karagila Jun 20 at 9:06
  • 1
    $\begingroup$ @David I think that it is essential to have $\Pi_1$-Replacement, PowerSet, and Regularity as axioms. I don't think that the usage of some alternative presentation of ordinals would really help. Note that in the model $H\aleph_\omega$ for ranks $\alpha\ge\omega2$ the collections of all sets of the rank $\alpha$ form proper classes. And even if you would represent ordinals differently $V_\alpha$'s still would be proper classes in this model. $\endgroup$ – Fedor Pakhomov Jun 20 at 11:16
  • 1
    $\begingroup$ @AsafKaragila Personally I consider any collection/replacement principle stronger than $\Sigma_1$-Collection to be strong. We could develop most of basic set-theoretic constructions in $\mathsf{KP}$ and it could only prove $\Sigma_1$-Collection. $\endgroup$ – Fedor Pakhomov Jun 20 at 13:01
8
$\begingroup$

KP (Kripke-Platek set theory) is the most well-known fragment of $\sf{ZF}$ which suffices for the development of the rank function, thus $\sf{KPR}$ = $\sf{KP}$ + "for all ordinals $\alpha$, $V(\alpha)$ exists" is the usual minimal theory in which one can be assured of the stratification of the universe into $V(\alpha)$s.

On the other hand, as observed by Mathias, $\sf{KPR}$ proves that Zermelo set theory $\sf{Z}$ has a transitive model, so in particular, $\sf{KPR}$ proves that $\sf{Z}$ is consistent; see Lemma 6.31 of this preprint, which was later published in APAL (2001).

Therefore, by the second incompleteness theorem, even Zermelo set theory (let alone bounded Zermelo set theory) cannot interpret $\sf{KPR}$.

Finally, I will add that $\sf{KPR}$ is provable in the well-known extension $\sf{KP}^{\cal{P}}$ of $\sf{KP}$, which is also studied in Mathias' paper.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ OK, cool. So it's probably $\sf{KP}^{\cal{P}}$ or Rathjen's $\sf{KP}(\cal{P})$ that I'm after, since I don't really want to give up power set right now. Or maybe $\sf{BZ}+\sf{KP}$... $\endgroup$ – David Roberts Jun 21 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.