Application of Transfinite Induction

Question

Our teacher gave us for practice to prove some properties of $V(\alpha)$ defined as $$V(0) = \emptyset,\; V(S(\alpha)) = \mathcal{P}(V(\alpha)),\; Lim(\alpha): V(\alpha) = \bigcup\{V(\beta)\; |\; \beta < \alpha\}$$ The properties are

1) $\alpha < \beta \Rightarrow V(\alpha) \subseteq V(\beta)$

2) $\alpha \in V(S(\alpha))$

3) $\alpha \notin V(\alpha)$

We should use transfinite induction to prove them. However, I've never seen a real application of transfinite induction ever. Although I know its definition I still can't figure out a way how to apply it. Can someone help me?

Answer 1

Since the $V(\alpha)$ hierarchy is defined by transfinite recursion on ordinals, many statements about the hierarchy lend themselves to proofs by transfinite induction on ordinals. For instance, to prove

$$\forall \alpha,\ \alpha \notin V(\alpha)$$

You need to show:

1. $0\notin V(0)$
2. $\alpha \notin V(\alpha) \rightarrow \alpha+1 \notin V(\alpha+1)$
3. $(\forall \beta < \alpha,\ \beta \notin V(\beta)) \rightarrow \alpha\notin V(\alpha)$ if $\alpha$ limit.

These three statements are straightforward, just apply the definition of the $V(\alpha)$ hierarchy (and the definitions of "successor" and "limit" ordinal).

Answer 2

I’ll use (2) as an example. Suppose that $\alpha$ is an ordinal, and $\beta\in V(S(\beta))$ for all $\beta<\alpha$. Suppose that $\beta\in\alpha$. Then $\beta$ is an ordinal, and $\beta<\alpha$, so by hypothesis $\beta\in V(S(\beta))$. Moreover, $S(\beta)\le\alpha$, so $V(S(\beta))\subseteq V(\alpha)$ by (1), and hence $\beta\in V(\alpha)$. Since $\beta$ was an arbitrary element of $\alpha$, $\alpha\subseteq V(\alpha)$, and therefore $\alpha\in\wp(V(\alpha))=V(S(\alpha))$. It follows by induction that $\alpha\in V(S(\alpha))$ for each ordinal $\alpha$.

Note that in this argument there was no need to split the induction into successor and limit cases: the same argument works for all ordinals $\alpha$. There is also no need for a basis step, because it’s vacuously true that $\beta\in V(S(\beta))$ for all $\beta<0$: there are no such $\beta$!

A variant of this is to suppose that the result is false and let $\alpha$ be the minimum counterexample; this makes sense, since the ordinals are well-ordered. Then you can use the argument in the first paragraph to get a contradiction, from which you may conclude that there is no counterexample and hence that the theorem is true. This is still a proof by transfinite induction.

For (3), on the other hand, you’ll find that you really do want to split the limit and successor cases, as suggested by Amit Kumar Gupta in his answer.

Clearly you want to do (1) before (2), so that you can use it in proving (2). The fact that two ordinals, $\alpha$ and $\beta$, are involved may make it harder to see what you should induct on. I suggest fixing $\alpha$ and proving by induction on $\beta\ge\alpha$ that $V(\alpha)\subseteq V(\beta)$. In other words, the induction is on $\beta$, and $\alpha$ is an arbitrary but fixed ordinal.

You can get the same effect by looking at this from the minimum counterexample point of view. If the theorem is false, there is a least ordinal $\alpha$ such that there is a $\gamma>\alpha$ with $V(\alpha)\nsubseteq V(\gamma)$, and among such $\gamma$ there is a least one, $\beta$. Thus, you can assume that if $\eta<\alpha$ and $\eta<\gamma$, then $V(\eta)\subseteq V(\gamma)$, and you can assume that if $\gamma>\beta$, then $V(\alpha)\subseteq V(\gamma)$. This is the information from which you have to derive your contradiction.

Whether you approach it in the traditional fashion or by trying to get a contradiction from a minimal counterexample, you’ll find that here too you want to split the limit and successor cases.