example of transfinite induction


Suppose we are interested in showing the property Φ(α) holds for all ordinalsMathworldPlanetmathPlanetmath α using transfinite inductionMathworldPlanetmath. The proof basically involves three steps:

  1. 1.

    (first ordinal) show that Φ(0) holds;

  2. 2.

    (successor ordinal) if Φ(β) holds, then Φ(Sβ) holds;

  3. 3.

    (limit ordinal) if Φ(γ) holds for all γ<β and β=sup{γγ<β}, then Φ(β) holds.

Below is an example of a proof using transfinite induction.

Proposition 1.

0+α=α for any ordinal α.

Proof.

Let Φ(α) be the property: 0+α=α. We follow the three steps outlined above.

  1. 1.

    Since 0+0=0 by definition, Φ(0) holds.

  2. 2.

    Suppose 0+β=β. By definition 0+Sβ=S(0+β), which is equal to Sβ by the induction hypothesis, so Φ(Sβ) holds.

  3. 3.

    Suppose β=sup{γγ<β} and 0+γ=γ for all γ<β. Then

    0+β=0+sup{γγ<β}=sup{0+γγ<β}.

    The second equality follows from definition. Furthermore, the last expression above is equal to sup{γγ<β}=β by the induction hypothesis. So Φ(β) holds.

Therefore Φ(α) holds for every ordinal α, which is the statement of the theoremMathworldPlanetmath, completing the proof. ∎

Title example of transfinite induction
Canonical name ExampleOfTransfiniteInduction
Date of creation 2013-03-22 17:51:12
Last modified on 2013-03-22 17:51:12
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 6
Author CWoo (3771)
Entry type Example
Classification msc 03B10