2重帰納関数の評価 ～支配定理に向けて～

先回のブログで2重帰納関数の定義が固まってきました。目標とするのは『3変数アッカーマン関数は全ての2重帰納関数を支配する』という次の予想です（この予想が成り立つように \(\mathcal{F}_2\) は定義されるべきだし、もし成り立たないなら \(\mathcal{F}_2\) の定義は修正されるべきです）。

予想(支配定理)： 任意の \(f(x_1,\ldots,x_n) \in \mathcal{F}_2\) に対して、ある非負整数 \(N\) が存在して、任意の非負整数 \(x_1,\ldots,x_n\) に対して \( f(x_1,\ldots,x_n) \le A(N,0,\mathrm{max}(x_1,\ldots,x_n)) 。 \)□

ただし、\(\mathcal{F}_2\) の定義については先回のブログを参照。\(A(x,y,z)\) は次で定義される3変数アッカーマン関数。

• \( A(0,0,z)＝z+1 \)
• \( A(x+1,0,z)＝A(x,z,z) \)
• \( A(x,y+1,0)＝A(x,y,1) \)
• \( A(x,y+1,z+1)＝A(x,y,A(x,y+1,z)) \)

もしこの支配定理が成り立つならば、系として \(A(x,y,z) \not \in \mathcal{F}_2\) がわかります。実際、\(A(x,y,z) \in \mathcal{F}_2\) だと仮定すると、ある非負整数 \(N\) が存在して任意の非負整数 \(x,y,z\) について \(A(x,y,z)<A(N,0,\max(x,y,z))\) です。 \(x=y=z=N+1\) とすると、\(A(N+1,N+1,N+1)\le A(N,0,N+1)\) です。一方補題3と4より \(A(N,0,N+1)<A(N+1,N+1,N+1)\) がわかるのでこれは矛盾です。

具体例

いきなり一般の支配定理を示すのは頭がこんがらがるので（というかまだできていません…）、先回 \(\mathcal{F}_2\) の元だとわかった３つの例 ①2変数アッカーマン関数, ②関数の数え上げ, ③チェーン関数 について支配定理を示そうと思います。証明に必要な補題は次の章にまとめてあります。

2変数アッカーマン関数

命題： 任意の非負整数 \(x,y\) に対して、\(A(x,y) \le A(1,0,\max(x,y))\)。

証明： 定義より \(A(x,y)=A(0,x,y)\) だから, \(A(x,y)=A(0,x,y)\le A(0,x,\max(x,y)) （補題2より）\)\( \le A(0,\max(x,y),\max(x,y)) （補題3より）\)\( = A(1,0,\max(x,y))\)。■

必要な補題たち

本ブログは 原始帰納的函数とアッカーマン函数 - 藤田 博司 を大いに参照しています。予想の証明に向けて必要になる補題たちを列挙していきます。（まだ証明をしていないものもあります。）

• 補題1: \(z < A(x,y,z)\)
• 補題2: \(A(x,y,z) < A(x,y,z+1) \)
• 補題3: \(A(x,y,z) < A(x,y+1,z) \)
• 補題4: \(A(x,y,z) < A(x+1,y,z) \)
• 補題5: \(A(x,y,z+1) < A(x,y+1,z)\)
• 補題6: \(A(x,y+1,z) < A(x+1,y,z) \)
• 補題7: \(A(x,y,A(a,b,c)) < A(\max(x,a),\max(y,b)+1,c+1) \)
• 補題8: \(A(x,2y,z) < A(x+1,y,z)\)

ただし\(x,y,z,a,b,c\) は任意の非負整数。

• 2変数アッカーマン関数版の支配定理(上記リンクの定理11.参照): 原始帰納関数 \(f(x_1,\ldots,x_n)\)に対してある非負整数 \(N_0\) が存在し、任意の非負整数 \(x_1,\ldots,x_n\) について  \(f(x_1,\ldots,x_n) \le A(N_0,\max(x_1,\ldots,x_n)) \)。

"支配定理"の証明の方針

\(\mathcal{D}_2\) を, \(A(x,y,z)\) に支配される \(n\) 変数関数 (\(n=0,1,2,\ldots\)) 全体の集合とします。つまり、 \(\mathcal{D}_2:=\{f(x_1,\ldots,x_n)\in\mathcal{F}| \exists N \in \mathbb{Z}_{\ge 0} ;\)\( \forall x_1,\ldots,x_n \in \mathbb{Z}_{\ge 0}, f(x_1,\ldots,x_n) \)\( \le A(N,0,\mathrm{max}(x_1,\ldots, x_n)) \}\) 。\(\mathcal{D}\) は"支配する=dominate" のDです。すると定理の主張は \(\mathcal{F}_2\subset \mathcal{D}_2\) と同値です。一方 \(\mathcal{F}_2\) は「ある3つの公理をみたす \(\mathcal{F}\) の部分集合の中で包含関係に関して最小のもの」として定義されていたので、結局  \(\mathcal{D}_2\) が次の3つの公理をみたすことを示せばよいということになります。

• \( \mathcal{F}_1 \subset \mathcal{D}_2\).
• \(f(y_1,\ldots,y_k), g_1(x_1,\ldots,x_m),\ldots, g_k(x_1,\ldots,x_m) \in \mathcal{D}_2\) ならば、\(h(x_1,\ldots,x_m)=f(g_1(x_1,\ldots,x_m),\ldots, g_k(x_1,\ldots,x_m))\) と定めたとき、\(h \in \mathcal{D}_2\).
• 非負整数 \(k\) に対し、\((2+k)\) 変数関数 \(G(n,x,y_1,\ldots,y_k) \) が次の1.～3.を満たすとき、\(G(n,x,y_1,\ldots,y_k)\in\mathcal{D}_2\).
  1. \(f(x,y_1,\ldots,y_k) = G(0,x,y_1,\ldots,y_k)\) とおくとき、\(f \in \mathcal{D}_2 \).
  2. 任意の非負整数 \( n \) に対して、\(k\) 変数関数 \( g_n(y_1,\ldots,y_k):=G(n+1,0,y_1,\ldots,y_k)\) は \( (1+k) \) 変数関数 \( \varphi_{n}(x,y_1,\ldots,y_k):=G(n,x,y_1,\ldots,y_k)\) および \(\mathcal{D}_2\) の元の合成により得られる.
  3. 任意の非負整数 \( n,x \) に対して、\(k\) 変数関数 \( h_{n,x}(y_1,\ldots,y_k):=G(n+1,x+1,y_1,\ldots,y_k)\) は \(k\) 変数関数 \( \psi_{n,x}(y_1,\ldots,y_k):=G(n+1,x,y_1,\ldots,y_k)\)、\( (1+k) \) 変数関数 \(\varphi_{n}(x,y_1,\ldots,y_k)\) および \(\mathcal{F}_1\) の元の合成により得られる.