Does the existence of the von Neumann hierarchy in models of Zermelo set theory with foundation imply that every set has ordinal rank?

Let $T$ be the theory consisting of Zermelo's original set theoretic axioms (extensionality, empty set, pairing, union, powerset, infinity, separation, choice) together with foundation. Put more succinctly, $T$ consists of ${\rm ZFC}$ axioms without the replacement axiom scheme. The theory $T$ is too weak for most set theoretic purposes because, for instance, it cannot even prove the existence of transitive closures. We consider strengthening $T$ in the following two ways. Let $A$ be the axiom asserting that $V_\alpha$ exists for every $\alpha$ and let $A^*$ be the axiom asserting that every $x$ is an element of a $V_\alpha$. For example, $V_{\omega+\omega}$ is a model of $T+A^*$. Does $T$ together with $A$ imply $A^*$? Or is it possible that $V_\alpha$ exists for every ordinal $\alpha$, but there is a set without an ordinal rank?

-
At first sight, the statement of $A$ appears depend on the existence of von Neumann ordinals, but I imagine you mean it to be taken as a assertion about recursions along arbitrarily long well-ordered sets? –  Adam Epstein Sep 1 '13 at 14:50
Adam, I actually do mean for the statements $A$ and $A^*$ to depend on the existence of the von Neumann ordinals. –  Victoria Gitman Sep 1 '13 at 15:18
I see that now, since you allow $V_{\omega+\omega}$ as a model. So you require that any von Neumann ordinal be the spine of a stage of the cumulative hierarchy, but you allow the existence of well-ordered sets longer than any von Neumann ordinal. I believe the answer is no. I will think a bit more and then try to justify this in an answer. –  Adam Epstein Sep 1 '13 at 15:28
Yes, I also suspect that $A^*$ is stronger than $A$, but I have no idea how to construct a model of $T+A$ that does not satisfy $A^*$. –  Victoria Gitman Sep 1 '13 at 15:30
The model I would propose is something I came up with in connection with my own question mathoverflow.net/questions/117910/… for which I also believe the answer is no. In a nutshell, take a model of finite set theory in which there is an infinite descending chain $x_{n+1}\in x_n$. This is possible, even assuming Foundation. Then formally adjoin $\omega$ levels of the cumulative hierarchy. –  Adam Epstein Sep 1 '13 at 15:41

Take the Zermelo ordinals to be defined by $Z(0) = 0$, $Z(\alpha+1) = \{Z(\alpha)\}$, and $Z(\lambda) = \{Z(\alpha): \alpha<\lambda\}$ (where $\alpha, \lambda$ are von Neumann ordinals). Then if we add $Z(\omega+ \omega)$ to $V_{\omega +\omega}$ and close under pairing, union, subsets, and powersets, we get a model of $T$ - Choice + $A$ which is not a model of $A^*$.

More precisely, let $D_0 = V_{\omega+\omega} \cup\{Z(\omega+\omega)\}$ and $D_{n+1}$ be the result of adding pairs, unions, subsets, and powersets of element of $D_n$ to $D_n$. Clearly, $M = \bigcup_{n <\omega}D_n$ is transitive and models $T$ - Choice. A simple induction shows that:

For every $x\in D_n$ there is an $\alpha<\omega+\omega$ such that the (von Neumann) ordinals in $tc(x)$ are less than $\alpha$.

Since $V_{\omega+\omega}\subseteq M$, it follows that the von Neumann ordinals in $M$ are just those in $\omega+\omega$. So it models $A$. Since the rank of $Z(\omega+\omega)$ is $\omega+\omega$, it doesn't model $A^*$.

(To get Choice in the form every set is well-orderable" we just throw in $x \times x$ at $D_{n+1}$ for $x\in D_n$).

-
Very nice - and transitive too. –  Adam Epstein Sep 1 '13 at 22:36
Thanks for the great answer. It is very elegant! –  Victoria Gitman Sep 2 '13 at 17:08
Thanks, Victoria and Adam! –  Sam Roberts Sep 2 '13 at 18:35

If i understand you correctly, your A* is equivalent to the assertion that every set x belongs to a transitive set X s.t. every subset of a member of X is a member of X. (That way you don't have to talk about Von neumann ordinals - or any ordinals at all). I'd bet very good money that this is not a theorem of Zermelo, and [slightly less money] that you will find this fact proved in a recent JSL article by A.R.D.Mathias under the title thin models of set theory''.

-
Weclome back to MathOverflow! Would you consider registering your account so we can properly recombine your multiple personas. Contact <moderators@mathoverflow.net> for assistance. –  François G. Dorais Sep 1 '13 at 19:46
Dear Thomas, You are most welcome. I am one of the fans of non well founded set theory, specially your beauty book "Set theory with a universal set". –  user36136 Sep 3 '13 at 8:44

As a partial answer: It follows at least from recursion and replacement over $\omega$:

Assume $\lnot A^\star$, then there exists a set $x$ such that $\not\exists_{\alpha\in\operatorname{On}} x\in V_\alpha$. Especially, therefore, we can find a set $y\in x$ such that also $\not\exists_{\alpha\in\operatorname{On}} y\in V_\alpha$, especially, $y\neq\emptyset$. Recursively, we can therefore define a sequence $x=x_0\ni y=x_1\ni x_2\ni x_2\ni \ldots$, and this contradicts the foundation axiom.

On the other hand, from $A^\star$ should follow that every set is well-founded, and therefore at least $\omega$-Induction, which should imply $\omega$-Induction and $\omega$-Replacement.

-

Assertion $A^*$ is strictly stronger than assertion $A$.

Denote by $Z$ the theory with axioms Extensionality, Empty Set, Pairing, Union, Power Set, Infinity, Separation Schema, Foundation. Adding Choice is yields a theory which is essentially your $T$ but for an important fine point, namely, the precise formulation of the Axiom of Infinity. My own preference is for the Axiom of Infinity to be the assertion of the existence of a Kuratowski infinite set. This assertion is provably weaker than both Zermelo's original formulation and the customary formulation in terms of inductive sets (see Slim Models of Zermelo Set Theory by Mathias).

Let $F$ be the theory obtained from $Z$ by replacing my preferred Axiom of Infinity by its negation. In this theory, Replacement is a theorem schema and Choice is a theorem: thus, $F$ is a reformulation of the finite theory of Enayat-Schmerl-Visser's article $\omega$-models of finite set theory.

Let ${\bf M}=(X,\lhd)$ be an $\omega$-model of $F+ \exists \phi(x)$ where $\phi(x)$ is the assertion "every element of the transitive closure of {$x$} is a singleton". Note that membership in this transitive closure is expressible by a first-order formula. There is no requirement that this transitive closure exist as a set: indeed it cannot, since $\bf M\models$ Foundation. There are various ways to obtain such a model. One method is to apply the Rieger-Bernays permutation procedure to the standard model $(V_\omega\in)$ and a cleverly chosen permutation $\sigma:V_\omega\rightarrow V_\omega$ to obtain ${\bf M}=(V_\omega,\in_\sigma)$ where $x \in_\sigma y\Leftrightarrow x\in \sigma(y)$: see Section 3 of A note on recursive models of set theory by Mancini-Zambella. Another is to construct $\bf M$ directly by starting with a linear order $\ldots < x_{n+1}< x_n\ldots< x_0$ and iterating $\omega$ many times the procedure of formally adjoining power sets of finite subsets (taking care to e.g. identify {$x_{n+1}$} with $x_n$). For details, see the paper of Enayat-Schmerl-Visser.

In work in progress addressed at my own Math Overflow question Can one exhibit an explicit Kuratowski infinite set without invoking Replacement? I've been adapting this idea of formally adjoining power sets to the setting where one is given an $\omega$-model of $F$ and an appropriate collection of (external) infinite subsets of its underlying set, and where one wishes to produce a suitably minimal $\omega$-model of $Z$ whose "hereditarily finite" sets are those of the original model, and which has members with the specified infinite extensions. Given ${\bf M}=(X,\lhd)$ as in the previous paragraph, for every $x$ such that $\phi(x)$ we formally adjoin an element with extension {$x$,{$x$},{{$x$}},$\ldots$}, then formally adjoin any missing elements with finite extension in this augmented domain (taking due care as alluded to previously) and iterate $\omega$-many times. The resulting structure $\widehat{\bf M}$ will be a model of $Z$ (including the Axiom of Infinity) with the property that the class $V_\omega$ has no infinite subset.

For reasons of symmetry, $\widehat{\bf M}$ has no definable infinite sets. While this responds to the question I originally posed, the fact that Transitive Containment is violated feels a bit like cheating. I have another construction for that, but I am digressing far too much already.

My proposal would be to modify the recipe by also formally adjoining an element with extension $V_\omega$ at the first stage, then proceeding as indicated above, i.e. lather, rinse and repeat $\omega$ many times.

-