Induction and Recursion

Induction#

Theorem. (Transfinite Induction Theorem). Let \(C\) be a class of ordinals and assume that

\(0\in C\),
if \(\alpha\in C\) then \(\alpha+1\in C\),
if \(\alpha\) is a nonzero limit ordinal and \(\beta \in C\) for all \(\beta < \alpha\) then \(\alpha\in C\).

Then \(C\) is the class of all ordinals.

Thus by ensuring that, say, a property holds for a class \(C\) of ordinals that satisfies the conditions for transfinite induction, then it holds for all ordinals. Hence we can define by transfinite recursion.

Recursion#

Theorem. (Transfinite Recursion Theorem). Let \(G\) be a function on \(V\) (the universe), then

\[F(\alpha) = G(F\restriction\alpha)\]

defines a unique function \(F\) on \(\text{Ord}\) for each \(\alpha\). In other words, let \(a_\alpha = F(\alpha)\), then for each \(\alpha\),

\[a_\alpha = G(\langle a_\xi:\xi<\alpha\rangle).\]

Here we used Replacement: \(F\restriction\alpha\) is a set for each \(\alpha\).

From this we can prove the following corollary:

Corollary. Let \(X\) be a set and \(\theta\) an ordinal. For every function \(G\) on the set of all transfinite sequences in \(X\) of length \(<\theta\) such that \(\text{Range}(G)\subset X\) there is a unique \(\theta\)-sequence \(\langle a_\alpha:\alpha < \theta\rangle\) in \(X\) such that \(a_\alpha = G(\langle a_\xi:\xi<\alpha\rangle)\) for every \(\alpha<\theta\).

Limit#

Definition. Given a nonzero limit ordinal \(\alpha\) and let \(\langle \gamma_\xi:\xi <\alpha\rangle\) be a non-decreasing sequence of ordinals. The limit of the sequence is defined by

\[\lim_{\xi\to\alpha}\gamma_\xi = \text{sup}\{\gamma_\xi:\xi<\alpha\}.\]

A sequence of ordinals \(\langle \gamma_\alpha:\alpha\in\text{Ord}\rangle\) is normal if it is increasing and continuous, namely for every ordinal \(\alpha\), \(\gamma_\alpha = \lim_{\xi\to\alpha}\gamma_\xi\).