42.03.02 · mathematical-logic / set-theory-forcing

Ordinals, Transfinite Induction, and Recursion

shipped3 tiersLean: none

Anchor (Master): Kunen 2011 *Set Theory* (College Publications) Ch. I §9 (the Transfinite Recursion Theorem and the role of Replacement, the counting/isomorphism theorem, ordinal arithmetic and Cantor normal form); Jech 2003 *Set Theory* 3e (Springer) Ch. 2-3 (ordinal numbers, transfinite induction and recursion, ordinal arithmetic); Cantor 1897 *Math. Ann.* 49 (Beiträge II, the original ordinal theory)

Intuition Beginner

Counting is so familiar that it hides a deep idea: the numbers $1, 2, 3, \dots$ are not just sizes, they are positions. The third runner across the line, the fifth chapter, the tenth step. What makes positions work is that there is always a first one, and after any position there is a next one. Ordinal numbers are what you get when you take this positional idea of counting and let it run past every finite stage, into the infinite, without ever losing the "there is always a first one" rule.

To see why anyone needs this, picture an endless to-do list where every non-empty batch of tasks has a clear first task to do. You can work through the list one task at a time, and even after finishing infinitely many tasks you can ask: what comes next? The answer is a brand-new position sitting just beyond all the ones you finished. That new position is the first limit stage. Then counting resumes: one past it, two past it, and so on. Ordinals are the bookkeeping system for this kind of never-stuck, always-has-a-first counting.

The rule that powers everything is called being well-ordered: an arrangement where every non-empty group of items has a least item. Ordinary counting numbers are well-ordered. So is the counting that continues after infinity. This single property is what lets you do "induction" not just up the whole numbers but all the way up the infinite ladder, and what lets you build things step by step even when the steps never end.

In this unit you meet the ladder itself, the principle that lets you prove things rung by rung, and the principle that lets you define things rung by rung.

Visual Beginner

An ordinal is a position on a ladder that may climb past infinity. The ladder starts at the bottom, goes up one rung at a time, and at certain places it gathers up everything below into a new "limit" rung before continuing.

   ...                                    (it never stops)
    |
   omega + 2   <- two rungs past the first limit
    |
   omega + 1   <- one rung past the first limit
    |
   omega       <- the FIRST LIMIT rung: gathers up all of 0,1,2,3,...
   ::            (nothing sits just below it; it is the "next position
   ::             after every counting number at once")
    3
    |
    2
    |
    1
    |
    0           <- the bottom rung (nothing below it)

Read it from the bottom. Rungs $0, 1, 2, 3, \dots$ are the ordinary counting positions, each with a single next rung. The rung named $ω$ ("omega") is the first place that is not a "next" of anything — it is a limit, the position sitting just above the whole infinite run $0, 1, 2, \dots$ all at once. Above $ω$ counting starts again: $ω + 1, ω + 2, \dots$ , and far higher there are more limit rungs.

rung	kind	what sits just below it
$0$	bottom	nothing
$1$	next-of	$0$
$2$	next-of	$1$
$ω$	limit	all of $0, 1, 2, \dots$
$ω + 1$	next-of	$ω$

The key idea: every rung is exactly the collection of all the rungs below it. The bottom rung is the empty collection; the rung " $3$ " is the collection ${0, 1, 2}$ ; the rung " $ω$ " is the collection of every counting number. A rung is its own past.

Worked example Beginner

Let us build the bottom rungs by hand using one rule: each rung is the collection of all the rungs below it. We start with nothing and write ${}$ for the empty collection.

Step 1. The bottom rung $0$ has no rungs below it, so $0 = {}$ , the empty collection.

Step 2. The rung $1$ has exactly one rung below it, namely $0$ . So $1 = {0}$ , the collection whose single item is $0$ .

Step 3. The rung $2$ has two rungs below it, $0$ and $1$ . So $2 = {0, 1}$ .

Step 4. The rung $3$ has three rungs below it. So $3 = {0, 1, 2}$ .

Notice the pattern for getting the next rung: to go from $3$ to $4$ you keep all the rungs in $3$ and add $3$ itself as a new item. In symbols the next rung after $n$ is $n$ together with ${n}$ . So $4 = {0, 1, 2, 3}$ .

Step 5. Now jump to the first limit. The rung $ω$ is the collection of every counting rung at once: $ω = {0, 1, 2, 3, \dots}$ . It is not the "next" of any single rung, because for any counting number $n$ there is always a bigger counting number $n + 1$ still below $ω$ . So nothing sits immediately below $ω$ ; it gathers the whole infinite run.

Step 6. Past the limit, counting resumes. The next rung after $ω$ keeps everything in $ω$ and adds $ω$ itself: $ω + 1 = {0, 1, 2, \dots, ω}$ .

What this tells us: with the single rule "a rung is its own past," the counting numbers, the first infinite gathering point $ω$ , and the rungs beyond it all come from the same construction. The rungs are nested collections, and "smaller" just means "is a member of."

Check your understanding Beginner

Formal definition Intermediate+

All of the following takes place inside ZF (cross-ref 42.03.01); the only primitive is $\in$ , and orderings, functions, and the cumulative hierarchy are as developed there.

A well-ordering of a set $A$ is a linear order $<$ on $A$ in which every nonempty $X \subseteq A$ has a $<$ -least element. Equivalently, $<$ is a strict linear order with no infinite strictly descending sequence (these coincide under Choice; well-foundedness is the half that matters). An isomorphism of well-orders $(A, <_{A}) \to (B, <_{B})$ is an order-preserving bijection; an initial segment of $(A, <)$ is a set of the form $A_{a} = {x \in A : x < a}$ (a proper initial segment) or $A$ itself.

A set $x$ is transitive when every member of a member of $x$ is a member of $x$ , that is $⋃ x \subseteq x$ . An ordinal is a transitive set well-ordered by the membership relation $\in$ ^{[Kunen Ch. I §8]}. Write $On$ for the class of all ordinals. For ordinals one writes $β < α$ to mean $β \in α$ ; the basic structural facts are that each ordinal equals the set of its predecessors, $$ \alpha = {\beta \in \mathrm{On} : \beta < \alpha} = {\beta : \beta \in \alpha}, $$ that every element of an ordinal is an ordinal, and that $<$ linearly (indeed well-) orders $On$ . The successor of $α$ is $α + 1 := α \cup {α}$ , the least ordinal greater than $α$ . An ordinal $α \neq = 0$ is a successor ordinal if $α = β + 1$ for some $β$ , and a limit ordinal if it is neither $0$ nor a successor, equivalently $α = sup {β : β < α} = ⋃ α$ with $α \neq = 0$ . The finite ordinals are the von Neumann naturals $0 = \emptyset$ , $n + 1 = n \cup {n}$ , and $ω := {0, 1, 2, \dots}$ — guaranteed to be a set by the Axiom of Infinity — is the least limit ordinal.

The rank function and the levels $V_{α}$ of 42.03.01 are exactly the canonical application of the recursion principle proved below: $rank (x) = sup {rank (y) + 1 : y \in x}$ takes ordinal values, and $On$ is the order type of the well-ordered spine that indexes the cumulative hierarchy.

Counterexamples to common slips Intermediate+

"The integers $Z$ with their usual order are well-ordered." They are linearly ordered but not well-ordered: the whole set $Z$ has no least element, and ${- 1, - 2, - 3, \dots}$ descends forever. Well-ordering forbids exactly such infinite descent.
"Every limit ordinal is $ω$ ." $ω$ is the least limit ordinal, but $ω + ω = ω \cdot 2$ , $ω^{2}$ , and $ω^{ω}$ are larger limits. A limit is any nonzero ordinal that is not a successor; there are class-many of them.
" $On$ is a set because each ordinal is." If $On$ were a set it would be a transitive set well-ordered by $\in$ , hence an ordinal $Ω$ , giving $Ω \in Ω$ and contradicting $\in$ -well-foundedness. This is the Burali-Forti paradox; $On$ is a proper class.
"Ordinal addition is commutative because it generalises addition of naturals." It is not: $1 + ω = ω \neq = ω + 1$ . Prepending one element to an $ω$ -sequence still has order type $ω$ , while appending one element after all of $ω$ creates a new largest element. Commutativity holds only among finite ordinals.

Key theorem with proof Intermediate+

The organising theorem of the subject is that the von Neumann ordinals are a system of canonical representatives for well-orderings: every well-ordered set is isomorphic to exactly one ordinal. This is what makes "the order type" a well-defined object and what lets ordinals serve as the universal yardstick for transfinite length.

Theorem (the counting theorem; well-orders have unique ordinal types). Let $(A, <)$ be a well-ordered set. Then there is a unique ordinal $α$ and a unique isomorphism $f : (A, <) \to (α, \in)$ . The ordinal $α$ is the order type of $(A, <)$ , written $otp (A, <)$ ^{[Kunen Ch. I §9]}.

Proof. Uniqueness first. Suppose $f : A \to α$ and $g : A \to β$ are isomorphisms onto ordinals. Then $g \circ f^{- 1} : α \to β$ is an isomorphism of $(α, \in)$ onto $(β, \in)$ . An isomorphism between well-orders that fixes initial segments is forced to be the identity: by $\in$ -induction (proved in the next section) one shows $h (γ) = γ$ for every $γ \in α$ , since $h (γ)$ is the least ordinal exceeding all $h (δ) = δ$ for $δ < γ$ , namely $γ$ itself. Hence $α = β$ and the isomorphism, and so $f$ , is unique.

Existence. Define $f$ on $A$ by recursion along the well-order: set $$ f(a) = { f(b) : b \in A,\ b < a }, $$ so that $f (a)$ is the set of values already assigned to the strict predecessors of $a$ . The Transfinite Recursion Theorem (next section) supplies such an $f$ as a genuine function, using Replacement to collect the values ${f (b) : b < a}$ into a set at each stage. One checks by induction along $<$ that each $f (a)$ is an ordinal and that $a < a^{'}$ implies $f (a) \in f (a^{'})$ : if every $b < a$ has $f (b)$ an ordinal and $f$ order-preserving below $a$ , then $f (a) = {f (b) : b < a}$ is a transitive set of ordinals linearly ordered by $\in$ , hence an ordinal, and it strictly exceeds each $f (b)$ . The image $α := f [A] = {f (a) : a \in A}$ is a set by Replacement; it is a transitive set of ordinals (it contains every $f (b)$ with $b < a$ whenever it contains $f (a)$ ) and is therefore an ordinal, and $f : A \to α$ is the required isomorphism. $□$

Bridge. The counting theorem is the foundational reason ordinals exist as a separate notion at all: they are the isomorphism invariants of well-orderings, one ordinal per order type, and this is exactly what lets every later transfinite construction be indexed by an honest set-theoretic object. It builds toward the cardinals of 42.03.03, where a cardinal is singled out as the least ordinal of a given size — an idea that only makes sense once "the least well-ordering type" is pinned down here. The recursion used to build $f$ is the same machinery that defines rank and the levels $V_{α}$ in 42.03.01, so the construction of the ordinal index and the construction of the hierarchy it indexes are one recursion; putting these together, the central insight is that well-foundedness — every nonempty set has an $\in$ -minimal element — is simultaneously what licenses the recursion that produces $f$ and what guarantees the uniqueness of the resulting type. This appears again in the constructible hierarchy 42.03.06, whose levels $L_{α}$ are indexed by the very ordinals constructed here, and the well-ordering theorem 42.03.05 generalises the counting theorem from a given well-order to every set once Choice supplies a well-ordering to count along.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove that no ordinal is a member of itself, and conclude that $α + 1 = α \cup {α}$ is the least ordinal strictly greater than $α$ .

Hint

Use Foundation, or use that $(α, \in)$ is a strict order so $α \in / α$ . For minimality, any $γ > α$ has $α \in γ$ , so $α \cup {α} \subseteq γ$ .

Answer

Since $(α, \in)$ is a strict (irreflexive) linear order on the members of $α$ and, more strongly, $\in$ is well-founded by Foundation, $α \in / α$ for every ordinal $α$ (a one-step $\in$ -loop is forbidden). Now $α + 1 = α \cup {α}$ is transitive (members of $α$ are subsets of $α$ , and $α$ itself is a subset) and well-ordered by $\in$ , hence an ordinal, and $α \in α + 1$ so $α < α + 1$ . If $α < γ$ then $α \in γ$ and, by transitivity of $γ$ , $α \subseteq γ$ , so $α \cup {α} \subseteq γ$ , giving $α + 1 \leq γ$ . Thus $α + 1$ is the least ordinal exceeding $α$ . Rubric: full credit for $α \in / α$ from Foundation, ordinalhood of $α + 1$ , and the minimality inclusion.

Exercise 4 (medium, symbolic).

Prove the Comparison Theorem for ordinals: for ordinals $α, β$ exactly one of $α \in β$ , $α = β$ , $β \in α$ holds.

Hint

Show $γ := α \cap β$ is an ordinal and that $γ = α$ or $γ = β$ by ruling out $γ \in α$ and $γ \in β$ simultaneously.

Answer

At most one holds, since two of them together would give an $\in$ -cycle, forbidden by Foundation. For at least one: let $γ = α \cap β$ . It is transitive (intersection of transitive sets) and well-ordered by $\in$ (a subset of the ordinal $α$ ), hence an ordinal, and $γ \subseteq α$ , $γ \subseteq β$ . Suppose $γ \neq = α$ and $γ \neq = β$ . Then $γ ⊊ α$ , and since $α$ is an ordinal $γ \in α$ (a proper transitive subset of an ordinal is an element of it: $γ$ is the least element of $α ∖ γ$ ). Likewise $γ \in β$ . So $γ \in α \cap β = γ$ , contradicting $γ \in / γ$ . Hence $γ = α$ (giving $α \subseteq β$ , so $α \in β$ or $α = β$ ) or $γ = β$ (symmetrically). Rubric: full credit for $γ$ being an ordinal, the "proper transitive subset is an element" lemma, and the contradiction $γ \in γ$ .

Exercise 5 (medium, symbolic).

State and prove the principle of transfinite induction on $On$ : if $C$ is a class of ordinals such that whenever every $β < α$ is in $C$ then $α \in C$ , then $C$ contains every ordinal.

Hint

If some ordinal is not in $C$ , the set of non-members below a witness is nonempty; apply well-ordering of $\in$ .

Answer

Suppose the hypothesis holds but some ordinal $δ \in / C$ . The set $S = (δ + 1) ∖ C = {γ \leq δ : γ \in / C}$ is a nonempty set of ordinals ( $δ \in S$ ), so by well-ordering it has a $\in$ -least element $α$ . By minimality every $β < α$ is in $C$ . The hypothesis then forces $α \in C$ , contradicting $α \in S$ . Hence no such $δ$ exists and $C = On$ . The successor/limit split is the familiar packaging: it suffices to check $0 \in C$ , $α \in C \Rightarrow α + 1 \in C$ , and ( $λ$ limit, all $β < λ$ in $C$ ) $\Rightarrow λ \in C$ . Rubric: full credit for forming the nonempty failure set, applying well-ordering, and deriving the contradiction.

Exercise 6 (hard, symbolic).

Prove that ordinal multiplication is left-distributive over addition, $α \cdot (β + γ) = α \cdot β + α \cdot γ$ , but that right-distributivity can fail by exhibiting a counterexample.

Hint

Use the order-type reading: $α \cdot β$ is $β$ copies of $α$ in sequence. For the failure, evaluate $(ω + 1) \cdot 2$ against $ω \cdot 2 + 1 \cdot 2$ .

Answer

By transfinite induction on $γ$ (with $α \cdot β$ read as the order type of $β$ consecutive copies of $α$ ): for $γ = 0$ both sides are $α \cdot β$ ; at a successor, $α \cdot (β + (γ + 1)) = α \cdot ((β + γ) + 1) = α \cdot (β + γ) + α = (α \cdot β + α \cdot γ) + α = α \cdot β + α \cdot (γ + 1)$ ; at limits both sides are the sup of the lower values by left-continuity of $+$ and $\cdot$ in the right argument. Right-distributivity fails: $(ω + 1) \cdot 2 = (ω + 1) + (ω + 1) = ω + (1 + ω) + 1 = ω + ω + 1 = ω \cdot 2 + 1$ , whereas $ω \cdot 2 + 1 \cdot 2 = ω \cdot 2 + 2$ . Since $ω \cdot 2 + 1 \neq = ω \cdot 2 + 2$ , $(ω + 1) \cdot 2 \neq = ω \cdot 2 + 1 \cdot 2$ . Rubric: full credit for the inductive left-distributive proof (all three cases) and a correctly computed right-distributive counterexample.

Exercise 7 (hard, symbolic).

Prove existence and uniqueness of the Cantor Normal Form: every ordinal $α > 0$ has a unique representation $α = ω^{β_{1}} k_{1} + \dots + ω^{β_{n}} k_{n}$ with $β_{1} > \dots > β_{n}$ ordinals and $k_{i}$ nonzero natural numbers.

Hint

For existence, let $β_{1}$ be the largest $β$ with $ω^{β} \leq α$ and divide with remainder: $α = ω^{β_{1}} k_{1} + ρ$ with $ρ < ω^{β_{1}}$ . Recurse on $ρ$ .

Answer

Existence by transfinite induction on $α$ . There is a largest ordinal $β_{1}$ with $ω^{β_{1}} \leq α$ (the function $β \mapsto ω^{β}$ is strictly increasing and continuous, and $ω^{α} \geq α \geq α$ , so the set ${β : ω^{β} \leq α}$ is bounded and has a maximum). By the ordinal division algorithm write $α = ω^{β_{1}} k_{1} + ρ$ with $k_{1} \geq 1$ finite and $ρ < ω^{β_{1}}$ ; finiteness of $k_{1}$ holds because $ω^{β_{1}} \cdot ω = ω^{β_{1} + 1} > α$ . Since $ρ < α$ , induction gives $ρ$ a normal form whose leading exponent is $< β_{1}$ (as $ρ < ω^{β_{1}}$ ), and concatenation yields the form for $α$ . Uniqueness: the leading term $ω^{β_{1}} k_{1}$ is determined because $ω^{β_{1}} k_{1} \leq α < ω^{β_{1}} (k_{1} + 1) \leq ω^{β_{1} + 1}$ pins $β_{1}$ as the largest exponent and $k_{1}$ as the unique multiplicity; subtract and recurse on the strictly smaller remainder. Rubric: full credit for the maximal-exponent argument, the bounded multiplicity, and the uniqueness via the inequality pinning $(β_{1}, k_{1})$ .

Advanced results Master

The recursion theorem is the engine; the arithmetic and the normal form are its first substantial outputs, and the proper-class character of $On$ is the boundary condition every construction must respect.

Theorem 1 (Transfinite Recursion on $On$ ). Let $G$ be a class function defined on all sets. There is a unique class function $F : On \to V$ such that for every ordinal $α$ , $$ F(\alpha) = G\big( F \restriction \alpha \big), $$ where $F ↾ α = {(β, F (β)) : β < α}$ ^{[Kunen Ch. I §9]}. The proof constructs, for each $α$ , the unique function $f_{α}$ on $α$ obeying the recursion below $α$ : the class of " $α$ -approximations" is shown nonempty and pairwise-compatible by transfinite induction, so $F := ⋃_{α} f_{α}$ is a well-defined class function. The single use of Replacement is decisive — to know $F ↾ α$ is a set (so that $G$ can be applied to it) one collects the set-many values ${F (β) : β < α}$ as the image of $α$ under the class function $F$ ; without Replacement the recursion does not close, which is why ordinal arithmetic, rank, and $L$ all require the full schema rather than Separation alone.

Theorem 2 (ordinal arithmetic by recursion). Addition, multiplication, and exponentiation are defined for each fixed $α$ by recursion on the second argument ^{[Jech Ch. 3]}: $$ \alpha + 0 = \alpha,\quad \alpha + (\beta+1) = (\alpha+\beta)+1,\quad \alpha + \lambda = \sup_{\beta<\lambda}(\alpha + \beta); $$ $$ \alpha \cdot 0 = 0,\quad \alpha\cdot(\beta+1) = \alpha\cdot\beta + \alpha,\quad \alpha\cdot\lambda = \sup_{\beta<\lambda}\alpha\cdot\beta; $$ $$ \alpha^0 = 1,\quad \alpha^{\beta+1} = \alpha^\beta\cdot\alpha,\quad \alpha^\lambda = \sup_{\beta<\lambda}\alpha^\beta\ (\alpha>0). $$ Each operation is associative, strictly increasing and continuous in its right argument, and weakly monotone in its left; none is commutative beyond the finite ordinals. The order-theoretic readings agree: $α + β$ is the order type of a copy of $α$ followed by a copy of $β$ , and $α \cdot β$ is the order type of $β$ lexicographically-ordered copies of $α$ . The asymmetry $1 + ω = ω \neq = ω + 1$ and $2 \cdot ω = ω \neq = ω \cdot 2$ is the signature of left-recursion against right-continuity.

Theorem 3 (Cantor Normal Form). Every $α > 0$ is uniquely $α = ω^{β_{1}} k_{1} + \dots + ω^{β_{n}} k_{n}$ with $β_{1} > \dots > β_{n}$ and $0 < k_{i} < ω$ ^{[Cantor 1897]}. The form turns ordinal arithmetic below $ε_{0}$ into a symbolic calculus on finite expressions, and the least ordinal not nameable this way from below is the first $ε$ -number $ε_{0} = ω^{ω^{ω^{\dots}}}$ , the supremum of $ω, ω^{ω}, ω^{ω^{ω}}, \dots$ and the least fixed point of $ξ \mapsto ω^{ξ}$ . Goodstein's theorem and the proof-theoretic strength of Peano arithmetic both hinge on this representation.

Theorem 4 (Burali-Forti). $On$ is a proper class ^{[Kunen Ch. I §8]}. Were $On$ a set, it would be transitive (every member of an ordinal is an ordinal) and well-ordered by $\in$ (the comparison theorem), hence itself an ordinal $Ω$ , whence $Ω \in On = Ω$ , an $\in$ -membership of a set in itself forbidden by Foundation. The same obstruction reappears for the class of cardinals and underlies why the cumulative hierarchy $V = ⋃_{α} V_{α}$ of 42.03.01 is a proper-class union indexed by the proper class $On$ .

Synthesis. The foundational reason ordinals organise the infinite is that well-foundedness of $\in$ — inherited from Foundation in 42.03.01 — is at once the hypothesis of transfinite induction and the input to transfinite recursion, two principles dual to the single fact that every nonempty class of ordinals has a least element: induction reads it as "no minimal counterexample," recursion as "every stage is determined by the completed earlier stages." This is exactly what the counting theorem exploits, assigning each well-order its unique ordinal type, and the Transfinite Recursion Theorem makes that assignment, ordinal arithmetic, rank, and the constructible levels $L_{α}$ legitimate definitions rather than informal recipes — the indispensable ingredient being Replacement, which collects each $F ↾ α$ into a set so the recursion closes. Putting these together, the ordinals are simultaneously the index set that climbs the cumulative hierarchy and the order types living inside it, and Burali-Forti is the boundary the picture respects: the indices form a proper class because any set of all of them would be an ordinal exceeding itself. The bridge forward is that cardinals 42.03.03 are distinguished ordinals (least of their cardinality), the well-ordering theorem 42.03.05 extends counting from a given well-order to every set, and the constructible universe 42.03.06 is the recursion of this unit run with the definable power set in place of the full one — each a controlled use of the ordinal recursion established here.

Full proof set Master

Proposition 1 (members and transitive subsets of ordinals). Every member of an ordinal is an ordinal, and every transitive proper subset $S ⊊ α$ of an ordinal is a member of $α$ ; in particular $α = {β \in On : β < α}$ .

Proof. Let $α$ be an ordinal and $β \in α$ . Since $α$ is transitive, $β \subseteq α$ , so $β$ is well-ordered by $\in$ (a subset of the $\in$ -well-order on $α$ ). For transitivity of $β$ : if $γ \in δ \in β$ then $γ, δ \in α$ , and $\in$ restricted to $α$ is a transitive relation (it linearly orders $α$ ), so $γ \in β$ . Hence $β$ is an ordinal. Now let $S ⊊ α$ be transitive. The set $α ∖ S$ is nonempty; let $μ$ be its $\in$ -least element. Then $μ \subseteq S$ : any $ν \in μ$ lies in $α$ (transitivity of $α$ ) and $ν < μ$ , so $ν \in / α ∖ S$ by minimality, i.e. $ν \in S$ . Conversely $S \subseteq μ$ : if some $σ \in S$ had $σ \in / μ$ then by comparison $μ \in σ$ or $μ = σ$ , and transitivity of $S$ would put $μ \in S$ , contradicting $μ \in α ∖ S$ . Thus $S = μ \in α$ . The displayed identity is the case $S = β$ . $□$

Proposition 2 (transfinite induction on a well-order). Let $(A, <)$ be well-ordered and $φ$ a property such that for all $a \in A$ , $(\forall b < a φ (b)) \to φ (a)$ . Then $φ (a)$ holds for all $a \in A$ .

Proof. Let $X = {a \in A : \neg φ (a)}$ , a subset of $A$ by Separation. If $X \neq = \emptyset$ , well-ordering gives a $<$ -least $a_{0} \in X$ . Every $b < a_{0}$ satisfies $b \in / X$ , i.e. $φ (b)$ ; the hypothesis then yields $φ (a_{0})$ , contradicting $a_{0} \in X$ . Hence $X = \emptyset$ . The case $A = α$ an ordinal with $< = \in$ is induction on $On$ relativised below $α$ , and the global form on $On$ follows by applying this to the well-order $(δ + 1, \in)$ for an arbitrary witness $δ$ . $□$

Proposition 3 (uniqueness in transfinite recursion). With $G$ as in Theorem 1, any two class functions $F_{1}, F_{2} : On \to V$ satisfying $F_{i} (α) = G (F_{i} ↾ α)$ for all $α$ coincide.

Proof. By transfinite induction on $α$ (Proposition 2 on $On$ ). Suppose $F_{1} (β) = F_{2} (β)$ for all $β < α$ . Then $F_{1} ↾ α = F_{2} ↾ α$ as sets of ordered pairs, so $F_{1} (α) = G (F_{1} ↾ α) = G (F_{2} ↾ α) = F_{2} (α)$ . Hence the agreement set is all of $On$ . $□$

Proposition 4 (existence in transfinite recursion). With $G$ as in Theorem 1, a class function $F$ satisfying the recursion exists.

Proof. Call a function $f$ with domain an ordinal $δ$ an approximation if $f (β) = G (f ↾ β)$ for all $β < δ$ . Any two approximations agree on the smaller of their domains, by the induction of Proposition 3 applied below that domain. For each $α$ there is an approximation with domain $α + 1$ : by induction on $α$ , if approximations $f_{β}$ with domain $β + 1$ exist for all $β < α$ , their union $g$ is an approximation with domain $α$ (Replacement guarantees $g$ — equivalently $g = {(β, f_{β} (β)) : β < α}$ , the image of $α$ under a class function — is a set), and extending $g$ by $g (α) := G (g)$ gives domain $α + 1$ . Define $F (α)$ as the common value $f (α)$ for any approximation $f$ whose domain contains $α$ ; this is well-defined by compatibility and satisfies $F (α) = G (F ↾ α)$ since $F ↾ α = f ↾ α$ for a suitable approximation $f$ . The set-hood of $F ↾ α$ at each step is precisely the Replacement step. $□$

Proposition 5 (left absorption $1 + ω = ω$ , with the general pattern). For every $n < ω$ , $n + ω = ω$ , while $ω + n \neq = ω$ for $n > 0$ ; hence ordinal addition is not commutative.

Proof. By the recursion for $+$ in the right argument, $n + ω = sup_{k < ω} (n + k)$ . Each $n + k$ is the finite ordinal $n + k < ω$ , and as $k$ ranges over $ω$ the values $n + k$ are cofinal in $ω$ , so the supremum is $ω$ ; thus $n + ω = ω$ . On the other side $ω + n$ is computed by the successor clause: $ω + 1 = ω \cup {ω}$ has $ω$ as a member and hence a largest element, so $ω + 1 \neq = ω$ , and inductively $ω + n$ for $n > 0$ has exactly $n$ elements above the copy of $ω$ , so $ω + n \neq = ω$ . With $n = 1$ this is $1 + ω = ω \neq = ω + 1$ . $□$

Connections Master

Cardinals and cardinal arithmetic 42.03.03 are built directly on this unit: a cardinal is defined as an initial ordinal, the least ordinal of a given cardinality, so the entire theory of $ℵ$ -numbers presupposes that every well-orderable set has a unique ordinal type (the counting theorem proved here) and that the ordinals are well-ordered so a least one exists. The foundational reason cardinal arithmetic diverges from ordinal arithmetic — $ℵ_{0} + ℵ_{0} = ℵ_{0}$ but $ω + ω \neq = ω$ — is exactly that cardinal operations collapse to the underlying-set size while ordinal operations remember order type; this unit owns the order-type layer, 42.03.03 owns the cardinality collapse.
The Axiom of Choice and the Well-Ordering Theorem 42.03.05 complete the picture by guaranteeing that every set, not merely the manifestly well-orderable ones, carries a well-ordering and hence an ordinal length; the counting theorem of this unit then assigns each set an ordinal, which is what makes cardinal assignment total. Zorn's lemma and transfinite recursion combine in the standard well-ordering proof: one enumerates a set along $On$ by recursion using a choice function, and the recursion theorem proved here is the precise instrument that licenses that enumeration.
The constructible universe $L$ 42.03.06 is the von Neumann recursion of this unit run with the definable power set $Def (\cdot)$ in place of the full $P (\cdot)$ : $L_{0} = \emptyset$ , $L_{α + 1} = Def (L_{α})$ , $L_{λ} = ⋃_{α < λ} L_{α}$ , indexed by the ordinals constructed here, with $L = ⋃_{α \in On} L_{α}$ . Transfinite recursion on $On$ is what defines the $L_{α}$ hierarchy, and the canonical well-ordering of $L$ — the source of " $V = L$ implies AC and GCH" — is itself defined by recursion along the ordinal index, making this unit the recursion-theoretic foundation of the inner-model theory in 42.03.06.

Historical & philosophical context Master

Transfinite ordinals originate with Georg Cantor, who arrived at them through the analysis of point sets: iterating the Cantor-Bendixson derivative of a closed set produces a descending sequence indexed first by the natural numbers and then past them, and naming the index $ω, ω + 1, \dots$ forced the invention of the transfinite. Cantor's 1883 Grundlagen einer allgemeinen Mannigfaltigkeitslehre introduced the ordinals via two "generating principles" (take the successor; take the limit of an increasing sequence), and his 1897 Beiträge zur Begründung der transfiniten Mengenlehre II ^{[Cantor 1897]} gave the mature order-type theory, the comparison theorem for well-ordered sets, the non-commutative arithmetic with his explicit $ω + 1 \neq = 1 + ω$ , and the normal-form representation in powers of $ω$ .

Cesare Burali-Forti published in 1897 the paradox now bearing his name — the order type of all ordinals would exceed itself — which, alongside Russell's, sharpened the need for axiomatisation. The decisive set-theoretic recasting is due to John von Neumann, whose 1923 note Zur Einführung der transfiniten Zahlen and 1928 Die Axiomatisierung der Mengenlehre defined an ordinal as a transitive set well-ordered by membership, making $α = {β : β < α}$ a definition rather than a picture; von Neumann also proved the general transfinite recursion theorem and identified the role of Replacement, the axiom Fraenkel and Skolem had added to Zermelo's system precisely to legitimate such recursions. The standard modern developments are Kunen's ^{[Kunen Ch. I §9]} and Jech's ^{[Jech Ch. 2]}, from which the present treatment of recursion, arithmetic, and Cantor normal form is drawn.

Bibliography Master

@book{kunen2011set,
  author    = {Kunen, Kenneth},
  title     = {Set Theory},
  series    = {Studies in Logic},
  volume    = {34},
  publisher = {College Publications},
  year      = {2011}
}

@book{jech2003set,
  author    = {Jech, Thomas},
  title     = {Set Theory},
  edition   = {3},
  series    = {Springer Monographs in Mathematics},
  publisher = {Springer},
  year      = {2003}
}

@article{cantor1897beitraege,
  author  = {Cantor, Georg},
  title   = {Beitr{\"a}ge zur Begr{\"u}ndung der transfiniten Mengenlehre II},
  journal = {Mathematische Annalen},
  volume  = {49},
  year    = {1897},
  pages   = {207--246}
}

@article{cantor1883grundlagen,
  author  = {Cantor, Georg},
  title   = {{\"U}ber unendliche, lineare Punktmannigfaltigkeiten V (Grundlagen einer allgemeinen Mannigfaltigkeitslehre)},
  journal = {Mathematische Annalen},
  volume  = {21},
  year    = {1883},
  pages   = {545--591}
}

@article{buraliforti1897questione,
  author  = {Burali-Forti, Cesare},
  title   = {Una questione sui numeri transfiniti},
  journal = {Rendiconti del Circolo Matematico di Palermo},
  volume  = {11},
  year    = {1897},
  pages   = {154--164}
}

@article{vonneumann1923einfuehrung,
  author  = {von Neumann, John},
  title   = {Zur Einf{\"u}hrung der transfiniten Zahlen},
  journal = {Acta Litterarum ac Scientiarum (Szeged)},
  volume  = {1},
  year    = {1923},
  pages   = {199--208}
}

@article{vonneumann1928axiomatisierung,
  author  = {von Neumann, John},
  title   = {Die Axiomatisierung der Mengenlehre},
  journal = {Mathematische Zeitschrift},
  volume  = {27},
  year    = {1928},
  pages   = {669--752}
}

Prerequisites

42.03.01

Tier anchors

beginner: Halmos 1960 *Naive Set Theory* (Van Nostrand) §17-19 (well-ordering, the counting picture, ordinals read by hand); Enderton 1977 *Elements of Set Theory* (Academic Press) Ch. 7 (well orderings and ordinals for the informal first pass)
intermediate: Kunen 2011 *Set Theory* (College Publications) Ch. I §7-9 (well-orderings, the comparison theorem, the von Neumann ordinals as transitive ∈-well-ordered sets, successor and limit ordinals, ω, Burali-Forti) and §9 (transfinite induction on a well-order and on On)
master: Kunen 2011 *Set Theory* (College Publications) Ch. I §9 (the Transfinite Recursion Theorem and the role of Replacement, the counting/isomorphism theorem, ordinal arithmetic and Cantor normal form); Jech 2003 *Set Theory* 3e (Springer) Ch. 2-3 (ordinal numbers, transfinite induction and recursion, ordinal arithmetic); Cantor 1897 *Math. Ann.* 49 (Beiträge II, the original ordinal theory)

References

Kunen, K. — Set Theory · College Publications, Studies in Logic 34 (2011, revised edition). Chapter I §7-9 develops the theory of well-orderings and ordinals: §7 defines a well-ordering as a linear order in which every nonempty subset has a least element and proves the Comparison Theorem that any two well-ordered sets are comparable (one is isomorphic to an initial segment of the other) with the isomorphism unique; §8 introduces the von Neumann ordinals as the transitive sets well-ordered by ∈, proves α = {β : β < α}, develops successor ordinals α+1 = α ∪ {α} and limit ordinals, identifies ω as the least limit ordinal (the natural numbers under the von Neumann coding), and proves the Burali-Forti theorem that the class On of all ordinals is not a set; §9 states and proves the Transfinite Induction principle (on On and on any well-order) and the Transfinite Recursion Theorem (a class function defined by recursion along ∈ on On exists and is unique), pinpointing the use of the Replacement schema to collect the recursively defined values into a set, proves that every well-ordered set is isomorphic to a unique ordinal (the counting theorem giving its order type), and defines ordinal addition, multiplication, and exponentiation by transfinite recursion, deriving non-commutativity (1+ω = ω ≠ ω+1, 2·ω = ω ≠ ω·2) and the Cantor Normal Form, the unique base-ω representation of an ordinal as a finite descending sum ω^{β_1}·k_1 + ⋯ + ω^{β_n}·k_n.
Jech, T. — Set Theory · Springer Monographs in Mathematics, 3rd millennium edition (2003). Chapter 2 develops ordinal numbers: well-orderings, the von Neumann ordinals as transitive sets well-ordered by membership, successor and limit ordinals, the natural numbers and ω, the theorem that every well-ordered set has a unique order type (is isomorphic to exactly one ordinal), the proof that On is a proper class (Burali-Forti), and the transfinite-induction and transfinite-recursion theorems with the explicit role of Replacement; Chapter 3 develops ordinal arithmetic (addition, multiplication, exponentiation by recursion, their associativity, left-continuity and monotonicity, the failure of commutativity), the Cantor Normal Form theorem, and ε-numbers (fixed points of ω^x); the rank function and the von Neumann hierarchy V_α are revisited as the canonical application of ordinal recursion.
Cantor, G. — Beiträge zur Begründung der transfiniten Mengenlehre II · *Mathematische Annalen* 49 (1897), 207-246. Cantor's second Beiträge memoir introduces the order types of well-ordered sets (his *Anzahlen*, the transfinite ordinal numbers), proves that the well-ordered sets are comparable, develops the arithmetic of ordinals — addition and multiplication defined order-theoretically, with the explicit observation that they are non-commutative (his ω+1 ≠ 1+ω) — and states the normal-form representation in powers of ω; this is the historical source of the ordinal theory that von Neumann later recast set-theoretically as the transitive ∈-well-ordered sets.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m