A mathematician proves P(0) holds, and proves that for all ordinals α, if P(α) holds then P(α+1) holds. They conclude P holds for every ordinal. What is the error?
AThe base case should be P(1), not P(0)
BThis only establishes P for successor ordinals reachable from 0 by finite steps — it fails at ω because ω has no immediate predecessor, so the successor step has nothing to hand off from
CThe proof is valid — any property provable for 0 and preserved by successors holds for all ordinals
DP(0) is unnecessary if the successor step is sufficiently strong
The successor step only lets you move from α to α+1 — it inherits from an immediate predecessor. ω is a limit ordinal: it has no immediate predecessor. There is no 'last finite number' from which the successor step can pass P(ω). The domino chain analogy breaks down: you can knock over every finite domino without ever reaching ω. The limit step is precisely the mechanism that handles this gap — it says that if P holds for all β < λ, it holds for λ. Without it, the proof only reaches the finite ordinals.
Question 2 Multiple Choice
In a transfinite induction proof, the limit step states: if P(β) holds for all β < λ, then P(λ). Why must this step assume P holds for ALL β < λ, rather than just for the ordinal immediately before λ?
AIt is a convention that makes proofs easier to write, not a logical necessity
BBecause limit ordinals like ω have no immediate predecessor — there is no 'ordinal immediately before' them from which to inherit
CTo avoid circular reasoning, since λ is defined in terms of its predecessors
DBecause limit ordinals are uncountable and therefore cannot have immediate predecessors
A limit ordinal λ is defined precisely as an ordinal with no immediate predecessor. ω is the smallest limit ordinal: every ordinal less than ω is a natural number, and there is no 'largest natural number' that is immediately below ω. Since there is no element immediately before λ, there is nothing to inherit from in the successor-step pattern. The limit step instead collects evidence from the entire downward neighborhood — all β < λ — and from that collective evidence infers P(λ). This is why the limit step uses the 'strong induction' pattern.
Question 3 True / False
Every ordinal is exactly one of three kinds: zero, a successor ordinal, or a limit ordinal — and a transfinite induction proof must handle all three cases separately to cover every ordinal.
TTrue
FFalse
Answer: True
This three-way partition of the ordinals is what makes transfinite induction exhaustive. Zero is its own case (not a successor, not a limit ordinal). Every other ordinal is either a successor (of the form α+1 for some α) or a limit ordinal (with no immediate predecessor, like ω, ω·2, ω², ε₀). A proof that handles all three cases has no gaps — every ordinal falls into exactly one bucket. Omitting any case leaves ordinals for which the property has not been established.
Question 4 True / False
A proof by transfinite induction that establishes P(0) (base case) and the successor step (P(α) → P(α+1)) is sufficient to prove P holds for most ordinals, including ω and beyond.
TTrue
FFalse
Answer: False
This is the central misconception flagged in the Common Misconceptions section. Without the limit step, the proof only reaches ordinals that are finitely many successor steps from 0 — all the natural numbers. It stops completely at ω. ω is not a successor of any natural number; it is the limit of the entire sequence. The limit step — if P holds for all β < λ, then P(λ) — is the essential addition that allows transfinite induction to jump over these accumulation points and reach all ordinals.
Question 5 Short Answer
Why does ordinary mathematical induction fail to reach the ordinal ω, and what does the limit step of transfinite induction add to fix this?
Think about your answer, then reveal below.
Model answer: Ordinary induction works as a domino chain: prove the first domino falls (base case), prove each domino knocks over the next (inductive step), and by repetition all dominoes fall. This works perfectly for natural numbers because they are arranged in a linear succession — you can reach any natural number by starting from 0 and taking finitely many successor steps. But ω is not reachable by finitely many successor steps from 0; it is the ordinal that comes *after* all natural numbers, a 'limit' with no immediate predecessor. There is no finite natural number n such that n+1 = ω. The limit step fixes this by saying: if P holds for every ordinal below some limit ordinal λ, then P holds for λ. This lets the proof 'jump' from knowledge about all of {0, 1, 2, 3, ...} to a conclusion about ω — their limit.
The analogy in the Explainer is illuminating: transfinite induction handles not just a line of dominoes but infinitely long 'rows' that accumulate into new dominoes (limit ordinals). The limit step is the mechanism for collecting evidence from an entire infinite row and using it to topple the accumulation point.