ハーディ階層 (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]\)の定義は一意でないため、それを1つに定めて初めてこれらの関数が定義される。基本列を変えるごとに、ハーディー階層の異なるバージョンを作ることが出来る。例えば、ワイナー階層の基本列は急増加関数の項で説明されている。

ワイナー階層の基本列においては、以下の性質が成り立つ:

  • \(\alpha + \beta = \gamma + \beta\)かつ\(\gamma < \alpha\)を満たす順序数\(\gamma\)が存在しないような任意の順序数\(\alpha,\beta < \varepsilon\)に対し、\(H_{\alpha+\beta}(n) = H_{\alpha}(H_{\beta}(n))\)である。
  • 任意の \(\alpha < \varepsilon_0\) に対し、\(H_{\omega^\alpha}(n) = f_\alpha(n)\)である。ただし\(f_{\alpha}\)は急増加関数である。

これらはワイナー階層の特殊な性質であるが、しばしばワイナー階層以外にも成立すると誤解されることがあるので注意が必要である。例えば「\(\alpha\)が\(\epsilon\)数であるならば、\(\alpha = \omega^{\alpha}\)なので\(H_{\alpha}(n) = 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\)


参考サイト

  1. Hardy hierarchy - Wikipedia
  2. Hardy, G. H. (1904), "A theorem concerning the infinite cardinal numbers", Quarterly Journal of Mathematics 35: 87–94.
特に記載のない限り、コミュニティのコンテンツはCC-BY-SA ライセンスの下で利用可能です。