FANDOM


先回のブログで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\) の元だとわかった3つの例 ①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\) の元の合成により得られる.

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

FANDOMでも見てみる

おまかせWiki