巨大数研究 Wiki
登録
Advertisement

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

順序数が再帰的であるとは、2条件

  1. グラフが\(\mathbb{N}^2\)の部分集合である。
  2. グラフの特性関数は計算可能である。

を満たす整列順序の順序数型であるということである。すなわち、順序数\(\alpha\)が再帰的であるとは、ある計算可能全域写像 \begin{eqnarray*} R \colon \mathbb{N}^2 & \to & \mathbb{N} \\ (n,m) & \mapsto & R(n,m) \end{eqnarray*} が存在して以下を満たすということである:

  1. \(R\)は\(\mathbb{N}\)上の二項関係を定める。すなわち任意の\((n,m) \in \mathbb{N}^2\)に対し\(R(n,m) \in \{0,1\}\)である。
  2. \(R\)が定める\(\mathbb{N}\)上の二項関係は\(\mathbb{N}\)の部分集合上の反射的関係である。すなわち\(D := \{n \in \mathbb{N} \mid R(n,n) = 1\}\)と置くと、\(D = \{n \in \mathbb{N} \mid \exists m \in \mathbb{N}[R(n,m) = 1 \lor R(m,n) = 1]\}\)である。
  3. \(R\)が定める\(D\)上の反射的関係は整列順序である。すなわち追加で以下の性質を満たす:
    1. \(R\)が定める\(D\)上の反射的関係は反対称律を満たす。すなわち任意の\((n,m) \in D^2\)に対し、\(R(n,m) = R(m,n) = 1\)ならば\(n = m\)である。
    2. \(R\)が定める\(D\)上の反射的関係は推移律を満たす。すなわち任意の\((n,m,l) \in D^3\)に対し、\(R(n,m) = R(m,l) = 1\)ならば\(R(n,l) = 1\)である。
    3. \(R\)が定める\(D\)上の反射的関係は整礎性を満たす。すなわち空でない任意の\(S \subset D\)に対し、ある\(n \in S\)が存在して任意の\(m \in S\)に対し\(R(n,m) = 1\)である。
  4. \(R\)が定める\(D\)上の整列順序の順序型は\(\alpha\)である。すなわちある全単射な写像\(f \colon \alpha \to D\)が存在して、任意の\((\beta,\gamma) \in \alpha^2\)に対し\(\beta \leq \gamma\)と\(R(f(\beta),f(\gamma))\)が同値である。

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

\(\omega_1^\text{CK}\)の基本列を固定した上で定義される急増加関数階層\(f_{\omega_1^\text{CK}}(n)\)は、いかなる計算可能関数よりも早く成長すると主張されることが多いが、どのような基本列を固定すれば\(f_{\omega_1^\text{CK}}(n)\)がそのように急増加するかすら知られていないため誤解である。実際、\(f_{\omega_1^\text{CK}}(n)\)が\(f_{\omega^4}(n)\)で抑えられるような\(\omega_1^\text{CK}\)の基本列が存在する。[1]

基本列[]

\(\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 \in K\) かつ \(g(n) <_\mathcal{O} m\)をみたす最小の\(m \in \mathbb{N}\)と定義する。\(\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}\)と定義することで、これらを対角化できる。


参考文献[]

  1. 木原貴行, [1], 2019.
Advertisement