\(\omega_1^\text{CK}\)("チャーチ・クリーネ順序数" Church-Kleene ordinal と呼ばれる)は最初の非再帰順序数である。再帰集合(再帰順序数もこれに含まれる)とはオブジェクトのメンバシップを決定するアルゴリズムの存在する集合のことである。\(\omega_1^\text{CK}\)は再帰順序数全体の集合、すなわち全ての再帰順序数の上限である。\(f_{\omega_1^\text{CK}}(n)\)は、どんな階層であれ、計算可能などんな関数よりも早く成長する。アロンゾ・チャーチとスティーヴン・コール・クリーネから名付けられた。
これは停止性問題の複雑性で、それによって\(f_{\omega_1^\text{CK}}(n)\)は\(\Sigma(n)\)、ビジービーバー関数と同等であると分かる。
基本列
\(\omega_1^\text{CK}\)の基本列は自明でない。それを定義する一つの方法として、クリーネの \(\mathcal{O}\)、再帰順序数全てを表記できる擬順序的表記がある。クリーネの \(\mathcal{O}\)を構築する前に、 部分再帰関数\(f_0, f_1, f_2, \ldots\)の全列挙が必要である。これをするための方法としてチューリングマシンの辞書的全列挙があげられる。
\(K\)をその列挙とし、\(<_\mathcal{O}\)を\(K\)の整列集合を示す演算子とする。また、\(\mathcal{O}\)は順序数を表記する関数となる。
- \(0 \in K\)、また \(\mathcal{O}(0) = 0\)。
- もし \(n \in K\) かつ \(\mathcal{O}(n) = \alpha\)ならば、 \(2^n \in K\)、 \(\mathcal{O}(2^n) = \alpha + 1\)、 また \(n <_\mathcal{O} 2^n\)。
- 全自然数 \(n\)に対し、 \(f_i(n) \in K\) 、 \(f_i(n) <_\mathcal{O} f_i(n + 1)\)とすると、 \(3 \cdot 5^i \in K\), \(\mathcal{O}(3 \cdot 5^i) = \lim_{k \rightarrow \omega} \mathcal{O}(f_i(k))\)で、 全ての \(k\) で \(f_i(k) <_\mathcal{O} 3 \cdot 5^i\)。
- \(a <_\mathcal{O} b\) かつ \(b <_\mathcal{O} c\) ならば \(a <_\mathcal{O} c\)。
\(g(0) = 0\) 、また \(g(n + 1)\) を \(m\) \(g(n) <_\mathcal{O} m\)をみたす最小の\(m\)と定義する。\(\omega_1^\text{CK}\)の基本列は、\(\omega_1^\text{CK}[n] = \mathcal{O}(g(n))\)となる。
これらは\(\omega^2\)までの例である:
- \(\mathcal{O}(0) = 0\)、 \(\mathcal{O}(1) = 1\)、 \(\mathcal{O}(2) = 2\)、 \(\mathcal{O}(2^2) = 3\)、 そして一般的に \(\mathcal{O}(2 \uparrow\uparrow n) = n + 1\)。
- \(f_{10}(n) = 2 \uparrow\uparrow n\) を選ぶ(これは再帰関数)。すると \(\mathcal{O}(3 \cdot 5^{10}) = \sup\{\mathcal{O}(2), \mathcal{O}(2^2), \mathcal{O}(2^{2^2}), \ldots\} = \sup\{1, 2, 3, \ldots\} = \omega\)。
- \(f_{100}(n) = (2 \uparrow)^n (3 \cdot 5^{10})\)を選ぶ。 すると \(\mathcal{O}(3 \cdot 5^{10}) = \sup\{\mathcal{O}(2^{3 \cdot 5^{10}}), \mathcal{O}(2^{2^{3 \cdot 5^{10}}}),\mathcal{O}(2^{2^{2^{3 \cdot 5^{10}}}}), \ldots\} = \sup\{\omega + 1, \omega + 2, \omega + 3, \ldots\} = \omega2\)。
- これを定義なしに続けることもできるが、 \(\mathcal{O}(3 \cdot 5^{10^a}) = \omega a\)と定義する。
- \(f_{11}(n) = 3 \cdot 5^{10^n}\)と定義することで、これらを対角化できる。