# example of transfinite induction

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

1. 1.

(first ordinal) show that $\Phi(0)$ holds;

2. 2.

(successor ordinal) if $\Phi(\beta)$ holds, then $\Phi(S\beta)$ holds;

3. 3.

(limit ordinal) if $\Phi(\gamma)$ holds for all $\gamma<\beta$ and $\beta=\sup\{\gamma\mid\gamma<\beta\}$, then $\Phi(\beta)$ holds.

Below is an example of a proof using transfinite induction.

###### Proposition 1.

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

###### Proof.

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

1. 1.

Since $0+0=0$ by definition, $\Phi(0)$ holds.

2. 2.

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

3. 3.

Suppose $\beta=\sup\{\gamma\mid\gamma<\beta\}$ and $0+\gamma=\gamma$ for all $\gamma<\beta$. Then

 $0+\beta=0+\sup\{\gamma\mid\gamma<\beta\}=\sup\{0+\gamma\mid\gamma<\beta\}.$

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

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

Title example of transfinite induction ExampleOfTransfiniteInduction 2013-03-22 17:51:12 2013-03-22 17:51:12 CWoo (3771) CWoo (3771) 6 CWoo (3771) Example msc 03B10