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.

## 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\).

## 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))\).

## Fast-Growing Hierarchy

There are many wrong informations 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\).

## See also

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

**Basics:** cardinal numbers · normal function · ordinal notation · ordinal numbers · fundamental sequence · ordinal collapsing function**Theories:** Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC**Countable ordinals:** \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\Gamma_0\) · \(\vartheta(\Omega^3)\) · \(\vartheta(\Omega^\omega)\) · \(\vartheta(\Omega^\Omega)\) · \(\vartheta(\varepsilon_{\Omega + 1}) = \psi(\Omega_2)\) · \(\psi(\Omega_\omega)\) · \(\psi(\varepsilon_{\Omega_\omega + 1})\) · \(\psi(\psi_I(0))\) · \(\omega_1^\mathfrak{Ch}\) · **\(\omega_1^\text{CK}\)** · \(\omega_\alpha^\text{CK}\) · \(\lambda,\zeta,\Sigma,\gamma\) · List of countable ordinals**Ordinal hierarchies:** Fast-growing hierarchy · Slow-growing hierarchy · Hardy hierarchy · Middle-growing hierarchy · N-growing hierarchy**Uncountable cardinals:** \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal · more...