Is Foundation equivalent to $\forall_x \exists_\alpha x \in V_\alpha$ (every set has a rank) in ZF-Foundation?

The Wikipedia article on Foundation makes this claim with no reference:

In ZF it can be proven that the class $V$, called the von Neumann universe, is equal to the class of all sets. This statement is even equivalent to the axiom of regularity (if we work in ZF with this axiom omitted). From any model which does not satisfy axiom of regularity, a model which satisfies it can be constructed by taking only sets in $V$.

I think I see how this works in one direction: if the rank is a total class function mapping sets to ordinals, then by Specification and Replacement every non-empty set has a non-empty subset containing the elements of smallest rank, and it's disjoint from every element of this subset, implying Foundation. I believe I did not use Choice here.

In the other direction, suppose $\{x: x \notin V\}$ is a class with a subclass $S = \{a, b, c, \dots\}$ satisfying $a \ni b \ni c \ni \dots$. More formally, $(S \neq \emptyset) \land (S \cap V = \emptyset) \land \forall_x(x \in S \rightarrow x \subset S)$. If $S$ were a set its existence would contradict Foundation because it's not disjoint from any of its elements. We could define a Foundation-violating set by transfinite recursion starting with $a$, if we had a class function sending every set to one of its elements — but that's equivalent to Choice!

Another way I was trying to look at it is, pick an $x \notin V$, and form its transitive closure. That set would not be disjoint from any of its elements. But I understand the transitive closure is defined by Specification from the rank of $x$ and we're assuming $x \notin V$ so it has no rank.

I'm probably missing something simple. How to prove this equivalence without Choice?

  • 1
    $\begingroup$ Forgive me as I am not very proficient, but perhaps page 70 of this (which coincidentally I am trying to figure out) may help: math.wisc.edu/~miller/old/m771-10/kunen770.pdf $\endgroup$ – user12802 May 17 '18 at 0:38

The key fact is:

If $a\not\in V$, then there is some $b\in a$ with $b\not\in V$.

Now choice may tempt us into trying to build - from a single $a\not\in V$ - an $\in$-decreasing sequence of sets not in $V$, by the above rule. Of course, this won't work without choice.

We can get around this as follows. By Replacement, the transitive closure $tcl(a)$ exists; now consider $x=$ "$tcl(a)\setminus V$," that is the set of elements of $tcl(a)$ not in $V$ (which exists by separation - $V$ is definable!). By the highlighted point above, for any $y\in x$ there is some $z\in y$ with $z\not\in V$; but then this $z$ is an element of an element of $tcl(a)$, and since $tcl(a)$ is transitive this tells us $z\in tcl(a)$. But then $z\in x$ since $z\not\in V$, and so we have $y\cap x\ni z$. So $x$ constitutes a failure of foundation.

  • $\begingroup$ Oh okay so the part I just added at the end can be made to work. I guess I need to figure out how to get the $\text{tcl}$ from Replacement. $\endgroup$ – Dan Brumleve May 16 '18 at 21:13
  • $\begingroup$ Wait is it transfinite recursion again using Union? $\endgroup$ – Dan Brumleve May 16 '18 at 21:14

If $x\in V$, then $\operatorname{tcl}(x)$ is well-founded. To see this: we prove two things:

  1. If $x\in V_\alpha$, then $\operatorname{tcl}(x)\in V_\alpha$ as well.
  2. If $x\subseteq y$ are two transitive sets and $y$ is well-founded, then $x$ is well-founded.

The former is easy by induction on $\alpha$. The latter is easy since if $z\in x$ is such that $\{u\in x\mid u\in z\}$ has no minimal element, then $z\in y$ is also a counterexample of well-foundedness there.

  • $\begingroup$ Right the second part shows that if $x \notin V$ then $\text{tcl}(x)$ isn't either and $\text{tcl}(x) \setminus V$ gives the counterexample. The first part is how I am defining $\text{tcl}$ (Specification from $V_\alpha$). My problem is not knowing what is $\text{tcl}(x)$ when $x \notin V$ but I think Noah gave me enough of a pointer. $\endgroup$ – Dan Brumleve May 16 '18 at 21:32
  • $\begingroup$ Use Replacement, Union and Infinity. $\endgroup$ – Asaf Karagila May 16 '18 at 21:39

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.