Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 38 · Ordinals and Well-Ordering

Transfinite Induction

Learn strong induction, well-founded induction and transfinite induction on ordinals, with runnable examples including Goodstein sequences.

Mathematical induction proves a statement for all natural numbers: show it for 0, and show that if it holds for n it holds for n + 1. That works because ℕ is well-ordered and every number is reached after finitely many steps. What about statements about ω + 1, or ω·2, or other ordinals? Ordinary induction cannot step across the limit ω. Transfinite induction is the version that can.

From induction to strong induction

Ordinary induction needs a base case and a step from n to n + 1. Strong induction is a more convenient form:

If, for every n, "the statement holds for all m < n" implies "the statement holds for n", then the statement holds for every n.

There is no separate base case: for n = 0 there are no smaller m, so the hypothesis is vacuous and the implication proves P(0) outright.

Strong induction is valid because ℕ is well-ordered. If the statement failed somewhere, the set of failures would have a least element n. But then all m < n satisfy the statement, so by the implication n does too, a contradiction.

Python Strong induction in action: prime factorization

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The recursion in the code mirrors the proof: the function calls itself on smaller numbers.

Transfinite induction

Theorem (transfinite induction). Let P(α) be a property of ordinals. Suppose that for every ordinal α:

if P(β) holds for all β < α, then P(α) holds.

Then P(α) holds for every ordinal α.

The proof is the same minimal-counterexample argument: if some ordinal fails, there is a least failing ordinal α (the ordinals are well-ordered), but all smaller ones succeed, so α succeeds too. Contradiction.

In practice you split the step into three cases:

  1. Zero: prove P(0).
  2. Successor: if P(α), prove P(α + 1).
  3. Limit: if λ is a limit ordinal and P(β) holds for all β < λ, prove P(λ).

The third case is new. It is the leap across infinity.

flowchart LR
  A["P(0)"] --> B["P(α) ⇒ P(α+1)"]
  B --> C["P(β) for all β < λ ⇒ P(λ)"]
  C --> D["P(α) for every ordinal α"]

The three cases of a transfinite induction.

Transfinite recursion

The same idea defines objects. To define F(α) for all ordinals, say how to get F(0), how to get F(α + 1) from F(α), and how to get F(λ) for a limit λ from the values F(β), β < λ. Ordinal arithmetic (next lesson) is defined exactly this way:

Text
α + 0     = α
α + (β+1) = (α + β) + 1
α + λ     = sup of (α + β) for β < λ         (λ a limit)

Goodstein sequences: induction beyond the naturals

A striking use of ordinals is Goodstein's theorem (1944). Write a number n in hereditary base-b notation: write it in base b as a sum of powers of b and also write all the exponents in base b, and so on. Then define the sequence:

  1. Replace every b by b + 1 in that notation (this makes the number grow, usually a lot).
  2. Subtract 1.
  3. Repeat with the next base.

Goodstein proved that for every starting number the sequence eventually reaches 0, even though it can first rise to astronomical values. The proof replaces each term by the ordinal obtained by substituting ω for the base. These ordinals form a strictly decreasing sequence, and by well-ordering such a sequence must end. The ordinals involved go up to ε₀, the limit of ω, ω^ω, ω^ω^ω, .... In 1982 Laurence Kirby and Jeff Paris showed that this theorem cannot be proved from the usual axioms of arithmetic (Peano arithmetic), although it is provable with transfinite induction up to ε₀.

Python Compute Goodstein sequences

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sequence for 3 ends quickly at 0. The sequence for 4 takes a very large number of steps to come down, far more than we could ever run. The proof guarantees it ends anyway.

A second use: well-founded recursion on trees

Induction on ordinals extends to any well-founded relation, meaning one with no infinite descending chain. Programs on finite trees terminate for this reason: each recursive call goes to a smaller subtree. Here is the idea in code.

Python Recursion terminates by well-foundedness

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which case is new in transfinite induction compared with ordinary induction?

    At a limit ordinal there is no immediate predecessor, so we assume the property for all smaller ordinals and prove it for the limit.
  2. 2. Why does strong induction need no separate base case?

    For n = 0 the statement 'holds for all m < 0' is vacuously true, so the step itself proves the case n = 0.
  3. 3. What guarantees that a Goodstein sequence reaches 0?

    The terms themselves can grow enormously. It is the associated ordinals that decrease, and no infinite descending chain of ordinals exists.
  4. 4. Transfinite induction is valid because...

    If the property failed, the least failing ordinal would lead to a contradiction.

Summary

  • Strong induction assumes the statement for all smaller numbers and needs no separate base case.
  • Transfinite induction works for ordinals, with zero, successor and limit cases.
  • Transfinite recursion defines functions on ordinals the same way; ordinal arithmetic is defined this way.
  • Goodstein's theorem is proved by showing an ordinal sequence strictly decreases; it is not provable in Peano arithmetic.
  • Any well-founded relation supports induction and terminating recursion.

Next: Ordinal Arithmetic