Transfinite Induction and Recursion on Ordinals

Transfinite induction extends mathematical induction to all ordinals, and transfinite recursion extends recursive definitions beyond the natural numbers.

Transfinite Induction

Theorem4.3Principle of transfinite induction

Let $P(\alpha)$ be a property of ordinals. If:

Base case: $P(0)$ holds,
Successor step: $P(\alpha) \implies P(\alpha + 1)$ for all ordinals $\alpha$ ,
Limit step: If $P(\beta)$ holds for all $\beta < \lambda$ (where $\lambda$ is a limit ordinal), then $P(\lambda)$ holds,

then $P(\alpha)$ holds for all ordinals $\alpha$ .

Proof

Suppose $P(\alpha)$ fails for some ordinal $\alpha$ . Then the class $C = \{\alpha : \neg P(\alpha)\}$ is nonempty. Since every set of ordinals is well-ordered, $C$ has a least element $\alpha_0$ .

$\alpha_0 \neq 0$ (by the base case).
$\alpha_0$ is not a successor $\beta + 1$ (otherwise $P(\beta)$ holds by minimality, so $P(\beta + 1)$ holds by the successor step, contradicting $\alpha_0 \in C$ ).
$\alpha_0$ is not a limit ordinal (otherwise $P(\beta)$ holds for all $\beta < \alpha_0$ by minimality, so $P(\alpha_0)$ holds by the limit step).

Every ordinal is $0$ , a successor, or a limit, so we have a contradiction. $\blacksquare$

■

Transfinite Recursion

Theorem4.4Transfinite recursion theorem

Let $G: V \to V$ be a class function (where $V$ denotes the universe of sets). Then there exists a unique class function $F: \mathbf{Ord} \to V$ such that:

$F(\alpha) = G(F \restriction \alpha) \quad \text{for all ordinals } \alpha,$

where $F \restriction \alpha$ denotes the restriction of $F$ to $\{\beta : \beta < \alpha\}$ .

ExampleDefinitions by transfinite recursion

Ordinal addition $\alpha + \beta$ is defined by transfinite recursion on $\beta$ with the three clauses (zero, successor, limit).
Von Neumann hierarchy (cumulative hierarchy):
- $V_0 = \emptyset$ ,
- $V_{\alpha+1} = \mathcal{P}(V_\alpha)$ ,
- $V_\lambda = \bigcup_{\beta < \lambda} V_\beta$ for limit $\lambda$ .
Then $V = \bigcup_{\alpha \in \mathbf{Ord}} V_\alpha$ (the axiom of foundation is equivalent to this).
Aleph sequence: $\aleph_0 = \omega$ , $\aleph_{\alpha+1} = \aleph_\alpha^+$ (the next cardinal), $\aleph_\lambda = \sup_{\beta < \lambda}\aleph_\beta$ .

Applications

RemarkEpsilon numbers

The epsilon numbers are ordinals $\varepsilon$ satisfying $\omega^\varepsilon = \varepsilon$ . By transfinite recursion: $\varepsilon_0 = \sup\{\omega, \omega^\omega, \omega^{\omega^\omega}, \ldots\}$ , $\varepsilon_1 = \sup\{\varepsilon_0 + 1, \omega^{\varepsilon_0 + 1}, \ldots\}$ , and in general $\varepsilon_{\alpha+1}$ is the next epsilon number after $\varepsilon_\alpha$ . The epsilon numbers form a proper class.

ExampleThe cumulative hierarchy

$V_0 = \emptyset$ , $V_1 = \{\emptyset\}$ , $V_2 = \{\emptyset, \{\emptyset\}\}$ , $V_3$ has $4$ elements, $V_n$ has $\beth_n = 2^{\beth_{n-1}}$ elements.
$V_\omega = \bigcup_{n < \omega} V_n$ contains all hereditarily finite sets and is a model of ZFC minus the axiom of infinity.
$V_{\omega+\omega}$ contains sets of every finite rank over $V_\omega$ .

The rank function $\rho(x) = \min\{\alpha : x \in V_{\alpha+1}\}$ assigns an ordinal rank to every set.