# Exercises on transfinite induction

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.

## 1 Answer

• 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\$$.

• Thanks! I have a few questions about (ii). In the third bullet point, how does it follow that $\{\beta\}\subseteq V(\beta+1)$? Also, in the last line you have $\beta\cup \{\beta\}\not\subseteq V(\beta)$; I'm assuming the reasoning is that if $\beta\cup \{\beta\}\subseteq V(\beta)$ then $\beta \subseteq V(\beta)$ and this contradicts $\beta \notin V(\beta)$. But I only know that proper inclusion $a \subset b$ implies containment $a\in b$, I'm not sure why improper inclusion would still imply that. Commented Feb 22, 2022 at 22:28
• In the fourth bullet point, it looks to me that you're saying that any limit ordinal $\alpha$ can be written as $\alpha = \cup_{\beta < \alpha} \beta$. But how do we know that? Later you're using that $\alpha = \cup_{\beta < \alpha} \beta$ implies $\alpha \subseteq \cup_{\beta < \alpha} \beta$ to prove that $\alpha \subseteq V(\alpha)$ if I'm not misinterpreting your argument, but I don't see why the limit ordinal should be contained in the union of all ordinals smaller than it. Commented Feb 22, 2022 at 22:32
• I've added a proof that $\ \alpha=\bigcup_\limits{\beta<\alpha}\beta\$ when $\ \alpha\$ is a limit ordinal. If $\ \beta\in V(\beta+1)\$ then every member of $\ \{\beta\}\$ (namely $\ \beta\$) is also a member of $\ V(\beta+1)\$, from which it follows that $\ \{\beta\}\subseteq V(\beta+1)\$. Conversely, if $\ \beta\notin V(\beta)\$, then there is a member of $\ \beta\cup\{\beta\}\$ (namely $\ \beta\$, because $\ \beta\in\{\beta\}\$) which is not a member of $\ V(\beta)\$. Therefore $\ \beta\cup\{\beta\}\$ cannot be a subset of $\ V(\beta)\$. Commented Feb 23, 2022 at 9:42