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	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