FANDOM


ハーディ階層 (Hardy hierarchy)[1]とは、 順序数\(\alpha\)に対して自然数から自然数への関数\(H_\alpha: \mathbb{N} \rightarrow \mathbb{N}\)を定める順序数による関数の階層である。関数の大きさを評価、比較する時によく用いられる。大きな順序数\(\alpha\)では、\(H_\alpha\)はとても速く成長する。ハーディー階層は、1904年に「A theorem concerning the infinite cardinal numbers」[2]で初めてそれを記述したイギリスの数学者ゴッドフレイ・ハロルド・ハーディの名のもとに名づけられた。急増加関数より知名度は低い。だが、急増加関数よりもより使いやすいこともある。例えば、グッドスタイン数列の項を表現するにはこちらの方が適している。

関数列は次のように定義される:

  • \(H_0(n) = n\)
  • \(H_{\alpha+1}(n) = H_\alpha(n+1)\)
  • \(\alpha\)が極限順序数なら \(H_\alpha(n) = H_{\alpha[n]}(n)\)

\(\alpha[n]\)は\(\alpha\)の基本列の\(n\)番目の項を表す。\(\alpha[n]\)の定義は変えることが可能で、ハーディー階層の異なるバージョンを作ることが出来る。例えば、ワイナー階層は急増加関数の項で説明されている。

次のようにもあらわされる: \(H_{\alpha+\beta}(n) = H_{\alpha}(H_{\beta}(n))\)

ハーディー階層と急増加関数は \(\alpha < \varepsilon_0\) の時に次の関係がある: \(H_{\omega^\alpha}(n) = f_\alpha(n)\)

関数編集

次はハーディー階層と巨大数論的記法との比較である。

\(H_0(n) = n\)

\(H_1(n) = n+1\)

\(H_2(n) = n+2\)

\(H_m(n) = n+m\)

\(H_\omega(n) = 2n\)

\(H_{\omega+1}(n) = 2(n+1) = 2n+2\)

\(H_{\omega+2}(n) = 2(n+2)\)

\(H_{\omega+m}(n) = 2(n+m)\)

\(H_{\omega 2}(n) = 4n\)

\(H_{(\omega 2)+m}(n) = 4(n+m)\)

\(H_{\omega 3}(n) = 8n\)

\(H_{(\omega 3)+m}(n) = 8(n+m)\)

\(H_{\omega m}(n) = (2^m)n\)

\(H_{\omega m+x}(n) = 2^m(n+x)\)

\(H_{\omega^2}(n) = 2^n*n\)

\(H_{\omega^2+1}(n) = 2^{n+1}*(n+1)\)

\(H_{\omega^2+2}(n) = 2^{n+2}*(n+2)\)

\(H_{\omega^2+\omega}(n) = 2^{2n}*(2n)\)

\(H_{\omega^2+\omega 2}(n) = 2^{4n}*(4n)\)

\(H_{(\omega^2) 2}(n) = 2^{2^n*n}*(2^n*n)\)

\(H_{(\omega^2) 3}(n) = 2^{2^{2^n*n}*(2^n*n)}*(2^{2^n*n}*(2^n*n))\)

\(H_{(\omega^2) m}(n) = 2^{H_{(\omega^2) m-1}(n)}*(H_{(\omega^2) m-1}(n))\)

\(H_{\omega^3}(n) \approx n \uparrow\uparrow n\)

\(H_{(\omega^3) 2}(n) \approx n \uparrow\uparrow (n \uparrow\uparrow n)\)

\(H_{\omega^4}(n) \approx n \uparrow\uparrow\uparrow n\)

\(H_{\omega^5}(n) \approx n \uparrow\uparrow\uparrow\uparrow n\)

\(H_{\omega^m}(n) \approx \{n,n,m\}\)

\(H_{\omega^\omega}(n) \approx \{n,n,n\}\)

\(H_{\omega^\omega+1}(n) \approx \{n,n,n+1\}\)

\(H_{\omega^\omega+2}(n) \approx \{n,n,n+2\}\)

\(H_{\omega^\omega+\omega}(n) \approx \{n,n,2n\}\)

\(H_{\omega^\omega+\omega^2}(n) \approx \{n,n,2^n*n\}\)

\(H_{(\omega^\omega) 2}(n) \approx \{n,n,\{n,n,n\}\}\)

\(H_{(\omega^\omega) 3}(n) \approx \{n,n,\{n,n,\{n,n,n\}\}\}\)

\(H_{\omega^{\omega+1}}(n)\) or \(H_{(\omega^\omega) \omega}(n) \approx \{n,n,1,2\}\)

\(H_{\omega^{\omega+2}}(n) \approx \{n,n,2,2\}\)

\(H_{\omega^{\omega+m}}(n) \approx \{n,n,m,2\}\)

\(H_{\omega^{\omega 2}}(n) \approx \{n,n,n,2\}\)

\(H_{\omega^{\omega 2+1}}(n) \approx \{n,n,1,3\}\)

\(H_{\omega^{\omega 2+2}}(n) \approx \{n,n,2,3\}\)

\(H_{\omega^{\omega m+2}}(n) \approx \{n,n,m,3\}\)

\(H_{\omega^{\omega m}}(n) \approx \{n,n,n,m\}\)

\(H_{\omega^{\omega m+x}}(n) \approx \{n,n,x,m+1\}\)

\(H_{\omega^{\omega^2}}(n) \approx \{n,n,n,n\}\)

\(H_{\omega^{\omega^3}}(n) \approx \{n,n,n,n,n\}\)

\(H_{\omega^{\omega^{m-2}}}(n) \approx \{n,m (1) 2\} = m \& n\)

\(H_{\omega^{\omega^m}}(n) \approx \{n,m+2 (1) 2\}\)

\(H_{\omega^{\omega^\omega}}(n) \approx \{n,n+2 (1) 2\}\)

参考サイト 編集

  1. Hardy hierarchy - Wikipedia
  2. Hardy, G. H. (1904), "A theorem concerning the infinite cardinal numbers", Quarterly Journal of Mathematics 35: 87–94.

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


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

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

FANDOMでも見てみる

おまかせWiki