11
$\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$
23
  • 1
    $\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
    Commented Jun 20, 2020 at 8:10
  • 1
    $\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
    Commented Jun 20, 2020 at 9:06
  • 1
    $\begingroup$ David, you can't get rid of the von Neumann part too easily: let $\alpha$ be the supremum of the von Neumann ordinals of the model, you might want to "pace yourself" with adding those to the levels of your hierarchy. But that means that the cofinality of your hierarchy must be the same as the cofinality of $\alpha$. Taking Mathias' $M_\lambda$ example of a model of Zermelo shows that this is impossible (as the rank function must be unbounded in all possible order types, i.e. the real Ord, but $\alpha=\lambda$ is a set). $\endgroup$
    – Asaf Karagila
    Commented Jun 20, 2020 at 9:16
  • 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$ Commented Jun 20, 2020 at 11:16
  • 1
    $\begingroup$ David, it's not about the image. It's about the possible ranks of your von Neumann ordinals. They cannot be exhausted before the you're done with the whole universe. $\endgroup$
    – Asaf Karagila
    Commented Jun 20, 2020 at 12:32

2 Answers 2

12
$\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.

$\endgroup$
4
  • $\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
    Commented Jun 21, 2020 at 2:10
  • $\begingroup$ But the theory $\sf Z + $$\forall \alpha : V_\alpha$ exists, (where $\alpha$ is a von Neumann) will stratifiy the universe into stages, and this is weaker than $\sf KPR$? $\endgroup$ Commented May 22, 2021 at 10:49
  • $\begingroup$ @ZuhairAl-Johar The two theories you mentioned are incomparable, the first has full separation but no collection, the second has some collection but not much separation. $\endgroup$
    – Ali Enayat
    Commented May 26, 2021 at 17:19
  • $\begingroup$ @AliEnayat, Ah! Yes. But the point is why we need collection for? I mean take $\sf KP - collection + \forall x \exists \alpha: x \in V_\alpha$ , why that won't ensure stratifying the universe into $V(\alpha)'s$ ? $\endgroup$ Commented May 26, 2021 at 18:17
8
$\begingroup$

One can directly assume in Zermelo that every set belongs to a rank. This does not add any strength at all. But notice that Zermelo may not prove the existence of very many von Neumann ordinals: there may be well-orderings which do not have a von Neumann ordinal as order type. A natural model of this theory is the union of the V^{omega + n}'s for n a natural number. Notice that in this structure the axioms of Zermelo hold, every object belongs to a V_alpha, but omega+omega does not exist. There are well-orderings with order types far higher than omega+omega (and in this context the Scott representation of the ordinals is available).

There are a couple of additional remarks. It is interesting to note that the assertion that every set has a rank adds no strength at all to Zermelo set theory (or to Zermelo set theory with bounded separation) but that adding this assertion to KP, a theory much weaker than Zermelo, gives a theory much stronger than Zermelo. The reason is that KP has a lot of replacement.

The natural way to describe the rank function in "Zermelo with ranks" is probably to use the Scott ordinals as values of the rank function but note that the rank function is not necessarily onto the ordinals. In the absence of replacement, the von Neumann notion of ordinal simply isn't the right notion of ordinal number.

$\endgroup$
6
  • 1
    $\begingroup$ Could you clarify what “adds no strength at all” means? $\endgroup$ Commented May 25, 2021 at 15:32
  • $\begingroup$ OK, this is nice. I'm not wedded to von Neumann ordinals, since ultimately what I want is something like Scott's trick, and I'm happy to get this from some class function from $V$ to a any old well-ordered class, where the preimage of every member is a set. But you are relying on Scott ordinals, and I haven't seen that before (at least, not outside ZF). $\endgroup$
    – David Roberts
    Commented May 25, 2021 at 17:36
  • 2
    $\begingroup$ What do you mean by the Scott representation of the ordinals? Is it something related to Scott's trick, e.g. represent a well-order-type by the set of all well-orderings of least rank having that order type? $\endgroup$ Commented May 25, 2021 at 18:23
  • $\begingroup$ @MikeShulman I assume so, but I don't know how to get this without having some kind of hierarchy as in question, which was the whole point! My only lead is section 3.6.1 in randall-holmes.github.io/proofsetslogic.pdf, where there are three extra axioms listed: Axiom of Ordinals, Axiom of Levels and Axiom of Rank. I presume that Randall in his answer is implying that one only needs the last of these, but in the notes the notion of rank uses subhierarchies, and it's not clearly signposted that these don't use the Ordinals and Levels axioms. $\endgroup$
    – David Roberts
    Commented May 26, 2021 at 0:17
  • 1
    $\begingroup$ I've seen a citation to Matthias' "The strength of Mac Lane set theory" for the claim that adding an axiom of rank "adds no essential strength to Zermelo or Mac Lane set theory", but all I see are results about KP. $\endgroup$
    – David Roberts
    Commented May 26, 2021 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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