FANDOM


\(\omega_1^\text{CK}\)("チャーチ・クリーネ順序数" Church-Kleene ordinal と呼ばれる)は最小の非再帰順序数である。アロンゾ・チャーチスティーヴン・コール・クリーネの名に由来する。

順序数が再帰的であるとは、自然数の集合の再帰的整列順序の順序数型であるということである。\(\omega_1^\text{CK}\)は再帰順序数全体の集合、すなわち全ての再帰順序数の上限である。再帰的順序数の後続順序数は再び再帰的となるので、\(\omega_1^\text{CK}\)は極限順序数である。全ての再帰的整列順序は互いに相異なるチューリングマシンと同一視でき、チューリングマシンの同値類は可算個しかないので、\(\omega_1^\text{CK}\)もまた可算である。

\(\omega_1^\text{CK}\)の基本列を固定した上で定義される急増加関数階層\(f_{\omega_1^\text{CK}}(n)\)は、いかなる計算可能関数よりも早く成長する。

基本列

\(\omega_1^\text{CK}\)の基本列は自明でない。それを定義する一つの方法として、クリーネの \(\mathcal{O}\)という再帰順序数全てを表記できる擬順序的表記がある。通常の順序数表記にはその整列順序構造に計算可能性が要求されるが、この表記は計算不可能である。クリーネの \(\mathcal{O}\)を構築する前に、 部分再帰関数 \(f_0, f_1, f_2, \ldots\)の全列挙が必要である。これをするための方法としてチューリングマシンの辞書的全列挙があげられる。

クリーネの \(\mathcal{O}\) の表記全体の集合 \(K\)とその上の整礎狭義半順序\(<_\mathcal{O}\)と表記を順序数に変換する関数\(\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) = \sup_{k \in \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}\)と定義することで、これらを対角化できる。
特に記載のない限り、コミュニティのコンテンツはCC-BY-SA ライセンスの下で利用可能です。