Induction and recursion on ordinals

1. Introduction

We have seen that ordinals are either zero, a successor, or a limit, and are based on $\in$ which is well-founded and has induction and recursion principles. Therefore there are induction and recursion principles on ordinals, which are essentially just special cases of $\in$ -induction and recursion. This web page states these principles: the proofs are the same as for $\in$ -induction and recursion. Examples will be given later.

As elsewhere, $α, β, γ, δ, \dots$ etc. and $λ, μ, \dots$ range over ordinals with $λ, μ, \dots$ being reserved for limit ordinals.

2. Induction on ordinals

Theorem.

Suppose $ϕ (x)$ is a first order formula and

$ϕ (0)$
$\forall α (ϕ (α) \to ϕ (α + 1))$
$\forall λ ((\forall α \in λ ϕ (α)) \to ϕ (λ))$

Then for all ordinals $α$ we have $ϕ (α)$ .

Remark: in the above, and everywhere in these notes, $λ$ is thought of as a limit ordinal. However the third case includes the first for $λ = 0$ and the second for $λ = α + 1$ so strictly speaking the first two cases are redundant.

3. Recursion on ordinals

Theorem.

Suppose $G (x, y), H (x, y)$ are class functions defined on ordinals alpha and $G$ is defined by

$F (0) = F_{0}$
$\forall α F (α + 1) = G (α, F (α))$
$\forall λ F (λ) = H (λ, \{F (α): α \in λ\})$

Then there is a class function $F$ defined as above, uniform in any parameters in $G, H$ .

4. Ordinals and well-founded sets

There are similar induction and recursion theorems on any well-founded relation. A well-order is a particular kind of well-founded relation closely related to ordinals.

Note: some of the following will be moved to somewhere more appropriate in the future.

Definition.

A binary relation, $R$ , is well-founded if $\forall z (z \neq \emptyset \to \exists y \in z \forall x (x \in z \to \neg R (x, y)))$ . A set $r \subseteq x \times x$ is well-founded if the relation $(u, v) \in r$ is well-founded. The relation $R$ is local if $\forall y \exists z \forall x (x \in z \leftrightarrow R (x, y))$ .

A set $x$ is called a well-founded set if the set membership relation is well-founded on the transitive closure of $x$ .

Definition.

A well-order $<$ on a set $X$ is a linear order such that for all nonempty $Y \subseteq X$ there is a $<$ -least element of $Y$ .

Theorem.

If $(X, <)$ is a well-ordered set there is a unique ordinal $α$ such that $(X, <)$ is order-isomorphic to $(α, \in)$ .

Proof.

Consider the class of set-functions $F = \{f : Y \to β: Y \subseteq_{e} X \land f : (Y, <) (β, \in)\}$ . where $\subseteq_{e}$ denoted Initial part of and $β$ ranges over ordinals. $F$ is a class i.e. defined by a first order formula. (We shall show eventually it is a set.) It is nonempty because it contains the empty cunction $\emptyset \to 0$ .

Given $f : Y \to β$ in $F$ , if the domain $Y$ of $f$ is not the whole of $X$ we can take $y \in X ∖ Y$ to be $\in$ -least and define $f' (y) = β$ and $f' (x) = f (x)$ for $x \in Y$ hence extend $f$ . Furthermore we can prove that for any $f, g \in F$ either $dom f \subseteq dom g$ or $dom g \subseteq dom f$ (since both are initial parts of $X$ ) and that $f, g$ agree on their common doman. (Else take $x \in X$ to be least such that $f, g$ disagree at $x$ .) It follows that the union of a set of fucntions in $F$ is a function in $F$ .

Now for each $x \in X$ let $F_{x}$ be the unique element of $F$ with domain $\{y \in X: y < x\}$ proving (by considering the least such $x$ such that $F_{x}$ doesn't exis) that such $F_{x}$ always exists. Then $\{F_{x}: x \in X\}$ is a set by replacement and $f = ⋃ \{F_{x}: x \in X\}$ is a set function mapping $X$ to some ordinal, as may be checked.