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. ∎
Title  example of transfinite induction 

Canonical name  ExampleOfTransfiniteInduction 
Date of creation  20130322 17:51:12 
Last modified on  20130322 17:51:12 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  6 
Author  CWoo (3771) 
Entry type  Example 
Classification  msc 03B10 