FANDOM


特に2重帰納関数がどのように定義されるべきか、その定義の候補を考えてみました。それなりに良い定義としてまとまってきた感触あります。

続き→ 2重帰納関数の評価_~支配定理に向けて~

2重帰納関数の定義(と思しきもの)

非負整数 \(n\) に対して、写像 \(f:\mathbb{Z}_{\ge 0}^n \to \mathbb{Z}_{\ge 0}\) のことを \(n\) 変数関数と呼ぶことにします。 \(n=0\) のときは \(\mathbb{Z}_{\ge 0}^0 = 1点集合\) なので、\(0\) 変数関数は定数関数になります。

\( \mathcal {F} = \{f | f は n 変数関数\, (n: 非負整数) \} \) とおきます。\( \mathcal{F}_1\) を原始帰納関数(=1重帰納関数)全体とします。もちろん \( \mathcal{F}_1 \subset \mathcal{F}\) です。 このとき、\( \mathcal {F}\) の部分集合\( \mathcal {F}_2\) を、次の公理を満たす集合 \( \mathcal {F}_2\) の中で、(包含関係に関して)最小のものと定義します。

  • \( \mathcal{F}_1 \subset \mathcal{F}_2\).
  • \(f(y_1,\ldots,y_k), g_1(x_1,\ldots,x_m),\ldots, g_k(x_1,\ldots,x_m) \in \mathcal{F}_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{F}_2\).
  • 非負整数 \(k\) に対し、\((2+k)\) 変数関数 \(G(n,x,y_1,\ldots,y_k) \) が次の1.~3.を満たすとき、\(G(n,x,y_1,\ldots,y_k)\in\mathcal{F}_2\).
    1. \(f(x,y_1,\ldots,y_k) = G(0,x,y_1,\ldots,y_k)\) とおくとき、\(f \in \mathcal{F}_2 \).
    2. 任意の非負整数 \( n \) に対して、\(k\) 変数関数 \( g_n(y_1,\ldots,y_k):=G(n+1,0,y_1,\ldots,y_k)\) は
      \(\quad (1+k) \) 変数関数 \( \varphi_{n}(x,y_1,\ldots,y_k):=G(n,x,y_1,\ldots,y_k)\) および
      \(\quad \mathcal{F}_2\) の元 
      の合成により得られる.
    3. 任意の非負整数の組 \( (n,x) \) に対して、\(k\) 変数関数 \( h_{n,x}(y_1,\ldots,y_k):=G(n+1,x+1,y_1,\ldots,y_k)\) は
      \(\quad k\) 変数関数 \( \psi_{n,x}(y_1,\ldots,y_k):=G(n+1,x,y_1,\ldots,y_k)\)、
      \(\quad (1+k) \) 変数関数 \(\varphi_{n}(x,y_1,\ldots,y_k)=G(n,x,y_1,\ldots,y_k)\) および
      \(\quad \mathcal{F}_1\) の元
      の合成により得られる.

そして、\(\mathcal{F}_2\) の元だが \(\mathcal{F}_1\) の元ではないものを2重帰納関数と呼びます。□


注釈

wikipediaの定義(Robinsonによる) を参考にしているのですが、ふぃっしゅっしゅさんにより2つの問題点を指摘されていました

  • 原始帰納の繰り返し、という定義が明記されていません。
  • また、二重帰納の繰り返しも二重帰納となる、とも書かれていません。

その後再びふぃっしゅっしゅさんにより、この定義は『二重帰納関数の定義というよりは、二重帰納作用素の定義であると考えればいいのかな?』ということになりました。\(\mathcal{F}_2\) の公理の3番目は、『\(\mathcal{F}_2\) が二重帰納作用素によって閉じている』ということを表していると解釈できると思います。

2重帰納関数の具体例

以下、いくつかのよく知られた具体例について実際に先ほど定義した2重帰納関数の定義をみたしていることを示そうと思います。\(\mathcal{F}_2\)に入ってることしか言っておらず、\(\mathcal{F}_1\) に入ってないことは示してないので厳密には「高々2重帰納関数である」ことの証明になっております。

アッカーマン関数

\(2\) 変数アッカーマン関数 \(A(n,x)\) が公理1. ~ 3. をみたすことをチェックします。1. は\(f(n)=A(0,n)=n+1\) からわかります。2. は \(g_n=A(n+1,0)=A(n,1)=\varphi_n(1)\) よりわかります。3. は\(h_{n,x}=A(n+1,x+1)=A(n,A(n+1,x))=\varphi_n(\psi_{n,x})\) よりわかります。

ゆえに \(A(n,x) \in \mathcal{F}_2\) です。

急増加関数 \(f_\omega(x) \)

急増加関数 は順序数 \(\alpha\) とその基本列 \(\alpha[n]\) が与えられるごとに定義される1変数関数 \(f_\alpha(x)\) です。とくに \(\alpha=\omega\) で、 \(\omega\) の基本列を \(\omega[n]=n\) としたときには \(f_{\omega}(x)\) は次で定められます(具体的な計算例はlimitofemptyさんのブログ を参照)。

  • \(f_0(x) = x + 1\)
  • \(f_{n+1}(x) = f_n^x(x)\)
  • \(f_\omega(x) = f_x(x)\)

\(f_\omega(x)\in\mathcal{F}_2\) であることを示します。

そのために、3変数関数 \(F(m,n,x):=f_m^n(x)\) を導入します。 \(f_\omega(x)=f_x(x)=F(x,1,x)\) なので、\(F(m,n,x)\in\mathcal{F}_2\) であることを示せば十分です。実際、 \begin{eqnarray*} F(0,n,x) &=& f_0^n(x) = x+n, \\ F(m+1,0,x) &=& f_{m+1}^0(x)=x, \\ F(m+1,n+1,x) &=& f_{m+1}^{n+1}(x)=f_{m+1}(f_{m+1}^n(x)) \\ &=& f_{m+1}(F(m+1,n,x))=f_m^{F(m+1,n,x)}(F(m+1,n,x)) \\ &=& F(m,F(m+1,n,x),F(m+1,n,x)) \\ \end{eqnarray*}  ですので、\(\mathcal{F}_2\) の定義より \(F(m,n,x)\in\mathcal{F}_2\) です。

チェーン関数

チェーン関数も上記の定義で2重帰納関数(特に、「2重帰納作用素を繰り返し施してできる2重帰納関数」)になることを示します。 自然数\(n\)に対して、長さ \(n\) のチェーン関数 \(C_n\) を次で定めます。 \[C_n(x_1,x_2,\ldots,x_n) =(x_n +1) \to \ldots \to (x_2 +1) \to (x_1 +1)。  \] この先の表記の都合により変数の順番を逆転させています。また、チェーンは1以上の数に対してしか定義されていなかったので、各\(x_i\)を1だけずらしています。 このとき『全ての自然数 \(n\) に対して、\(C_n \in \mathcal{F}_2\)』であることを、\(n\) に関する帰納法で示します。

[STEP1] \(n=1,2\) のとき: \(C_1(x)=x+1\), \(C_2(x,y)=(y+1)\to(x+1)=(y+1)^{(x+1)}\) だから、\(C_1,C_2 \in \mathcal{F}_1\)。 よって1. より \( C_1,C_2 \in \mathcal{F}_2\)。


[STEP2] \(n=3\) のとき(このステップは本当は必要ないが、見易さのため示します): \( C_3 \in \mathcal{F}_2\) を示します。 \[ C_3(x,y,z)=(z+1)\to(y+1)\to(x+1) \] だから、チェーンの定義より、次がわかります。

  • \( C_3(0,y,z)=(z+1)\to(y+1)\to 1=(z+1)\to(y+1)=C_2(y,z) \)
  • \( C_3(x+1,0,z)=(z+1)\to 1 \to (x+2)=z+1=C_1(z) \)
  • \( C_3(x+1,y+1,z) =(z+1)\to(y+2)\to(x+2) \) \( =(z+1)\to( (z+1)\to(y+1)\to(x+2) ) \to(x+1) \) \( =C_3(x,C_3(x+1,y,z)-1,z) \) \( =C_3(x,p(C_3(x+1,y,z)),z)\)

但し \(p(n)\) は前者関数(\(p(0)=0, p(n+1)=n \))で、原始帰納関数であることが知られています。これらを\( f,g,h,\varphi,\psi\) を使って書き換えると、

  • \( f(y,z)=C_2(y,z) \)
  • \( g_x(z)= C_1(z) \)
  • \( h_{x,y}(z) = \varphi_x(p(\psi_{x,y}(z)),z) \)

となります。 [STEP1]により \( C_1,C_2 \in \mathcal{F}_2\) がわかっているので、\(3\) 変数関数 \(C_3\) は公理1. ~3. をみたすことがわかりました。よって、\(C_3 \in \mathcal{F}_2\) が示されました。

[STEP3] \(n\ge 3\) に対して \(C_{n-2}, C_{n-1} \in \mathcal{F}_2 \) を仮定します。このとき \(C_{n} \in \mathcal{F}_2\) を示します。 [STEP2]のときと同様のノリで、

  • \(C_{n}(0,x_2,\ldots,x_n) =(x_n+1)\to \cdots \to(x_2+1)\to 1\) \(=(x_n+1)\to \cdots \to(x_2+1) =C_{n-1}(x_2,\ldots,x_n) \)
  • \( C_{n}(x_1+1,0,x_3,\ldots,x_{n}) =(x_{n}+1)\to \cdots \to(x_3+1) \to 1 \to (x_1+2)\) \( = (x_{n}+1)\to \cdots \to(x_3+1) = C_{n-2}(x_3,\ldots,x_{n}) \)
  • \( C_{n}(x_1+1,x_2+1,x_3,\ldots,x_n)\) \(= (x_n +1)\to \cdots \to (x_3+1) \to (x_2 +2) \to (x_1 +2) \) \(= (x_n +1)\to \cdots \to (x_3+1) \) \( \to ((x_n +1)\to \cdots \to (x_3+1) \to (x_2 +1) \to (x_1 +2))\) \( \to (x_1 +1) \) \(=C_n(x_1, p(C_n(x_1 +1,x_2,x_3,\ldots,x_n)) ,x_3,\ldots,x_n) \) \( =g_{x_1,x_3,\ldots,x_n}(p(C_n(x_1 +1,x_2,x_3,\ldots,x_n)) ) \)

が得られます。これらを\( f,g,h,\varphi,\psi\) を使って書き換えると、

  • \( f(x_2,\ldots,x_n) = C_{n-1}(x_2,\ldots,x_n) \)
  • \( g_{x_1}(x_3,\ldots,x_n) = C_{n-2}(x_3,\ldots,x_{n}) \)
  • \( h_{x_1,x_2}(x_3,\ldots,x_n) = \varphi_{x_1}(p(\psi_{x_1,x_2}(x_3,\ldots,x_n)),x_3,\ldots,x_n) \)

となります。仮定より  \(C_{n-2}, C_{n-1} \in \mathcal{F}_2 \) なので、\(n\) 変数関数 \(C_n\) は公理1. ~3. をみたすことがわかりました。よって、\(C_n \in \mathcal{F}_2\) が示されました。

[STEP4] 以上により、『全ての自然数 \(n\) に対して、\(C_n \in \mathcal{F}_2\)』であることが示されました。■

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


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

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

FANDOMでも見てみる

おまかせWiki