An ordinal is considered *recursive* if 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 if 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.

## Contents

## Ordinal notation

A system called **Kleene's \(\mathcal{O}\)** gives us a non-recursive notation system over all recursive ordinals. Since an ordinal notation is required to be recursive, it is not an ordinal notation. 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-founded strict partial 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) = \sup_{k \in \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\).

### Examples

From definition it follows that:

\(\mathcal{O}(2^0) = 1 \\ \mathcal{O}(2^{2^0}) = 2 \\ \mathcal{O}(2^{2^{2^0}}) = 3 \\ \mathcal{O}(2^{2^{2^{2^0}}}) = 4 \\ \mathcal{O}(3 \cdot 5^i) = \omega\)

Here \(i\) is an index of Turing machine that computes \(f_i(n) = 2 \uparrow\uparrow n\). Continuing,

\(\mathcal{O}(2^{3 \cdot 5^i}) = \omega+1 \\ \mathcal{O}(2^{2^{3 \cdot 5^i}}) = \omega+2 \\ \mathcal{O}(2^{2^{2^{3 \cdot 5^i}}}) = \omega+3 \\ \mathcal{O}(2^{2^{2^{2^{3 \cdot 5^i}}}}) = \omega+4 \\ \mathcal{O}(3 \cdot 5^j) = \omega \times 2\)

Here \(j\) is an index of Turing machine that computes \(f_j(n) = (2 \uparrow)^n (3 \cdot 5^i)\).

Continuing in this manner, it is possible to notate all recursive ordinals. The only issue is that indices of Turing machines are uncomputable; that is, we can't run over TM's via algorithm to verify that it actually computes needed function.

## Fundamental sequences

For each \(\alpha < \omega_1^\text{CK}\), if \(\alpha\) is a limit ordinal, then \(\alpha[n]\) is defined as \(\mathcal{O}(f_{i_{\alpha}}(n))\), where \(i_{\alpha}\) denotes the minimum of the non-empty set \(\{i \in K \mid \mathcal{O}(i) = \alpha\}\).

Define \(g(0) = 0\) and \(g(n+1)\) as the notation with smallest \(m \in \mathbb{N}\) such that \(m \in K\) and \(\mathcal{O}(g(n)) < \mathcal{O}(m)\). The fundamental sequence for \(\omega_1^\text{CK}\), then, is defined as \(\omega_1^\text{CK}[n] = \mathcal{O}(g(n))\).

### Examples

Let's check how we define \(\omega[n] = \mathcal{O}(f_{i_{\omega}}(n))\).

Say that there is an ordering of Turing machines so that \(i_{\omega} = 1000\) and Turing machine with index \(1000\) computes \(2 \uparrow\uparrow n\). Then \(\omega[n] = \mathcal{O}(f_{1000}(n)) = \mathcal{O}(2 \uparrow\uparrow n) = 1+n\).

Say that there is another ordering of Turing machines so that \(i_{\omega} = 969\) and Turing machine with index \(969\) computes \(2 \uparrow\uparrow (n-1)\). Then \(\omega[n] = \mathcal{O}(f_{969}(n)) = \mathcal{O}(2 \uparrow\uparrow (n-1)) = n\).

Thus, fundamental sequences are dependent on ordering of Turing machines.

### First few terms of fundamental sequence of Church-Kleene ordinal

By the definition, \(\omega_1^\text{CK}[0] = 0\). It turns out that \(\omega_1^\text{CK}[1] = 1\) and \(\omega_1^\text{CK}[2] = 2\) under any enumeration of Turing machines since 1 and 2 cannot be expressed in the form \(3 \cdot 5^n\). However, \(\omega_1^\text{CK}[3]\) depends on enumeration of Turing machines because \(3 = 3 \cdot 5^0\). If we fix, for example, \(f_0(n) = 2 \uparrow\uparrow n\), then \(\omega_1^\text{CK}[3] = \omega\).

## Fast-growing hierarchy

There is much wrong information on the fast-growing hierarchy \(f_{\omega_1^\text{CK}}\) with respect to the system of fundamental sequence above.

- The statement
**"\(f_{\omega_1^\text{CK}}\) is computable because every function in the fast growing hierarchy is computable"**is wrong. A function in the fast-growing hierarchy is not necessarily computable even if it is associated to a recursive ordinal, and moreover \(\omega_1^\text{CK}\) is not recursive. - The statement
**"\(f_{\omega_1^\text{CK}}\) is approximated to the busy beaver function because both of them are uncomputable functions diagonalising computable functions"**is wrong. The system of fundamental sequences above heavily depends on the choice of the enumeration of Turing machines, and so does the growth rate of \(f_{\omega_1^\text{CK}}\). For example, it is known that it can be bounded by \(f_{\omega+3}\) in Wainer hierarchy if one chooses a specific enumeration of Turing machines.^{[1]}At least, there is no known enumeration of Turing machines for which \(f_{\omega_1^\text{CK}}\) is approximated to the busy beaver function. - The statement
**"\(f_{\omega_1^\text{CK}}\) grows faster than any computable function because it diagonalises all computable functions in the fast-growing hierachy"**is wrong. As we explained above, it can be bounded by \(f_{\omega+3}\) in Wainer hierarchy. The diagonalisation sometimes causes the decreasing of growth rates. - The statement
**"\(f_{\omega_1^\text{CK}}\) is bounded by the second order busy beaver function because it can be computable by an oracle Turing machine"**is wrong. Such a comparison has never been verified for a specific non-pathologic enumeration of Turing machines. We do not even know whether \(f_{\omega_1^\text{CK}}\) is bounded by the \(\alpha\)-th order busy beaver function for some ordinal \(\alpha\) below \(\omega_1^\text{CK}\) or not with respect to a non-pathologic enumeration of Turing machines, because no notation up to \(\omega_1^\text{CK}\) is computable by a higher order oracle Turing machine whose order is smaller than \(\omega_1^\text{CK}\).

Namely, the growth rate of \(f_{\omega_1^\text{CK}}\) with respect to a non-pathologic enumeration of Turing machines is unknown in the sense that the least ordinal \(\alpha\) such that \(f_{\omega_1^\text{CK}}\) is bounded by the \(\alpha\)-th order busy beaver function is unknown. At least, if a given function \(f\) irrelevant to \(f_{\omega_1^\text{CK}}\) is verified to grows faster than \(f_{\omega_1^\text{CK}}\), then it usually grows significantly faster than the busy beaver function because we usually need a stronger tool than higher order oracle Turing machines in order to study such an \(f\).

However, \(f_{\omega_1^\text{CK}}\) (with respect to any system of fundamental sequences) necessarily grows at least as fast as \(f_\omega\) in Wainer hierarchy because the fundamental sequence of \(\omega_1^\text{CK}\) is monotonically increasing.

## References

- ↑ T. Kihara, omega-1-ck.pdf.

## External links

- Wikipedia articles on Kleene's O and Church-Kleene ordinal

**Basics:** cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation**Theories:** Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC**Model Theoretic Concepts:** structure · elementary embedding**Countable ordinals:** \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\eta_0\) · \(\Gamma_0\) (Feferman–Schütte ordinal) · \(\varphi(1,0,0,0)\) (Ackermann ordinal) · \(\psi_0(\Omega^{\Omega^\omega})\) (small Veblen ordinal) · \(\psi_0(\Omega^{\Omega^\Omega})\) (large Veblen ordinal) · \(\psi_0(\varepsilon_{\Omega + 1}) = \psi_0(\Omega_2)\) (Bachmann-Howard ordinal) · \(\psi_0(\Omega_\omega)\) with respect to Buchholz's ψ · \(\psi_0(\varepsilon_{\Omega_\omega + 1})\) (Takeuti-Feferman-Buchholz ordinal) · \(\psi_0(\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}})\) (countable limit of Extended Buchholz's function) · \(\omega_1^\mathfrak{Ch}\) · **\(\omega_1^{\text{CK}}\) (Church-Kleene ordinal)** · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\zeta,\Sigma,\gamma\) (ordinals on infinite time Turing machine) · gap ordinal · List of countable ordinals**Ordinal hierarchies:** Fast-growing hierarchy · Slow-growing hierarchy · Hardy hierarchy · Middle-growing hierarchy · N-growing hierarchy**Ordinal functions:** enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Buchholz's function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert's Psi function**Uncountable cardinals:** \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal**Classes:** \(V\) · \(L\) · \(\textrm{On}\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)