KleeneのOの亜種について

Math Advent Calendar 2019４日目投稿用の記事です。非再帰的順序数表記であるクリーネの\(\mathcal{O}\)の亜種を無数に構成します。

部分写像\(\mathbb{N} \to \mathbb{N}\)全体の集合を\(X\)と置く。\(F\)を写像\(\mathbb{N} \setminus \{0\} \to X\)であって像が任意の全域定数関数を含むとする。例えば\(F\)としては原始再帰関数のコードやチューリングマシンのコード等、特定の計算モデルの数え上げを整えることで\(F\)を具体的に構成することが可能である。

この記事では与えられた\(F\)に対し、具体的に順序数の表記（算術で定義される順序数表記ではなく、集合論で定義される単に順序数へ対応を持つだけの表記）\(T_F\)を構成する。

基本列

可算順序数全体の集合を\(\omega_1\)と置き、\(\mathbb{N}\)の部分集合全体の集合を\(\mathcal{P}(\mathbb{N})\)と置く。写像 \begin{eqnarray*} \mathcal{G}_F \colon \omega_1 & \to & \mathcal{P}(\mathbb{N}) \\ \alpha & \mapsto & \mathcal{G}_F(\alpha) \end{eqnarray*} を以下のように超限再帰的に定める：

1. \(\textrm{cof}(\alpha) = 0\)ならば、\(\mathcal{G}_F(\alpha) := \{0\}\)である。
2. \(\textrm{cof}(\alpha) = 1\)ならば、\(\mathcal{G}_F(\alpha)\)は以下を満たす\(a \in \mathbb{N} \setminus \{0\}\)全体の集合である：
   1. \(\textrm{dom}(F(a)) = \mathbb{N}\)である。
   2. \(a \notin \bigcup_{\beta \in \alpha} \mathcal{G}_F(\beta)\)である。
   3. ある\(m \in \mathcal{G}_F(\max \alpha)\)が存在して、任意の\(n \in \mathbb{N}\)に対し\(F(a)(n) = m\)である。
3. \(\textrm{cof}(\alpha) = \omega\)ならば、\(\mathcal{G}_F(\alpha)\)は以下を満たす\(a \in \mathbb{N} \setminus \{0\}\)全体の集合である：
   1. \(\textrm{dom}(F(a)) = \mathbb{N}\)である。
   2. \(a \notin \bigcup_{\beta \in \alpha} \mathcal{G}_F(\beta)\)である。
   3. 任意の\(n \in \mathbb{N}\)に対し、\(F(a)(n) \in \bigcup_{\beta \in \alpha} \mathcal{G}_F(\beta)\)である。
   4. 任意の\(n \in \mathbb{N}\)に対し、ある\(\beta,\gamma \in \alpha\)が存在して、\(F(a)(n) \in \mathcal{G}_F(\beta)\)かつ\(F(a)(n+1) \in \gamma\)かつ\(\beta \in \gamma\)である。

\(T_F := \bigcup_{\alpha \in \omega_1} \mathcal{G}_F(\alpha) \in \mathcal{P}(\mathbb{N})\)と置く。各\(a \in T_F\)に対し、\(a \in \mathcal{G}_F(\alpha)\)を満たす一意な\(\alpha \in \omega_1\)を\(o_F(a)\)と置く。

写像 \begin{eqnarray*} [ \ ]_F \colon T_F \times \mathbb{N} & \to & \mathbb{N} \\ (a,n) & \mapsto & a[n]_F \end{eqnarray*} を以下のように定める：

1. \(\textrm{cof}(o_F(a)) = 0\)ならば、\(a[n]_F := 0\)である。
2. \(\textrm{cof}(o_F(a)) = 1\)ならば、\(a[n]_F := F(a)(0)\)である。
3. \(\textrm{cof}(o_F(a)) = \omega\)ならば、\(a[n]_F := F(a)(n)\)である。

\([ \ ]_F\)は\(o_F\)と整合的な基本列を定める。すなわち、\(\textrm{cof}(o_F(a)) = 1\)ならば\(o_F(a[0]) = \max o_F(a)\)であり、\(\textrm{cof}(o_F(a)) = \omega\)ならば\(o_F(a[n])\)は\(o_F(a)\)の基本列をなす。

以上より、\(T_F\)は順序数への対応\(o_F\)及びそれと整合的な基本列\([ \ ]_F\)を持つ（一般には非再帰的な）表記となる。

急増加関数

写像 \begin{eqnarray*} f_F \colon T_F \times \mathbb{N} & \to & \mathbb{N} \\ (a,n) & \mapsto & f_{F,a}(n) \end{eqnarray*} を以下のように超限再帰的に定める：

1. \(\textrm{cof}(o_F(a)) = 0\)ならば、\(f_{F,a}(n) := n+1\)である。
2. \(\textrm{cof}(o_F(a)) \neq 0\)ならば、\(f_{F,a}(n) := \sum_{m=0}^{n} f_{F,a[m]}^n(n)\)である。

順序数の整礎性と\([ \ ]_F\)の\(o_F\)との整合性から、\(f_F\)は\(T_F \times \mathbb{N}\)全体で定義される関数階層である。

写像 \begin{eqnarray*} \textrm{enum}_F \colon \mathbb{N} & \to & T_F \\ n & \mapsto & \textrm{enum}(n) \end{eqnarray*} を以下のように再帰的に定める：

1. \(n = 0\)ならば\(\textrm{enum}(n) := 0\)である。
2. \(n \neq 0\)ならば\(\textrm{enum}(n) := \min \{a \in T_F \mid a > \textrm{enum}(n-1)\}\)である。

要するに\(\textrm{enum}_F\)は\(T_F\)の数え上げ関数である。

写像 \begin{eqnarray*} \textrm{Lim}_F \colon \mathbb{N} & \to & \mathbb{N} \\ n & \mapsto & \textrm{Lim}_F(n) \end{eqnarray*} を以下のように定める：

1. \(n = 0\)ならば、\(\textrm{Lim}_F(n) := f_{F,\textrm{enum}(n)}(n)\)である。
2. \(n \neq 0\)ならば、\(\textrm{Lim}_F(n) := f_{F,\textrm{enum}(n)}^{\textrm{Lim}_F(n-1)}(n)\)である。

以上より、\(F\)から（一般には計算不可能な）急増加関数\(\textrm{Lim}_F\)を一意に構成することが出来た。

特に\(F\)として、原始再帰的関数のコードやチューリングマシンのコードを用いることで具体的に写像\(\mathbb{N} \setminus \{0\} \to X\)が構成できるため、これにより具体的に巨大関数を得る。予想としては、チューリングマシンのコードに付随する巨大関数はクリーネの\(\mathcal{O}\)に伴う急増加関数階層\(f_{\omega_1^{\textrm{CK}}}\)で近似できると考えられる。原始再帰関数のコードに付随する巨大関数はどのくらいになるだろうか？