example of transfinite induction
Below is an example of a proof using transfinite induction.
for any ordinal .
Let be the property: . We follow the three steps outlined above.
Since by definition, holds.
Suppose . By definition , which is equal to by the induction hypothesis, so holds.
Suppose and for all . Then
The second equality follows from definition. Furthermore, the last expression above is equal to by the induction hypothesis. So holds.
Therefore holds for every ordinal , which is the statement of the theorem, completing the proof. ∎