Church-Kleene ordinal

An ordinal is considered recursive iff it is the order type of a computable well-ordering of a subset of the natural numbers. The Church-Kleene ordinal \(\omega_1^\text{CK}\), then, is the first ordinal that is not recursive.

An ordinal is always recursive iff it is less than another recursive ordinal, so the Church-Kleene ordinal is also the supremum of all recursive ordinals. It is a limit ordinal, since the successor of a recursive ordinal is also recursive. Since every computable well-ordering can be identified by a distinct Turing machine, of which there are countably many, \(\omega_1^\text{CK}\) is also countable.

Ordinal notation Edit

A system called Kleene's \(\mathcal{O}\) gives us an ordinal notation over all recursive ordinals. Before constructing Kleene's \(\mathcal{O}\), first we need an enumeration \(f_0, f_1, f_2, \ldots\) of all the partial recursive functions. One way to do this is to order all the Turing machines lexicographically.

Let \(K\) be the set of all notations, let \(<_\mathcal{O}\) be an operator indicating a well-ordering of \(K\), and let \(\mathcal{O}\) be a function mapping notations to ordinals. These three are defined inductively as follows:

• \(0 \in K\) and \(\mathcal{O}(0) = 0\).
• If \(n \in K\) and \(\mathcal{O}(n) = \alpha\), then \(2^n \in K\), \(\mathcal{O}(2^n) = \alpha + 1\), and \(n <_\mathcal{O} 2^n\).

• If for all natural numbers \(n\), we have \(f_i(n) \in K\) and \(f_i(n) <_\mathcal{O} f_i(n + 1)\), then \(3 \cdot 5^i \in K\), \(\mathcal{O}(3 \cdot 5^i) = \lim_{k \rightarrow \omega} \mathcal{O}(f_i(k))\), and for all \(k\) \(f_i(k) <_\mathcal{O} 3 \cdot 5^i\).
• \(a <_\mathcal{O} b\) and \(b <_\mathcal{O} c\) implies \(a <_\mathcal{O} c\).

Kleene's \(\mathcal{O}\) is, inescapably, not a computable notation.

See also Edit