MathLabs
TheoremProved

Principle of transfinite induction

Statement

Let CC be a class of ordinals such that for every ordinal α\alpha: if β∈C\beta \in C for all β<α\beta<\alpha, then α∈C\alpha \in C. Then CC contains every ordinal.

Why is it true?

This lets us prove a statement for every ordinal — finite, ω\omega, and beyond — by only ever handling "assume it holds for everything smaller", with no separate base case and no separate limit case needed in the statement of the principle itself.

Proof sketch

Suppose, for contradiction, that CC does not contain every ordinal. Then the class DD of ordinals not in CC is nonempty. The ordinals themselves form a well-order (any nonempty class of ordinals has a least element — this is essentially the defining property of the ordinals), so DD has a least element; call it α\alpha.

By minimality of α\alpha, every ordinal β<α\beta<\alpha is not in DD, i.e. every β<α\beta<\alpha satisfies β∈C\beta \in C.

But this is exactly the hypothesis of the theorem applied to α\alpha: "β∈C\beta \in C for all β<α\beta<\alpha" implies α∈C\alpha \in C. So α∈C\alpha \in C.

This contradicts α∈D\alpha \in D (i.e. α∉C\alpha \notin C). The contradiction shows no such least counterexample α\alpha can exist, so D=∅D=\emptyset: CC contains every ordinal. ■\blacksquare

Topics that use this theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

  1. Wikipedia contributors (2024). Ordinal number
  2. Wikipedia contributors (2024). König's theorem (set theory)
  3. Wikipedia contributors (2024). Goodstein's theorem