example of transfinite induction

Suppose we are interested in showing the property $\mathrm{\Phi }(\alpha )$ holds for all ordinals $\alpha$ using transfinite induction. The proof basically involves three steps:

1. (first ordinal) show that $\mathrm{\Phi }(0)$ holds;

2. (successor ordinal) if $\mathrm{\Phi }(\beta )$ holds, then $\mathrm{\Phi }(S\beta )$ holds;

3. (limit ordinal) if $\mathrm{\Phi }(\gamma )$ holds for all and , then $\mathrm{\Phi }(\beta )$ holds.

Below is an example of a proof using transfinite induction.

Proposition 1.

$0+\alpha =\alpha$ for any ordinal $\alpha$.

Proof.

Let $\mathrm{\Phi }(\alpha )$ be the property: $0+\alpha =\alpha$. We follow the three steps outlined above.

1. Since $0+0=0$ by definition, $\mathrm{\Phi }(0)$ holds.

2. Suppose $0+\beta =\beta$. By definition $0+S\beta =S(0+\beta )$, which is equal to $S\beta$ by the induction hypothesis, so $\mathrm{\Phi }(S\beta )$ holds.

3. Suppose and $0+\gamma =\gamma$ for all . Then

   The second equality follows from definition. Furthermore, the last expression above is equal to by the induction hypothesis. So $\mathrm{\Phi }(\beta )$ holds.

Therefore $\mathrm{\Phi }(\alpha )$ holds for every ordinal $\alpha$, which is the statement of the theorem, completing the proof.∎