# Proof of two facts on the von Neumann hierarchy by transfinite induction

I have two problems about ordinal numbers.

Set $V_0 = \emptyset$ and if we have define $V_a$ then $V_{a+1}= \mathcal{P}(V_a)$ if $a$ is successor and let $V_{\beta}= \sup\{ V_a ,\quad a<\beta \}= \bigcup \{ V_a ,\quad a< \beta \}$

1.For every ordinal $a$ prove that $a \in V_{a+1}$

2.If $a\in \beta$ then prove that $V_a \in V_{\beta}$

I want to prove these using Transfinite induction but I can't. Can you give some help?

-

1. If $a=\emptyset$, then $\emptyset\in \mathcal{P}(\emptyset) = \mathcal{P}(V_a) = V_{a+1}$, as desired.

If the result holds for $a$, then it holds for $a+1$: we know that $a\in V_{a+1}=\mathcal{P}(V_a)$; we need to show that $a\cup\{a\}\in \mathcal{P}(V_{a+1})$. Since $a\in V_{a+1}$, then $a\subseteq V_a$. Since $a$ is an ordinal, if $b\in a$, then $b\subseteq a$, hence $b\subseteq V_a$; thus, $b\in\mathcal{P}(V_a) = V_{a+1}$. Thus, for every $b\in a$, $b\in V_{a+1}$, which shows that $a\subseteq V_{a+1}$. Therefore, since $a\in V_{a+1}$ and $a\subseteq V_{a+1}$, it follows that $a\cup\{a\}\subseteq V_{a+1}$, hence $a\cup\{a\}=a+1\in \mathcal{P}(V_{a+1})=V_{a+2}$, as desired.

Finally, assume that $b$ is a limit ordinal and for all $a\lt b$ we have $a\in V_{a+1}$. We want to show that $b\in V_{b+1}$.

If $a\lt b$, then $a\in V_{a+1}\subseteq V_b$; since $b$ is an ordinal, this implies that if $a\in b$, then $a\in V_b$. Hence, $b\subseteq V_b$, so $b\in\mathcal{P}(V_{b}) = V_{b+1}$, as desired.

-
@passenger: Hey, I only did one; I don't see how it can be "accepted" since I didn't do the second part. You should really not accept it quite yet. – Arturo Magidin Jan 25 '12 at 20:22
I can do the second part now. Thank's for the answer! – passenger Jan 25 '12 at 20:25

To show $a \in V_{a+1}$ I'll use that $V_\alpha$ are transitive.

Claim 0: $V_\alpha$ are transitive, that is, if $a \in V_\alpha$ then $a \subset V_\alpha$

Proof: By transfinite induction over $\alpha$.

Case $\alpha = \emptyset$: We trivially have that for all $a$ in $V_\emptyset = \emptyset$ that $a \subset V_\emptyset$.

Case $\alpha = \beta + 1$ is a successor ordinal: Assume that for all $a \in V_\beta$ we have $a \subset V_\beta$ and let $b \in V_{\beta + 1} = P(V_\beta)$. Then for each $x$ in $b$ we have that $x \in V_\beta$. By assumption we have $x \subset V_\beta$, so for each $y \in x$ we have $y \in V_\beta$. Hence for each $y$ in $x$, $\{y \} \in P(V_\beta)$ and hence $\bigcup_{y \in x} \{y\} = x \in P(V_\beta) = V_{\beta + 1}$. So for each $x$ in $b$ we have $x \in V_{\beta + 1}$ which is the same as saying $b \subset V_{\beta + 1}$.

Case $\lambda$ is a limit ordinal: Assume that for all $\beta < \lambda$ we have $x \in V_\beta$ implies that $x \subset V_{\lambda}$ and let $b \in V_{\lambda} = \bigcup_{\beta < \lambda} V_\beta$. Then there exists a $\beta < \lambda$ such that $b \in V_\beta$. Then by assumption $b \subset V_\beta \subset \bigcup_{\beta < \lambda} V_\beta = V_{\lambda}$.

Claim 1: $a \in V_{a + 1}$

Proof: By transfinite induction over $a$.

Case $a = \emptyset$: $a = \emptyset \in P(V_\emptyset) = P(\emptyset) = \{\emptyset\}$.

Case $a = b + 1$ is a successor ordinal: Assume that $b \in V_{b+1}$. We want to show $b + 1 \in V_{b + 2}$ where $b + 1 = b \cup \{b \}$. Since $b \in V_{b + 1}$ we have $\{b\} \in P(V_{b + 1}) = V_{b + 2}$. Since $V_\alpha$ are transitive we have $b \subset V_{b+1}$ and so for all $x$ in $b$, $x$ is also in $V_{b+1}$. Hence $\{x\} \in P(V_{b+1}) = V_{b+2}$ and so $b = \bigcup_{x \in b} \{x\} \in P(V_{b+1}) = V_{b+2}$. Hence $b \cup \{b\} \in V_{b+2}$ or in other words $a \in V_{a + 1}$.

Case $a = \lambda$ is a limit ordinal: Assume that we have $b \in V_{b+1}$ for all $b < \lambda$. We want to show that $\lambda \in V_{\lambda+1} = P(V_\lambda)$. By transitivity of $V_\alpha$ we have that if $c < d$ then $V_c \subset V_d$ hence for $b+1 < \lambda$ we get $V_{b+1} \subset V_\lambda$. By assumption, $b \in V_{b+1}$ hence $b \in V_\lambda$ for all $b + 1 < \lambda$ and hence $b \in P(V_{\lambda})$. So we have $\cup \{b \mid b + 1 < \lambda \} =\cup \{b \mid b < \lambda \} = \lambda \in P(V_{\lambda})$.

Claim 2: If $\alpha \in \beta$ then $V_\alpha \in V_\beta$

Proof:

I'll write $\alpha \in \beta$ as $\alpha < \beta$. We know that for $\alpha < \beta$ we have $V_\alpha \subset V_\beta$.

If $\beta$ is a successor ordinal then there is a $\gamma$ such that $V_\beta = P(V_\gamma)$ for $\gamma + 1 = \beta$. If $\alpha = \gamma$ then $V_\alpha \in V_\beta$. If $\alpha < \gamma$ then $V_\alpha \in V_{\alpha + 1} \subseteq V_\gamma \subset V_\beta$.

If $\beta > 0$ is a limit ordinal then $V_\beta = \bigcup_{\gamma < \beta} V_\gamma$. Since $\beta$ is a limit ordinal we have $\alpha < \alpha + 1 < \beta$ and hence $V_\alpha \in P(V_\alpha) = V_{\alpha + 1} \subset V_\beta$.

-
There was already a good answer but I thought I'd add an answer to the second part, just for completion. – Rudy the Reindeer Jan 30 '12 at 18:13