Define the function $$V_0=\emptyset,\qquad V_{\alpha+1}={\cal P}(V_\alpha),\qquad V_{\delta}=\bigcup_{\beta<\delta}V_\beta.$$

Since we are working in $\sf Z$ (i.e. $\sf ZF$ without the axiom of replacement - note that regularity is an axiom of $\sf Z$ for me), there are some difficulties in doing transfinite recursion, and in particular this does not necessarily define a function on $\sf On$. Instead, what happens is that the recursion continues as long as the initial segments of the function exist, and it stops at some limit ordinal $\kappa$ (which may or may not be a set) such that the function $\alpha\in\kappa\mapsto V_\alpha$ is a proper class with domain $\kappa$ but $\alpha\in\beta\mapsto V_\alpha$ is a set function for any $\beta<\kappa$. (Notation note: $V_\delta$ for a limit ordinal $\delta\ge\kappa$ means the proper class union of all smaller $V_\beta$ even though this is not in the range of the function, and in particular $V_{\sf On}$ means the union of all $V_\alpha$.)

The task is to show that this hierarchy of sets covers $V$ (the universe). Since the usual model for $\sf Z$, $V_{\omega2}$, does in fact satisfy this property, it is at least plausible. There are two problem points in the usual $\sf ZF$ derivation. The first part is to show that if $A\subseteq V_{\sf On}$ and $A$ is a set, then $A\in V_{\sf On}$. The second part is to use regularity to show that this covers all sets.

A sketch of the first part: Given such an $A$, define $\alpha=\bigcup_{x\in A}\DeclareMathOperator{\rank}{rank}\rank x$, where $\rank x$ is the function on $V_{\sf On}$ which gives the smallest $\beta$ such that $x\subseteq V_\beta$. Then by replacement, $\alpha$ is a set, and each $x\subseteq V_{\rank x}\subseteq V_\alpha$ so $x\in V_{\alpha+1}$, so $A\in V_{\alpha+2}$. I feel like the fact that $A$ is a set was not sufficiently applied in this instance in order to make sure that $\alpha$ is not too large. Working in $\sf ZF$, are there any set models of $\sf Z$ other than $V_{\alpha}$ for some limit ordinal $\alpha>\omega$?

For the second part, I have rather less hope. Given a class $A$ which satisfies $x\subseteq A\to x\in A$, the goal is to show that $A=V$. Here's the $\sf ZF$ proof sketch: if there is a $z\in V\setminus A$, then construct the class $\operatorname{TC}(z)$, the smallest transitive set containing $z$. Assuming that this defines a set, we have $z\in\operatorname{TC}(z)\setminus A$ so we can apply regularity to it to get an $x\in\operatorname{TC}(z)\setminus A$ with $x\cap\operatorname{TC}(z)\setminus A=\emptyset$. But by transitivity $x\subseteq\operatorname{TC}(z)$, so $x\cap\operatorname{TC}(z)=x$ and thus $x\setminus A=\emptyset$ or $x\subseteq A$. But $x\notin A$, in contradiction to the original hypothesis, so therefore $V\setminus A=\emptyset$ and $A=V$.

The place where replacement sneaks in is in the proof of the existence of transitive closures, which uses the set $\operatorname{TC}(z)=\bigcup_{n\in\omega}f(n)$ where $f(0)=\{z\}$ and $f(n+1)=f(n)\cup\bigcup f(n)$. I'm pretty sure that replacement is essential here, but I'd like some definitive answers regarding which parts of this proof require replacement and which parts can avoid it by an alternative method. I'm not very good at model-building, which is usually the easiest way to answer this sort of thing, so perhaps someone here knows the answers to these questions.

  • $\begingroup$ In many places $\sf Z$ doesn't include foundation making this utterly false. What is $\sf Z$ for you? $\endgroup$ – Asaf Karagila Nov 17 '14 at 4:55
  • $\begingroup$ @Asaf Well, obviously I have foundation or else this is pointless, as you say (although the first part of the proof is still valid and interesting). For me, ${\sf Z}={\sf ZF}-{\sf F}$, where ${\sf F}$ is the Fraenkel axiom, i.e. replacement. In particular, regularity and infinity are axioms of $\sf Z$. (Edit: After a little Wikipedia research, I see that the standard definition of $\sf Z$ indeed does not contain regularity. Oh well, just pretend I'm using $\sf Z+Reg$ then.) $\endgroup$ – Mario Carneiro Nov 17 '14 at 5:40
  • $\begingroup$ "The Fraenkel Axiom"??? (I still feel that I'm missing a few question marks to make my point.) $\endgroup$ – Asaf Karagila Nov 17 '14 at 5:49
  • 1
    $\begingroup$ @Asaf Blame my haphazard education, but I had been under the impression that the only difference between $\sf Z$ and $\sf ZF$ was the addition of the axiom of replacement, due to Fraenkel. Whether this is in fact true (as it turns out it isn't) isn't really relevant to the question though; as I said just pretend I wrote $\sf ZF-Rep$ or $\sf Z+Reg$ instead of $\sf Z$. However, it appears that regularity is more Zermelo's work (or von Neumann's) than Fraenkel, so I don't know how historically correct it is to keep $\sf Reg$ out of $\sf Z$ under the usual definition. $\endgroup$ – Mario Carneiro Nov 17 '14 at 6:16
  • 1
    $\begingroup$ @Asaf Maybe I'm fooling myself, but I'm pretty sure I've heard it called something like "Fraenkel's axiom" since it is Fraenkel's contribution to $\sf ZF$. $\endgroup$ – Mario Carneiro Nov 17 '14 at 14:15

One cannot prove this from $Z$ + Foundation. Indeed, one cannot prove that $V = \bigcup V_\alpha$ even in $Z$ + Foundation + $\forall \alpha (V_\alpha$ exists). For details, see this mathoverflow answer.

  • $\begingroup$ I was about to post that link with a summary of the answer. :-) $\endgroup$ – Asaf Karagila Nov 17 '14 at 8:55
  • $\begingroup$ Rarely do I beat you to it! $\endgroup$ – GME Nov 17 '14 at 8:57
  • 1
    $\begingroup$ I blame this for doing most of this morning surfing from my phone. I had to get up to post the answer. :-P $\endgroup$ – Asaf Karagila Nov 17 '14 at 8:58
  • $\begingroup$ Do you know if the first part is provable, that is ${\cal P}(\bigcup V_\alpha)\subseteq\bigcup V_\alpha$? $\endgroup$ – Mario Carneiro Nov 17 '14 at 14:45
  • 1
    $\begingroup$ @Asaf ${\cal P}(\bigcup V_\alpha)$ is the proper class of all subclasses of $\bigcup V_\alpha$ that are also sets. ${\cal P}(\bigcup V_\alpha)\subseteq\bigcup V_\alpha$ is just a compact way of saying that if $x$ is a set and $x\subseteq\bigcup V_\alpha$, then $x\in\bigcup V_\alpha$, which is the same as what you wrote. As for what GME termed "set models", I think the correct term is "standard model", yes? $\endgroup$ – Mario Carneiro Nov 18 '14 at 8:32

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.