Transfinite Induction and Ordinal Arithmetic

Transfinite methods extend finite counting and induction to the infinite, using ordinals as the foundation for recursive constructions that go "beyond omega."

Ordinal Exponentiation in Detail

Definition7.1Ordinal exponentiation (set-theoretic)

For ordinals $\alpha, \beta$ with $\alpha > 0$ , the set $\alpha^\beta$ can be defined set-theoretically as the order type of the set of functions $f: \beta \to \alpha$ with finite support (i.e., $f(\gamma) \neq 0$ for finitely many $\gamma$ ), ordered anti-lexicographically: $f < g$ iff at the largest $\gamma$ where $f$ and $g$ differ, $f(\gamma) < g(\gamma)$ .

This agrees with the recursive definition: $\alpha^0 = 1$ , $\alpha^{\beta+1} = \alpha^\beta \cdot \alpha$ , and $\alpha^\lambda = \sup_{\beta < \lambda}\alpha^\beta$ for limit $\lambda$ .

ExampleOrdinal exponentiation examples

$2^\omega = \omega$ : The functions $f: \omega \to 2$ with finite support form a countable set isomorphic to the binary representations of natural numbers.
$\omega^\omega$ : The order type of the set of "polynomials" $n_k\omega^k + \cdots + n_1\omega + n_0$ with natural number coefficients.
$\omega^{\omega^\omega}$ : Beyond Cantor normal form with finitely many terms.
$\varepsilon_0 = \omega^{\omega^{\omega^{\cdot^{\cdot^{\cdot}}}}}$ : The first ordinal satisfying $\omega^\alpha = \alpha$ .

Fixed Points and Normal Functions

Definition7.2Normal function

A function $f: \mathbf{Ord} \to \mathbf{Ord}$ is normal (or continuous and strictly increasing) if:

$\alpha < \beta \implies f(\alpha) < f(\beta)$ (strictly increasing).
$f(\lambda) = \sup_{\alpha < \lambda} f(\alpha)$ for all limit ordinals $\lambda$ (continuous).

Theorem7.1Fixed-point theorem for normal functions

Every normal function $f: \mathbf{Ord} \to \mathbf{Ord}$ has a proper class of fixed points. The least fixed point is $\sup\{f^n(0) : n < \omega\}$ , where $f^n$ denotes $n$ -fold iteration.

ExampleFixed-point hierarchies

$f(\alpha) = \omega^\alpha$ : fixed points are the epsilon numbers $\varepsilon_0, \varepsilon_1, \ldots$
$f(\alpha) = \aleph_\alpha$ : fixed points are the $\aleph$ -fixed points $\alpha = \aleph_\alpha$ .
$f(\alpha) = \beth_\alpha$ : fixed points are the beth fixed points $\alpha = \beth_\alpha$ .

The function $\alpha \mapsto \varepsilon_\alpha$ is itself normal, so it has fixed points: ordinals $\alpha$ with $\varepsilon_\alpha = \alpha$ . These are called strongly critical ordinals.

Veblen Hierarchy

RemarkThe Veblen hierarchy

The Veblen functions $\varphi_\beta$ are defined by:

$\varphi_0(\alpha) = \omega^\alpha$ .
$\varphi_{\beta+1}$ enumerates the fixed points of $\varphi_\beta$ .
$\varphi_\lambda(\alpha) =$ the $\alpha$ -th common fixed point of all $\varphi_\beta$ for $\beta < \lambda$ .

The ordinal $\Gamma_0 = \varphi_{\Gamma_0}(0)$ (the Feferman-Schutte ordinal) is the first ordinal not reachable by the Veblen hierarchy from below. It plays a central role in proof theory as the proof-theoretic ordinal of ATR $_0$ .