巨大数研究 Wiki
登録
Advertisement

急増加関数 (FGH; Fast-growing hierarchy)[1][2] は、順序数 α に対して自然数から自然数への関数 \( f_\alpha(n) \) を定める順序数による関数の階層である。関数の大きさを評価、比較する時によく用いられる。

定義[]

通常は、次のように定義される。

  • \(\alpha=0\) の場合:\(f_0(n)=n+1\)
  • \(\alpha=\alpha'+1\)の場合:\(f_{\alpha'+1}(n)=f_{\alpha'}^n(n)\)
  • \(\alpha\) が0でない極限順序数の場合:\(f_\alpha(n)=f_{\alpha[n]}(n)\)

ここで \(f_\alpha^k(n)\) とは、関数 \(f_\alpha\) に対する反復合成で、

\(\begin{align}f_\alpha^0(n)&=n\\ f_\alpha^{k+1}(n)&=f_\alpha(f_\alpha^k(n))\end{align}\)

として定義される。\( \alpha[n] \) は、極限順序数 \( \alpha \) の基本列の \( n \) 番目である。後述するように、順序数 \( \alpha \) に対する関数 \( f_\alpha(n) \) は \( \alpha \) 以下の全ての極限順序数の基本列の取り方に依存するため、それらを完全に指定しない限り急増加関数は意味をなさない。

一般の単調増加関数 \( f_0 \) に対する階層は 急反復関数 (fast iteration hierarchy) である。基本列 \( \alpha[n] \) の定義は一通りではなく、基本列の定義によって異なる急増加関数が得られる。

Wainer階層[]

いわゆる Wainer 階層 (ウェイナーかいそう、ワイナーかいそう) は、極限順序数 \( \alpha \leq \epsilon_0 \) に対して次のように帰納的に定義される基本列 \( \alpha[n] \) を用いて定まる急増加関数の階層である[注 1]

  1. \( \omega[n] = n \)
  2. \( \omega^{\alpha + 1}[n] = \omega^\alpha n \)
  3. \( \omega^{\alpha}[n] = \omega^{\alpha[n]} \) ( \(\alpha\) が極限順序数の時かつその時に限り)
  4. \( (\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\) の場合)
  5. \( \epsilon_0[0] = 0 \) (もしくは \(1\) )かつ \( \epsilon_0[n + 1] = \omega^{\epsilon_0[n]} \)

Wainer 階層は最も標準的な急増加関数の階層の1つであり、巨大数研究において基本列の明示なく \( \varepsilon_0 \) 以下の順序数に対する急増加関数が扱われている場合は Wainer 階層を意図している可能性が高い。

たとえば、

\begin{align*}\omega^\omega [n] &= \omega^{\omega[n]} \quad \text{(3.を用いた)}\\&= \omega^n \quad \text{(1.を用いた)}\end{align*}

であるから、Wainer 階層における \(\omega^\omega\)に対する基本列は\(1, \omega, \omega^2, \omega^3, \ldots\) である。また、

\begin{align*}\left(\omega^{\omega^{\omega^\omega}} + \omega^{\omega^{\omega^2+2}} \right)\, [n] &= \omega^{\omega^{\omega^\omega}} + \omega^{\omega^{\omega^2+2}} [n] \quad \text{(4.を用いた)}\\ &= \omega^{\omega^{\omega^\omega}} + \omega^{(\omega^{\omega^2+2}\ )\ [n]} \quad \text{(3.を用いた)} \\&=\omega^{\omega^{\omega^\omega}} + \omega^{(\omega^{(\omega^2+1) +1}\ \ ) \ [n]}\\ &= \omega^{\omega^{\omega^\omega}} + \omega^{(\omega^{\omega^2+1}\ )\ n} \quad \text{(2.を用いた)} \end{align*}

であるから、Wainer 階層における \(\omega^{\omega^{\omega^\omega}} + \omega^{\omega^{\omega^2+2}} \)に対する基本列は \(\omega^{\omega^{\omega^\omega}} +1, \omega^{\omega^{\omega^\omega}} + \omega^{(\omega^{\omega^2+1} )} ,\ \omega^{\omega^{\omega^\omega}} + \omega^{(\omega^{\omega^2+1}) 2} ,\ \omega^{\omega^{\omega^\omega}} + \omega^{(\omega^{\omega^2+1}) 3} ,\ \ldots\) である。

Wainer 階層は ヴェブレン階層(限界はフェファーマン・シュッテの順序数 \(\Gamma_0\))にまで拡張できる[注 2]。基本列が定義される限り、急増加関数を帰納的順序数を通して、 \(\omega_1^\text{CK}\) (チャーチ・クリーネ順序数) にまで拡張することができる。急増加関数はより大きな(従って帰納的でない)順序数にも様々な方法で拡張されるが、巨大数研究においては増大度をはじめとしてあまり多くのことが明らかになってはいない。

近似[]

以下に、いくつかの Wainer 階層による関数と、巨大数で使われる他の表記との比較をする。

いくつか、気をつけることがある。

  • \(f_\alpha(n) > g(n)\) と書かれているときに、その関係は十分に大きい \(n\) に対して成り立つことを意味し、すべての \(n\) に対して成り立つとは限らない。
  • \(m\) は任意の正の整数である。

再帰的な順序数[]

\begin{eqnarray*} f_0(n) &=& n + 1 \\ f_1(n) &=& f_0^n(n) = ( \cdots ((n + 1) + 1) + \cdots + 1) = n + n = 2n \\ f_2(n) &=& f_1^n(n) = 2(2(\ldots 2(2n))) = 2^n n > 2 \uparrow n \\ f_3(n) &>& 2\uparrow\uparrow n \\ f_4(n) &>& 2\uparrow\uparrow\uparrow n \\ f_m(n) &>& 2\uparrow^{m-1} n \\ f_\omega(n) &>& 2\uparrow^{n-1} n = A(n,n) \\ f_{\omega+1}(n) &>& \lbrace n,n,1,2 \rbrace \approx A(1,1,n) \\ f_{\omega+2}(n) &>& \lbrace n,n,2,2 \rbrace \approx A(1,2,n) \\ f_{\omega+m}(n) &>& \lbrace n,n,m,2 \rbrace \approx A(1,m,n) \\ f_{\omega2}(n) &>& \lbrace n,n,n,2 \rbrace \approx A(2,0,n) \\ f_{\omega3}(n) &>& \lbrace n,n,n,3 \rbrace \approx A(3,0,n) \\ f_{\omega m}(n) &>& \lbrace n,n,n,m \rbrace \approx A(m,0,n) \\ f_{\omega^2}(n) &>& \lbrace n,n,n,n \rbrace = \lbrace n,2,1,1,2 \rbrace \approx A(1,0,0,n) \\ f_{\omega^3}(n) &>& \lbrace n,n,n,n,n \rbrace = \lbrace n,2,1,1,1,2 \rbrace \approx A(1,0,0,0,n) \\ f_{\ldots + \omega^3 a_3 + \omega^2 a_2 + \omega a_1 + a_0}(n) &>& \lbrace n,2,a_0+1,a_1+1,a_2+1,a_3+1,\ldots\rbrace \approx A(\ldots, a_3, a_2, a_1, a_0, n) \end{eqnarray*}

ここで \(\uparrow\) は矢印表記であり、\(\text{A}\) は多変数アッカーマン関数であり、\(\lbrace \rbrace\)はBEAFである。

Aeton が、さらに近似精度を高めるための計算をしている[3]

\begin{eqnarray*} f_\omega(n) &<& (n+1)\uparrow^{n-1} (n+1) \\ f_{\omega+m}(n) &>& \lbrace n+1,n+1,m,2 \rbrace \\ f_{\omega^2}(n) &<& \lbrace n+1,n+1,n,n \rbrace \\ \end{eqnarray*}

BEAFはテトレーション配列までは定義されているため上記の比較には意味があるものの、それ以降は定義されていないにもかかわらずGoogology Wikiにおいてしばしば意味のない比較がされることに注意する必要がある。

再帰的でない順序数[]

急増加関数は、すべての再帰的な順序数について定義することが可能である。さらに、そうでない順序数についても可能である。しかしながら、その定義は必然的に計算可能な範疇では扱えない関数を定めるため、解析ははるかに複雑になる。例えば チャーチ・クリーネ順序数 \(\omega_1^\mathrm{CK}\)の基本列で一般的なものはないため、\( f _ { \omega _ 1 ^ \mathrm{CK} } ( n ) \) が特定の基本列の取り方に関してすべての計算可能関数より速く増加するかどうかは自明ではなく、複数の数学者が慎重に考えるべきだとしている。しかしながら、巨大数の愛好者の一部には \( f _ { \omega ^ \mathrm{CK} _ 1 } ( n ) \) は \( \Sigma ( n ) \) を近似すると考える者もいる。そうでない者の中にも計算不可能関数の増大度を測る基準がないことを理由として、以下のような近似式を比喩的に使うものがいる。

\begin{eqnarray*} f _ { \omega _ 1 ^ \mathrm{CK} } ( n ) &\approx& \Sigma _ 1 ( n ) \\ f _ { \omega _ 2 ^ \mathrm{CK} } ( n ) &\approx& \Sigma _ 2 ( n ) \\ f _ { \omega _ 3 ^ \mathrm{CK} } ( n ) &\approx& \Sigma _ 3 ( n ) \\ f _ { \omega _ m ^ \mathrm{CK} } ( n ) &\approx& \Sigma _ m ( n ) \\ \end{eqnarray*}

ここで \( \Sigma _ m ( n ) \) は m-次のビジービーバー関数である。 \( f _ { \omega _ 1 ^ \mathrm{CK} } ( n ) \) が容易に解析できないことと同様に、より一般の許容順序数 (admissible ordinal) と呼ばれる順序数の系列 \( \omega _ m ^ \mathrm{CK} \) に対する急増加関数の解析も非常に困難である。従って上の式もあくまで比喩的な比較であり、数学的な根拠が与えられているわけではない。そもそも左辺の定義に用いる基本列を明確に定める方法も単純ではなく、その信頼性は皆無といっても良い。

関連項目[]

注釈[]

  1. 正確には、前節で定義した急増加関数の定義も含めてWainer階層と呼ばれる (Prömel, Thumser and Voigt, 1991)。
  2. ウェイナーの72年の論文によると、ウェイナー自身は\(\Gamma_0\)まで定義をしたらしいが、その発表に関する詳細は確認できない。また、拡張された急増加関数あるいは急成長階層に関するこれ以外の考察は見受けられない。

参考サイト[]

Advertisement