FANDOM


以下、一部計算ミスがあります。現在修正中です。

以前に書いた User_blog:Limitofempty/対角化と支配する からの続きです。超限帰納法による急増加関数を詳細に追います。

急増加関数の定義は以下のようになっています。

  • \(f_0(x) = x + 1\)
  • \(f_{\alpha+1}(x) = f^x_\alpha(x)\)
  • \(f_\alpha(x) = f_{\alpha[x]}(x)\) (\(\alpha\) が極限順序数の時かつその時に限り)

ここで、\(\alpha = 1\) の時、

\begin{align} f_1(x) &= f_0^x(x) \\ &= x \underbrace{+ 1 + 1 + \cdots + 1}_{x\ times} \\ &= x + x \\ &= 2x \end{align}

となります。加算を行う関数を \(g(x) = x + m\) とすると、任意の \(m\) について \(f_1(x)\) が \(g\) を支配します。その \(m\) を超える \(x\) を与えた時点で、より大きな数となるためです。これにより、あらゆる加算を支配する関数 \(f_1(x)\) の存在がわかります。

次に \(\alpha = 2\) の時、

\begin{align} f_2(x) &= f_1^x(x) \\ &= \underbrace{2 \times 2 \times \cdots \times 2}_{x\ times} \times x \\ &= 2^x x \end{align}

となります。これも同様に、あらゆる乗算を支配しています。冪乗であれば充分なので、最後に \(\times x\) があるのは余計なのですが、あらゆる乗算を支配しているという意味では \(g(x) = 2^x\) とした時の \(g\) と増加程度は同じです。また、自明ではありますが \(f_2\) はこの \(g\) を支配します。すなわち \(f_2 \gg g\) です。

ここ最近の議論の細かいところを追えていないので、現時点で数え上げの well-defined な定義ができているのかいまいち掴めていないのですが、とりあえず「1 つ前の増加程度の関数を \(x\) 回呼び出す引数 \(x\) の関数」という形にすることで、すなわち 1 つ前の増加程度の関数を数え上げることで、急増加関数は順に支配する関数を作り出すという形になっています。

更に \(\alpha = 3\) の時は、関数の中に \(x\) が 2 度出てくるのでかなり複雑な結果になってしまいます。よってここでは割愛しますが、しかし \(g(x) = 2 \uparrow\uparrow x\) とした時の \(g\) と増加程度は同じであり、また \(f_3 \gg g\) です。

これを一般化すると、\(\omega\) よりも小さい任意の順序数 \(n\) について、ハイパー演算子との関係が \(f_n(x) \gg hyper(n + 1)(2, x)\) となります。急増加関数による増加程度の判断は、近似というよりも、単に「ある性質を持ったあらゆる関数を支配する関数であるか」という一点に注目しているということです。User_blog:Mikadukim/多重帰納関数の厳密な定義について や、User_blog:Mikadukim/2重帰納関数の評価_~支配定理に向けて~ で研究が進められている内容は、ある性質を持ったあらゆる帰納関数(たとえば原始帰納関数)を支配する、異なる性質を持った帰納関数(たとえば 2 重帰納関数)を定義しようとするものであると言うことができます。

後で示しますが、急増加関数において 2 重帰納関数に到達するのは、\(f_{\omega}(x)\) からです。定義により、\(\alpha\) が極限順序数の場合は引数 \(x\) によって基本列から任意の順序数を取り出します。しかし \(\omega\) に到達する基本列は、例えば自然数全体の集合 \(0, 1, 2, 3, \cdots\) や、非負奇数全体の集合 \(1, 3, 5, \cdots\) など、様々な取り方が可能です。そこで Wainer 階層によってその基本列の取り方を確定させます。

  • \(\omega[n] = n\)
  • \(\omega^{\alpha + 1}[n] = \omega^\alpha n\)
  • \(\omega^{\alpha}[n] = \omega^{\alpha[n]}\) (\(\alpha\) が極限順序数の時かつその時に限り)
  • \((\omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_{k - 1}} + \omega^{\alpha_k})[n] = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_{k - 1}} + \omega^{\alpha_k}[n]\) (\(\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_{k - 1} \geq \alpha_k\) の場合)
  • \(\epsilon_0[0] = 0\) (もしくは \(1\)) かつ \(\epsilon_0[n + 1] = \omega^{\epsilon_0[n]}\)

最後の「\(\epsilon_0[0] = 0\) (もしくは \(1\))」という部分ですが、要は 0 から開始する論文と 1 から開始する論文がある、というだけのことです。急増加関数も、本質的な部分ではないところで異なる定義(たとえば \(\alpha\) が後続順序数の時に \(f_{\alpha+1}(x) = f^{x+1}_\alpha(x)\) となっているものなど)がいくつも存在しますし、「今はこの定義を使います」と文脈ごとにただ決めてしまえばいいだけのことです。とりあえず今回は \(\epsilon_0\) まで到達しませんから、この細部が異なる 2 つの論文の話を割愛し、今後の解説に回します。

この Wainer 階層にて \(\omega\) に到達する基本列は \(0, 1, 2, 3, \cdots\) と確定し、\(\omega[2] = 2\) となります。これを使って、例えば \(f_{\omega}(2)\) の時、

\begin{align} f_{\omega}(2) &= f_{\omega[2]}(2) \\ &= f_2(2) \\ &= f_1^2(2) \\ &= \underbrace{2 \times 2}_{2\ times} \times 2 \\ &= (2^2) 2 \\ &= 8 \end{align}

となります。\(x = 3\) からは計算が急に煩雑になりますが、

\begin{align} f_{\omega}(3) &= f_{\omega[3]}(3) \\ &= f_3(3) \\ &= f_2^3(3) \\ &= f_2^2((2^3)3) \\ &= f_2^2(24) \\ &= f_2((2^{24})24) \\ &= f_2(402653184) \\ &= (2^{402653184})402653184 \\ &\approx 6.895080597277195 \times 10^{121210694} \end{align}

このように、\(f_{\omega}(x)\) は、引数である \(x\) の値によって、ハイパー演算子の段階を上がっていくことで支配の段数を変数化したということになります。Mikadukim さんへの説明でも色々と書きましたが、原始帰納関数は支配の段数を上がっていく操作(原始帰納作用素)を定数回しか扱うことしかできません。しかし \(f_{\omega}(x)\) を使うことで、原始帰納作用素による支配の段数を変数化した帰納関数を定義できます。よってこの \(f_{\omega}\) は原始帰納関数では定義できず、2 重帰納関数です。

次に s(n)変換です。定義は以下のようになっています。

\begin{align} s(1)f &:= g; g(x)=f^x(x) \\ s(n)f &:= g; g(x)=[s(n-1)^x]f(x) (n>1) \end{align}

これは汎関数、つまり関数を変数に取る関数ですから、変数 \(f\) に関数が与えられることで計算結果が確定します。ここで、\(f(x) = x + 1\) として、s(1) 変換を次のように計算できます。

\begin{align} s(1)f(x) &= f^x(x) \\ &= x+x \\ &= 2x \end{align}

結果は \(2x\) ですから、これは \(f_1(x)\) と同じ関数です。すなわちあらゆる加算関数を支配する関数であるということです。更に \(s(1)^{2}f(x) = (2^x)x\) ですから、これもまた \(f_2(x)\) と同じ関数です。急増加関数と関数の定義が一致していますから、これを一般化すると、\(s(1)^{n}f(x) = f_n(x)\) となります。この \(n\) は定数です。

次に s(2) 変換は s(1) 変換を数え上げますから、

\begin{align} s(2)f(x) &= s(1)^{x}f(x) \\ &= f_x(x) \\ &= f_{\omega}(x) \end{align}

となります。

ここで \(\omega\) よりも大きな極限順序数による急増加関数について見ていきます。\(\omega\) よりも大きな最小の極限順序数は \(\omega \times 2\) です。Wainer 階層の規則のうち

  • \((\omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_{k - 1}} + \omega^{\alpha_k})[n] = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_{k - 1}} + \omega^{\alpha_k}[n]\) (\(\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_{k - 1} \geq \alpha_k\) の場合)

により、

\[ (\omega \times 2)[n] = (\omega^1 + \omega^1)[n] = \omega^1 + \omega^1[n] = \omega + n \]

となり、急増加関数において \(\omega \times 2\) に到達するための基本列は \(\omega + 0, \omega + 1, \omega + 2, \cdots\) を用いることになります。よって例えば、\(f_{\omega \times 2}(3)\) は次のようになります。

\begin{align} f_{\omega \times 2}(3) =& f_{(\omega + \omega)[3]}(3) \\ =& f_{\omega + 3}(3) \\ =& f_{\omega + 2}^{3}(3) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 2}(3))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 2}(3))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 1}^3(3))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 1}(f_{\omega + 1}(f_{\omega + 1}(3))))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 1}(f_{\omega + 1}(f_{\omega}^3(3))))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 1}(f_{\omega + 1}(f_{\omega}(f_{\omega}(f_{\omega}(3))))))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 1}(f_{\omega + 1}(f_{\omega}(f_{\omega}((2^{402653184})402653184)))))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 1}(f_{\omega + 1}(f_{\omega}(f_{(2^{402653184})402653184}((2^{402653184})402653184)))))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 1}(f_{\omega + 1}(f_{\omega}(f_{(2^{402653184})402653184-1}^{(2^{402653184})402653184}((2^{402653184})402653184)))))) \\ & \vdots \\ \end{align}

数をそのまま記述するのが困難なレベルになっていますが、\((\omega + \omega)[3]\) の右の \(\omega\) が \(\omega[3] = 3\) となっており、そこからの計算が爆発しています。そこについては、\(f_3 \gg g; g(x) = 2 \uparrow\uparrow x\) であることを考えれば、なるべくしてなるといった大きさであることがわかります。

また、これは 2 重帰納関数である \(f_\omega\) を数え上げています。すなわち、\(f_\omega\) の羃の回数が引数によって変化しています。よって \(f_{\omega \times 2}\) は、あらゆる 2 重帰納関数を支配する 3 重帰納関数です。

これを s(n) 変換と対応付けると次のようになります。

\begin{array}{l} f_{\omega \times 2}(3) &= f_{(\omega + \omega)[3]}(3) &= s(2)^{2}f(3) \\ &= f_{\omega + 3}(3) &= s(2)s(1)^{3}f(3) \\ &= f_{\omega + 2}^{3}(3) &= s(2)s(1)^{2}f^{3}(3) \\ &= f_{\omega + 1}^{27}(3) &= s(2)s(1)^{1}f^{27}(3) \\ &= f_{\omega}^{7625597484987}(3) &= s(2)f^{7625597484987}(3) \\ && \vdots \end{array}

s(2) 変換を 1 つずつ s(1) 変換の数え上げに、s(1) 変換を 1 つずつ関数 \(f\) の数え上げにしています。

次に \(f_{\omega \times 3}(3)\) について対応付けを行ないます。急増加関数における基本列は、Wainer 階層により \(\omega \times 2, \omega \times 2 + 1, \omega \times 2 + 2, \cdots\) と与えられます。

\begin{array}{l} f_{\omega \times 3}(3) &= f_{(\omega \times 2 + \omega)[3]}(3) &= s(2)^{3}f(3) \\ &= f_{\omega \times 2 + 3}(3) &= s(2)^{2}s(1)^{3}f(3) \\ &= f_{\omega \times 2 + 2}^{3}(3) &= s(2)^{2}s(1)^{2}f^{3}(3) \\ &= f_{\omega \times 2 + 1}^{27}(3) &= s(2)^{2}s(1)^{1}f^{27}(3) \\ &= f_{\omega \times 2}^{7625597484987}(3) &= s(2)^{2}f^{7625597484987}(3) \\ && \vdots \end{array}

この \(f_{\omega \times 3}(x)\) は 4 重帰納関数です。

以下同様に続き、これを一般化することで \(f_{\omega \times n}(x) = s(2)^{n}f(x)\) となります。また、\(f_{\omega^2}(x) = s(2)^{x}f(x) = s(3)f(x)\) です。また、これは関数の帰納程度そのものを変数化しています。すなわち、任意の自然数 \(n\) について、\(n\) 重帰納関数よりも大きな帰納程度となる \(x\) が存在します。よって、\(f_{\omega^2}(x)\) はあらゆる \(n\) 重帰納関数を支配する関数です。

更に s(3) 変換について以下のように対応付けることができます。Wainer 階層に基いて極限順序数を超限帰納法で展開していく過程に注目してください。

\begin{array}{l} f_{\omega^2 \times 2}(3) &= f_{(\omega^2 + \omega^2)[3]}(3) &= s(3)^{2}f(3) \\ &= f_{\omega^2 + \omega^{2}[3]}(3) \\ &= f_{\omega^2 + \omega^{1} \times 3}(3) &= s(3)s(2)^{3}f(3) \\ &= f_{(\omega^2 + \omega^{1} \times 3)[3]}(3) \\ &= f_{\omega^2 + (\omega^{1} \times 3)[3]}(3) \\ &= f_{\omega^2 + (\omega^{1} \times 2 + \omega^{1})[3]}(3) \\ &= f_{\omega^2 + \omega \times 2 + \omega[3]}(3) \\ &= f_{\omega^2 + \omega \times 2 + 3}(3) &= s(3)s(2)^{2}s(1)^{3}f(3) \\ &= f_{\omega^2 + \omega \times 2}^{7625597484987}(3) &= s(3)s(2)^{2}f^{7625597484987}(3) \\ && \vdots \end{array}

こうして、以下同様にすることで \(f_{\omega^2 \times n}(x) = s(3)^{n}f(x)\) となり、また \(f_{\omega^3}(x) = s(3)^{x}f(x) = s(4)f(x)\) です。

これを更に一般化すると、\(f_{\omega^{n}}(x) = s(n)^{x}f(x) = s(n + 1)f(x)\) となり、\(f_{\omega^{\omega}}(x) = s(x + 1)f(x)\) となります。ここまでは s(n) 変換と急増加関数が完全に一致します。

これが急増加関数に Wainer 階層を導入して計算する方法です。

ふぃっしゅ数バージョン3 は \(f_{(\omega^{\omega+1})63+1}(63)\) と示されていますが、この余計な \(+ 1\) は、今回示した s(x+1) の部分が ss(n) 変換で s(x) になってしまい、急増加関数とずれてしまうためです。引数が \(x\) ではなく \(63\) になっており、これは数であるため、厳密な近似のために \(+1\) を加えることには意味があると思います。

関数の話であれば、数え上げている(1 つ前の増加程度の関数の繰り返しを変数化している)以上、結局はその変数に与える数をより大きくすることで、やはりそれより弱いあらゆる関数を支配する構造になり、あまり大きな問題ではなくなります。というのも、s(n) 変換や ss(n) 変換の場合は急増加関数で厳密に等価なものを定義できるというだけで、関数によっては厳密に等価なものを作ることが困難になり、単に支配関係を示す目的で急増加関数を用いたほうが良いためです。但し、関数の性質をより良く理解する目的で、より細かい支配関係を洗い出すことはとても有益だと思います。

余談

古い下書きの段階で、ふぃっしゅっしゅさんにご指摘いただいてました。ありがとうございます。

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


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

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

FANDOMでも見てみる

おまかせWiki