## You are here

Homeexample of transfinite induction

## Primary tabs

# 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. (first ordinal) show that $\Phi(0)$ holds;

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

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. Since $0+0=0$ by definition, $\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 $\Phi(S\beta)$ holds.

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

## Mathematics Subject Classification

03B10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections