Why doesn´t the von Neumann hierarchy to $V_{\omega_1}$ exist in Zermelo set theory if with Scott´s trick you can "count" to $ \omega_1 $


To see what goes wrong, let's try to prove something even simpler: that $\omega_1$ exists.

We definitely have the set of all well-orderings of $\omega$ (via Powerset and Separation). Now, via Separation and Choice, we can pick a family $\{R_i: i\in I\}$ of well-orderings of $\omega$ such that each well-ordering of $\omega$ is order-isomorphic with exactly one $R_i$. The usual proof that well-orderings are well-ordered by initial segment embedding goes through, so we can build a well-ordering $W$ of order-type $\omega_1$ by "adding all the $R_i$s together." Of course, this is not an ordinal, it's just a binary relation on a set (specifically, on $\omega\times I$) which is a well-ordering and which has "length $\omega_1$" intuitively.

OK, so we can build a thing of length $\omega_1$; why can't we build $\omega_1$ itself?

Well, what we would want to do is show: "For every well-ordering, there is an ordinal of the same length." (Appropriately formalized.) However, this fact uses Replacement!

Specifically, the usual proof goes roughly as: "Suppose there was a well-ordering $R$ of a set $X$, which is not in order-preserving bijection with any ordinal. We can assume that for each $x\in X$, the set $X_x=\{y\in X: y<_R x\}$ is in order-preserving bijection with some ordinal. (Otherwise, if there is some $x\in X$ such that $\{y\in X: y<_R x\}$ is not in order-preserving bijection with any ordinal, then since $R$ is a well-ordering there is a least such $x$; so just replace $X$ and $R$ with $X_x$ and $R\upharpoonright X_x\times X_x$.) So we have a map from elements of $X$ to ordinals. By Replacement, the image of that map exists and is a downwards-closed set of ordinals, and hence an ordinal; and it's easy to show that this ordinal is in order-preserving bijection with $R$."

In $ZC$, however, there is no reason for the class of ordinals corresponding to elements of $X$ to be a set! So the proof breaks down here. In fact, it’s worse: in $ZC$ we can’t even prove that $\omega+\omega$ exists! (And the only way $ZC$ knows $\omega$ exists is by having it "built in" via the Axiom of Infinity.)

Technically, this doesn’t answer your question: all I’ve explained is why the usual proof that $\omega_1$ exists breaks down. I haven’t shown that no proof exists. In order to prove that, really, $ZC$ can’t prove $\omega+\omega$ exists, it suffices to show that $V_{\omega+\omega}$ is a model of $ZC$. (This is a fun exercise!)

EDIT: You may be interested in the paper "Slim models of Zermelo set theory" by Mathias (https://www.dpmms.cam.ac.uk/~ardm/slim.dvi) - it focuses specifically on recursive definitions in Z(C), and where they break. Note that the first sentence of the abstract confirms my statement that Z alone cannot prove that $V_\omega$ exists.

  • 3
    $\begingroup$ A good exercise for getting a handle on what sorts of things $ZC$ can and can't do: working in $ZFC$, describe the least ordinal $\alpha$ such that there is no $(X, R)\in V_{\omega+\omega}$ where $R$ is a well-ordering of $X$ with order type $\alpha$. For example, even though $V_{\omega+\omega}$ doesn't contain $\omega+\omega$, it does contain all the binary relations on $\omega$ - in particular, all the countable ordinals are so represented! And the early part of my answer shows that $\omega_1$ is also represented. It's not hard to get $\omega_2$, $\omega_3$, etc. So: how high can you go? $\endgroup$ – Noah Schweber Aug 19 '15 at 3:26
  • $\begingroup$ But in ZC it is not possible neither demonstrate that Vω+1, while the ordinal ω+1 exist. $\endgroup$ – Raul Aug 20 '15 at 6:28
  • $\begingroup$ If you're saying that ZC doesn't prove $V_{\omega+1}$ exists, but does prove that $\omega+1$ exists, this seems right; but what does that have to do with my answer above? $\endgroup$ – Noah Schweber Aug 20 '15 at 14:40
  • $\begingroup$ Because then it is impossible use induction even for ordinals type $ \omega+n$. Is it induction a non propierty of ZC? $\endgroup$ – Raul Aug 21 '15 at 3:06
  • 1
    $\begingroup$ It depends what you mean by "induction." ZC is more than strong enough to prove, for any formula $\varphi$: "If $R$ is a well-ordering of $X$, and for all $x\in X$, if $\varphi(y)$ holds $\forall y<_Rx$ then $\varphi(x)$ holds, then $\forall x\in X(\varphi(x))$." But maybe you mean the proof that definition by recursion works - one instance of which is the theorem "$V_\alpha$ exists for every ordinal $\alpha$." This does require replacement, and ZC is not enough to make all recursive constructions work (although some still do). Does that help? $\endgroup$ – Noah Schweber Aug 21 '15 at 3:21

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.