Questions: Transfinite Recursion

Question 1

When defining ordinal addition α + β by transfinite recursion on β, what is the correct definition at a limit ordinal λ?

• A. α + λ = (α + (λ-1)) + 1, using the predecessor of λ
• B. α + λ = α + ω, since all limit ordinals behave like ω
• C. α + λ = sup{α + β : β < λ}, taking the supremum over all prior values
• D. α + λ = α, since adding a limit ordinal contributes nothing

Answer: (C)

Limit ordinals have no immediate predecessor — that is exactly what makes them limit ordinals. Since there is no 'previous value' to step from, we cannot define α + λ as 'one more than α + (λ-1).' Instead, the definition takes the supremum of all prior values α + β for β < λ. This limit clause is the distinctive feature of every transfinite recursion, with no analogue in ordinary natural-number recursion.

Question 2

Why does transfinite recursion require the Axiom of Replacement?

• A. Without it, ordinals may not be well-ordered, breaking the inductive structure
• B. Without it, the collection {F(β) : β < λ} at a limit stage may not form a set, making the limit-step definition impossible
• C. Without it, successor ordinals cannot be constructed from their predecessors
• D. Without it, the power set operation used in the cumulative hierarchy is unavailable

Answer: (B)

To define F(λ) at a limit ordinal as a supremum or union, you first need {F(β) : β < λ} to be a set — a completed collection you can hand to a function. Without Replacement, applying a definable function to all elements of a set might produce a proper class rather than a set. Replacement guarantees that if you apply a definable function to every element of a set, the image is also a set. This is what allows partial approximations at each stage to be assembled into a set for use at the next stage.

Question 3

Transfinite recursion requires three cases — base, successor, and limit — because ordinals come in three distinct kinds, unlike natural numbers which have only two.

• T. True
• F. False

Answer: True

Natural-number recursion has just two cases: base (n = 0) and successor (n + 1 in terms of n). Ordinals have a third kind: limit ordinals like ω, ω + ω, or ω₁ that have no immediate predecessor. The successor clause 'define F(α+1) in terms of F(α)' cannot apply at a limit ordinal because there is no α such that α + 1 = λ. This third clause — typically a supremum or union over all prior values — is the signature of every transfinite construction.

Question 4

Ordinal addition is commutative: α + β = β + α for most ordinals α and β.

• T. True
• F. False

Answer: False

Ordinal addition is not commutative. The canonical counterexample: 1 + ω = ω (we count 1, then continue through all natural numbers, giving an order-type isomorphic to ω), but ω + 1 ≠ ω (we count through all natural numbers, then add one more element at the end, which is a strictly larger ordinal). These are different ordinals, and the difference follows directly from the transfinite recursion definitions. Non-commutativity is one of the most surprising features of ordinal arithmetic.

Question 5

Explain why the definition of a transfinite recursion must include an explicit limit clause, rather than simply extending the successor clause to cover all ordinals.

Model answer: At a successor ordinal α+1, there is an immediate predecessor α, so we can define F(α+1) in terms of F(α). But at a limit ordinal λ (like ω), there is no immediate predecessor — no 'last' ordinal before λ. So 'one step beyond the previous value' has no meaning. The limit clause handles this by defining F(λ) as the supremum or union of all prior values {F(β) : β < λ}, which is well-defined even without a predecessor.

The existence of limit ordinals is what structurally distinguishes transfinite from ordinary recursion. Every transfinite construction — ordinal arithmetic, the cumulative hierarchy V_α, the aleph sequence — must explicitly handle limit stages, and the appropriate construction (sup or union) must be chosen to make the function well-defined and continuous in the appropriate sense. Without the limit clause, the recursion would produce a function defined only on successor ordinals, missing all limit ordinals entirely.