10
$\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$
12
  • $\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 '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$ Jun 20 '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 '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$ Jun 20 '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$ Jun 20 '20 at 13:01
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$ Jun 21 '20 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$ May 22 '21 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
    May 26 '21 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$ May 26 '21 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$ May 25 '21 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$ May 25 '21 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$ May 25 '21 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$ May 26 '21 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$ May 26 '21 at 0:51

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.