This church is not to be confused with logician Alonzo Church. It is probably very clean.
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 · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation · Absolute infinity
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 one of chess) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\gamma,\zeta,\Sigma\) (Infinite time Turing machine ordinals) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Hardy hierarchy · Slow-growing hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Weak Buchholz's function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Weak Buchholz's function · Extended Buchholz's function · Jäger-Buchholz function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert's Psi function · Arai'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: \(\textrm{Card}\) · \(\textrm{On}\) · \(V\) · \(L\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)