-2
$\begingroup$

I find that most proofs in cumulative hierarchy that any set belongs to some $V_\alpha$ of ordinals are inconclusive. One online source assumes it be axiom. Is it really axiom? In addition, cumulative hierarchy actually assumes that there is a bottom layer of all sets.

$\endgroup$

closed as off-topic by Andrés E. Caicedo, Leucippus, I am Back, user99914, Claude Leibovici Nov 10 '17 at 8:37

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Andrés E. Caicedo, Leucippus, I am Back, Claude Leibovici
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ What precisely do you mean by the last question? (As for the rest, this is a consequence of the axiom of foundation. And it is fairly easy to see that it is in fact equivalent to this axiom.) $\endgroup$ – Andrés E. Caicedo Nov 9 '17 at 18:07
  • 2
    $\begingroup$ Again, I do not understand what it is you are trying to covey by that expression. $\endgroup$ – Andrés E. Caicedo Nov 9 '17 at 19:39
  • $\begingroup$ See the treatment of this in Set Theory: An Introduction To Independence Proofs, by K.Kunen. $\endgroup$ – DanielWainfleet Nov 10 '17 at 3:11
  • $\begingroup$ @DanielWainfleet Where in Kunen are you referring to? On page 95, he defines $WF=\bigcup \{R(\alpha): \alpha\in On\}$ with the following comment that the well-founded sets are defined to be those in some $R(\alpha)$. So is there a proof. Thanks, $\endgroup$ – user12802 Jun 13 '18 at 22:04
4
$\begingroup$

EDIT: The following is based on the OP's comments below.

Let's look in detail at my claim $(i)$, below, which is really the heart of the argument (everything else is just leveraging this claim in a straightforward way). To repeat:

$(i)$ If $a$ is not cumulative, then $a$ has some non-cumulative element.

What does this use about the cumulative hierarchy?

Well, here's the proof of $(i)$: suppose every element of $a$ is cumulative. To each element $b$ of $a$, associate an ordinal $\beta_b$ such that $b\in V_{\beta_b}$ - e.g. let $\beta_b$ be the least such ordinal (which exists since the ordinals are well-ordered; alternatively, use choice).

The collection $B=\{\beta_b: b\in a\}$ is a set (by replacement - consider the formula $\varphi(x, y)\equiv$"$x\in a$ and $y=\beta_x$"), so there is an ordinal $\gamma$ greater than every ordinal in $B$ (why? this is essentially Burali-Forti).

Now think about $V_\gamma$. Since $\gamma>\beta_b$ for each $b\in a$, we have $b\in V_\gamma$ for each $b\in a$. In other words, $a\subseteq V_\gamma$. But then $a\in V_{\gamma+1}$, so $a$ is cumulative. And we're done.

${}{}$

Now what did we use about the ordinals and the cumulative hierarchy, here?

  • There is no biggest ordinal - this was needed to construct $\gamma+1$ from $\gamma$.

  • More significantly, any set of ordinals has some upper bound - this was needed to construct $\gamma$ in the first place.

  • The levels of the cumulative hierarchy are nested: if $\alpha_0>\alpha_1$ then $V_{\alpha_0}\supseteq V_{\alpha_1}$. This was needed to argue that $b\in V_\gamma$ for each $b\in a$.

  • We used the fact that every subset of one level of the cumulative hierarchy is an element of the next level, that is, $\mathcal{P}(V_\alpha)\subseteq V_{\alpha+1}$; this was needed to argue that $a\in V_{\gamma+1}$ since $a\subseteq V_\gamma$.

  • Additionally, if we want to avoid choice, we need that the ordinals are well-ordered, so that we could in fact pick $\beta_b$ for each $b\in a$.


I'm not sure what proofs you're reading, but here's an outline of the usual argument (you should be able to fill in the gaps):

We want to prove the following statement, in ZFC (but we'll improve this below):

For every $x$, there is some ordinal $\alpha$ such that $x\in V_\alpha$.

(Note that this requires us to define $V_\alpha$ in terms of $\alpha$ in the language of set theory; this isn't hard (HINT: transfinite recursion) but it does need to be done, and if you haven't seen it before it's worth trying to do.)

Crucially, we will use the axiom of foundation; this says that for any nonempty set $s$, there is an element $t\in s$ which is "minimal" in the sense that $t\cap s=\emptyset$ (there may be more than one such $t$, but there has to be at least one). Intuitively, foundation rules out things like infinite descending sequences of sets $w_0\ni w_1\ni w_2\ni ...$. Foundation is necessary here; in fact, over ZF minus foundation, the axiom of foundation is provably equivalent to the statement "every set is in the cumulative hierarchy."


OK, on to the proof sketch!

Say that a set $x$ is non-cumulative if $x$ is not in any $V_\alpha$ (and note that "non-cumulative" is in fact expressible in the language of ZFC). The key observation is:

$(i)$ If $x$ is non-cumulative, then $x$ has some non-cumulative element.

Proof sketch: prove the contrapositive. If every element of $x$ is in some level of the cumulative hierarchy, show that $x$ also is in the cumulative hierarchy (HINT: find a level $V_\alpha$ at which all elements of $x$ have shown up ...).

Now we iterate this, to show:

$(ii)$ If $x$ is noncumulative then there is a sequence of sets $x_0\ni x_1\ni x_2\ni ...$

Namely, take $x_0=x$ and let $x_{i+1}$ be any noncumulative element of $x_i$ (which will exist by induction on $i$).

But then:

$(iii)$ We're done, since this contradicts Foundation.


Note that this argument implicitly used the axiom of choice, in step $(ii)$, to pick $x_{i+1}$ from $x_i$. One natural question is:

Can we do this without choice?

This time, the answer is yes: while choice makes things simpler, it's not necessary at all.

Replacement is your friend here (incidentally, even though choice is "flashier" there are many senses in which replacement is really the "powerhouse" axiom). With replacement, we can prove that there is a set $y$ (e.g. the transitive closure of $x$) such that

  • $x\subseteq y$, and

  • $y$ is transitive: if $u\in v$ and $v\in y$ then $u\in y$.

(This is a good exercise.) Now given this $y$, look at the subset $\hat{y}$ consisting of all non-cumulative elements of $y$. Then $\hat{y}$ violates the axiom of foundation:

$(iv)$ If $a\in y$, then $a$ is noncumulative, so by $(i)$ we know that $a$ has a noncumulative element $b$; but since $y$ is transitive, we have $b\in y$, and since $b$ is noncumulative we have $b\in\hat{y}$, and hence $b\in a\cap\hat{y}$. So for every $a\in\hat{y}$, we have $a\cap\hat{y}\not=\emptyset$, which is exactly what foundation says can't happen.

I believe that replacement is in fact necessary, but set theory without replacement is quite weird, and I'm not confident of my claim.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.