Transfinite Induction and Recursion

Ordinary proof by induction is a line of dominoes: knock over 0, show each domino topples the next, and every natural number falls. But the ordinals reach past \omega — and there is no single domino sitting just before \omega to knock it over. Transfinite induction repairs this with one extra move: a special rule for the limit ordinals, the places you can only reach "all at once."

Let P(\alpha) be a property of ordinals. If whenever P(\beta) holds for all \beta < \alpha it follows that P(\alpha) holds, then P(\alpha) holds for every ordinal \alpha.
In practice this splits into three cases: the base P(0); the successor step P(\alpha) \Rightarrow P(\alpha+1); and the limit step — if P(\beta) for all \beta < \lambda then P(\lambda), at each limit \lambda.

Why it must work: no infinite descent

The principle is guaranteed by the very definition of well-ordering. Suppose P failed somewhere. Then the set of counterexamples — ordinals where P is false — is non-empty, so (the ordinals being well-ordered) it has a least member \alpha_0. But then P(\beta) holds for every \beta < \alpha_0 (those are smaller than the least counterexample), and the hypothesis forces P(\alpha_0) to hold too — contradicting that it was a counterexample. So there are no counterexamples. It is exactly the "least counterexample" argument, now running along the whole ordinal line.

Watch the wave of "proved" sweep up the staircase — through the finite steps, across the limit \omega, and onward:

Transfinite recursion: defining, not just proving

Its twin is transfinite recursion — the tool for defining a function on all ordinals. You specify a value in three matching cases, and recursion guarantees a unique function F exists:

Base: give F(0).
Successor: give F(\alpha+1) in terms of F(\alpha).
Limit: for a limit \lambda, give F(\lambda) from all earlier values — usually the union or supremum F(\lambda) = \bigcup_{\beta < \lambda} F(\beta).

This is how ordinal addition, multiplication, the cumulative hierarchy V_\alpha, and the aleph function \aleph_\alpha are all built. For example, ordinal addition \alpha + \beta is recursion on \beta:

\alpha + 0 = \alpha,\qquad \alpha + (\beta+1) = (\alpha+\beta)+1,\qquad \alpha + \lambda = \bigcup_{\beta<\lambda}(\alpha+\beta).

// Recursion on a well-founded order: rank(x) = sup of (rank(child)+1) over children. // The empty node gets rank 0; the limit/union case is the max over all children. type Node = { name: string; children: Node[] }; function rank(n: Node): number { if (n.children.length === 0) return 0; // base return Math.max(...n.children.map((c) => rank(c) + 1)); // successor/sup step } const leaf = (name: string): Node => ({ name, children: [] }); const tree: Node = { name: "root", children: [leaf("a"), { name: "b", children: [leaf("c")] }] }; console.log("rank(root) = " + rank(tree)); // 0 -> a:0, c:0 -> b:1 -> root:2

Try proving "\alpha is finite" by induction — it sails through the base and successor steps (0 is finite; if \alpha is finite so is \alpha+1) yet is false, because the limit step fails: each finite ordinal below \omega is finite, but their union \omega is not. That broken limit step is not a nuisance — it is the whole reason transfinite induction has a third case. Ordinary induction never notices, because \mathbb{N} has no limit ordinals below \omega.

Don't forget the limit case. A "proof by transfinite induction" that only checks base and successor is incomplete — it can prove false things (like "every ordinal is finite"). The limit ordinals need their own argument.
The hypothesis is 'for all $\beta < \alpha$', not just $\alpha-1$. At a limit there is no \alpha-1 to lean on, so transfinite induction is inherently strong (complete) induction: you assume P for every smaller ordinal at once.