Exercises on transfinite induction

Question

Define by transfinite recursion $V(0)=\emptyset, V(\alpha+1)=\mathcal P(V(\alpha)), V(\alpha)=\cup_{\beta < \alpha}V(\beta)$ for $\beta$ a limit ordinal.

I'm trying to show the following properties: (i) $V(\alpha)$ is transitive; (ii) $\alpha \in V(\alpha+1)-V(\alpha),$ (iii) if $\alpha \leq \beta$ then $V(\alpha)\subseteq V(\beta)$.

(i) The base case and the step for $\alpha+1$ are clear. Suppose $\alpha$ is a limit ordinal and suppose for all $\beta < \alpha$ $V(\beta)$ is transitive. Consider $V(\alpha)=\cup_{\beta < \alpha} V(\beta)$. Suppose $a\in b\in V(\alpha)$. Since $b\in\cup_{\beta < \alpha} V(\beta) $, $b\in V(\beta) $ for some $\beta < \alpha$. Since $a\in b\in V(\beta)$ and since $V(\beta)$ is transitive, we have $a\in V(\beta)$ so $a\in V(\alpha)$. Is this a correct argument? I don't see where I used that $\alpha$ is a limit ordinal. Or is this assumption not needed here?

(ii) The base case is clear. Suppose $\alpha \in V(\alpha+1)-V(\alpha)$. Consider $\alpha+1=\alpha\cup\{\alpha\}$. The aim is to prove that $\alpha + 1\in V(\alpha+2)-V(\alpha+1)=\mathcal P(V(\alpha+1))-\mathcal P(V(\alpha))$. Since $\alpha \in V(\alpha+1)-V(\alpha)$, we have $\alpha \subset V(\alpha+1)-V(\alpha)$, so $\alpha \in \mathcal P(V(\alpha+1))-\mathcal P(V(\alpha))$. But I don't see what to do next.

For the limit case, suppose $\beta\in V(\beta+1)-V(\beta)$ for all $\beta < \alpha$, where $\alpha $ is a limit ordinal. The aim is to prove that $\alpha \in \mathcal P (\cup_{\beta < \alpha +1} V(\beta)) - \mathcal P (\cup_{\beta < \alpha } V(\beta)) $. How to proceed from this?

(iii) I tried to do this by the induction on $\alpha$. Suppose [$\alpha \leq \beta]\implies [V(\alpha)\subseteq V(\beta)]$ and suppose $\alpha + 1 \leq \beta$. Then $\alpha\cup\{\alpha\}\subseteq \beta$, so $\alpha \subseteq \beta$. By the assumption, this implies $V(\alpha)\subseteq V(\beta)$. The aim is to show that $\mathcal P(V(\alpha))\subseteq V(\beta)$. So let $x\subseteq V(\alpha)$. I don't see how to show that it's an element of $V(\beta)$.

For the limit case, let $\alpha$ be a limit ordinal and suppose for all $\gamma < \alpha$, $\gamma \leq \beta$ implies $V(\gamma) \subseteq V(\beta)$. Suppose $\alpha \leq \beta$. The aim is to show that $V(\cup_{\beta < \alpha} V(\beta))\subseteq V(\beta)$. I guess at this point, as in the limit step in (ii), I'm confused how to work with $V$ of a union.

Answer 1

• Your argument for property (i) looks ok to me, but it also looks to me like you did use the fact that $\ \alpha\ $ is a limit ordinal when you wrote $\ V(\alpha)=\bigcup_\limits{\beta<\alpha} V(\beta)\ $.

• I don't believe your statement that $\ \alpha\subset V(\alpha+1)-V(\alpha)\ $ in your attempted proof of property (ii) is true for any $\ \alpha\ge3\ $. I get \begin{align} V(2)&=\{0,1\}=2\ ,\\ V(3)&={\cal P}\big(V(2)\big)=\{0,1,\{1\},2\}\ \text{, and}\\ V(3)&-V(2)=\{\{1\},2\}\ , \end{align} for instance. So, while $\ 2\subset V(3)\ $, and $\ 2\in V(3)-V(2)\ $, $\ 2\not\subset V(3)-V(2)\ $ $\big($in fact, $\ 2\cap\big(V(3)-V(2)\big)=\emptyset\ \big)$. However, you don't need $\ \alpha\subset V(\alpha+1)-V(\alpha)\ $ anyway, only $\ \alpha\subseteq V(\alpha+1)\ $, which follows from $\ \alpha\in V(\alpha+1)\ $ and the transitivity of $\ V(\alpha+1)\ $, which you've already proved. It therefore seems to me that it might be easier to prove (ii) by treating the two propositions $\ \alpha\in V(\alpha+1)\ $ and $\ \alpha\not\in V(\alpha)\ $ separately.

• If $\ \alpha=\beta+1=\beta\cup\{\beta\}\ $ is a successor ordinal, and $\ \beta\in V(\beta+1)\ $, then $\ \beta\subseteq V(\beta+1)\ $ by the transitivity of $\ V(\beta+1)\ $, so $\ \beta \cup\{\beta\}\subseteq V(\beta+1)\ $, and hence $\ \beta\cup\{\beta\}=\alpha\in{\cal P}\big(V(\beta+1)\big)=$$\,V(\alpha+1)\ $.

  If $\ \beta\notin V(\beta)\ $, then $\ \alpha=\beta\cup\{\beta\}\not\subseteq V(\beta)\ $, and so $\ \alpha\notin$$\,{\cal P}\big(V(\beta)\big)=V(\alpha)\ $.

• If $\ \alpha=\bigcup_\limits{\beta<\alpha}\beta\ $ is a limit ordinal, and $\ \beta\in V(\beta+1)\ $ for all $\ \beta<\alpha\ $, then $\ \beta\subseteq V(\beta+1)\ $ for all such $\ \beta\ $ by the transitivity of $\ V(\beta+1)\ $, so $\ \alpha=$$\,\bigcup_\limits{\beta<\alpha}\beta\subseteq$$\,\bigcup_\limits{\beta<\alpha}V(\beta+1)\subseteq$$\,V(\alpha)\ $, and therefore $\ \alpha\in{\cal P}\big(V(\alpha)\big)=V(\alpha+1)\ $.

  If $\ \beta\notin V(\beta)\ $ for any $\ \beta<\alpha\ $ but $\ \alpha\in V(\alpha)=\bigcup_\limits{\beta<\alpha}V(\beta)\ $, then $\ \alpha\in V(\beta)\ $ for some $\ \beta<\alpha\ $. But $\ \beta<\alpha\Leftrightarrow\beta\in\alpha\ $, and so, by the transitivity of $\ V(\beta)\ $, we'd have $\ \beta\in V(\beta)\ $, which contradicts the induction hypothesis. Therefore $\ \alpha\notin V(\alpha)\ $.

• For proving $\ \alpha\le\beta\Rightarrow V(\alpha)\subseteq V(\beta)\ $ I'd suggest trying induction on $\ \beta\ $ rather than $\ \alpha\ $, for which I don't think the proof will be all that difficult. As you've already found, a proof by induction on $\ \alpha\ $ doesn't appear to be easy.

Proof that $\ \alpha=\bigcup_\limits{\beta<\alpha}\beta\ $ for $\ \alpha $ a limit ordinal

\begin{align} \gamma\in\bigcup_\limits{\beta<\alpha}\beta&\Rightarrow\gamma\in\beta\ \ \text {for some}\ \beta<\alpha\\ &\Rightarrow\gamma<\beta<\alpha\\ &\Rightarrow\gamma<\alpha\\ &\Rightarrow\gamma\in\alpha\ . \end{align} Therefore $\ \bigcup_\limits{\beta<\alpha}\beta\subseteq\alpha\ $.

Conversely, \begin{align} \gamma\in\alpha&\Rightarrow\gamma<\alpha\\ &\Rightarrow\gamma\in\gamma+1<\alpha\\ &\Rightarrow\gamma\in\bigcup_\limits{\beta<\alpha}\beta\ . \end{align} Therefore $\ \alpha\subseteq\bigcup_\limits{\beta<\alpha}\beta\ $.