Rank of a well-founded set is one plus the supremum over the ranks of its elements

273 Views Asked by At

I'm trying to prove the following lemma left as an exercise in my course notes.

If $x$ is a well-founded set, then $$ \mathrm{rank}(x) = \sup \{ \mathrm{rank}(y) + 1 : y \in x \} $$

Proof. Let $\alpha = \sup \{ \mathrm{rank}(y) + 1 : y \in x \}$. It suffices to show that $x \in V_{\alpha + 1}$ but $x \notin V_\alpha$. Notice that for any $y \in x$, $\mathrm{rank}(y) < \alpha$ by definition. Hence, $y \in V_\alpha$. Since $\forall y \in x : y \in V_\alpha$, $x \subseteq V_\alpha$, so by definition $x \in V_{\alpha + 1}$.

The part I'm struggling to show is that $x \notin V_\alpha$. I don't see how assuming this leads to a contradiction.

2

There are 2 best solutions below

1
On BEST ANSWER

As $\alpha$ is the least ordinal that is $>\operatorname{rank}(y)$ for all $y\in x$, the assumption that $\operatorname{rank}(x)<\alpha$ means that $\operatorname{rank}(x)\le\operatorname{rank}(y)$ for some $y\in x$. But that is impossible.

0
On

Suppose $y \in BF(\alpha)$ then by definition $rank(y) < \alpha$.

Now return to y. You know that $x \in y \rightarrow rank(x) < rank(y)$. Then $$ rank(x) + 1 \leq rank(y) \mathbb \space \forall x\in y $$

Now look back at your definition of supremum. With the above line we have created an upper bound lower than the supremum $a$ which contradicts the minimality of $\alpha$. Thus $ y \not\in BF(\alpha)$