FANDOM

9,785 Pages

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.