緩増加関数 (SGH; slow-growing hierarchy) は順序数\(\alpha\)に対し関数\(g_\alpha: \mathbb{N} \rightarrow \mathbb{N}\)を定義する一連の階層である。名前が示す通り、急増加関数やハーディー階層よりもより遅く成長する。
関数は次のように定義される:
- \(g_0(n) = 0\)
- \(g_{\alpha+1}(n) = g_\alpha(n)+1\)
- \(g_\alpha(n) = g_{\alpha[n]}(n)\) (\(\alpha\)は極限順序数)
ただし\(\alpha[n]\)は順序数\(\alpha\)の基本列の\(n\)番目の項を表す。\(\alpha[n]\)の定義は一意でないため、上記の定義は基本列を１つに定めて初めて意味を持ち、異なる基本列に対して異なる緩増加関数ができる。例えば、ワイナー階層の基本列は急増加関数の項で説明されている。
小さな順序数に対しては、SGHはFGHから完全に離れている。ワイナー階層の基本列に関する \(g_{\varepsilon_0}(n)\) はようやく \(f_3(n)\) 程度で、ワイナー階層の基本列に関する \(f_{\varepsilon_0}(n)\) にSGHが追い付くのは基本列次第でバッハマン・ハワード順序数などになる。他の順序数階層と比べると、SGHは基本列の定義の変化に極めて敏感である。何らかの自然な基本列に関してSGHはFGHに初めて追いつく順序数（catching ordinal）はブーフホルツのψ関数を用いて\(\psi_0(\Omega_\omega)\)と表せると英語版の記事に書かれており英語版コミュニティでしばしば事実として述べられるが、追いつくことの定義が固定されておらずまた固定した定義での証明も知られていない。
追いつくことの定義と基本列の次第では、最小の catching ordinal は \(\varepsilon_0\)[1]や大ヴェブレン順序数あるいは竹内・フェファーマン・ブーフホルツ順序数よりも大きい順序数となるため、追いつくことの定義と基本列の指定なく「最小のcatching ordinalが\(\psi_0(\Omega_{\omega})\)である」と述べるのは典型的な誤りである。
巨大数論者にとって、SGHはFGH程には使いにくい。SGHは順序数階層の中で最も遅く成長することから、基本列が適切に指定されれば、関数の増加速度を階層化するのに最適なのかもしれない。しかし、グッドスタイン数列と同様に急増加関数を作ることができるということが理論化されている。
関数[]
以下は何かしらの基本列を用いた比較である。上述したようにSGHの増大度は基本列に強く依存するため、この比較が常に正しい保証はない。
\(\Gamma_0\)まで[]
\(g_0(n) = 0\)
\(g_1(n) = 1\)
\(g_2(n) = 2\)
\(g_m(n) = m\)
\(g_\omega(n) = n\)
\(g_{\omega^{\omega}}(n) = n^n\)
\(g_{\omega^{\omega^{\omega}}}(n) = n^{n^{n}}\)
\(g_{\varepsilon_0}(n) = n \uparrow\uparrow n\) (ε₀を参照)
\(g_{\varepsilon_1}(n) \approx n \uparrow\uparrow (2n)\)
\(g_{\varepsilon_2}(n) \approx n \uparrow\uparrow (3n)\)
\(g_{\varepsilon_{\omega}}(n) \approx n \uparrow\uparrow (n^2)\)
\(g_{\varepsilon_{\omega^2}}(n) \approx n \uparrow\uparrow (n^3)\)
\(g_{\varepsilon_{\omega^3}}(n) \approx n \uparrow\uparrow (n^4)\)
\(g_{\varepsilon_{\omega^{\omega}}}(n) \approx n \uparrow\uparrow (n^n)\)
\(g_{\varepsilon_{\varepsilon_0}}(n) \approx n \uparrow\uparrow (n \uparrow\uparrow n)\)
\(g_{\zeta_0}(n) \approx n \uparrow\uparrow\uparrow n\)
\(g_{\varepsilon_{\zeta_0+1}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow n\)
\(g_{\varepsilon_{\zeta_0+2}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow (2n)\)
\(g_{\varepsilon_{\zeta_0 2}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow n) \approx n \uparrow\uparrow\uparrow (n+1)\)
\(g_{\varepsilon_{\zeta_0 3}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow (2(n \uparrow\uparrow\uparrow n))\)
\(g_{\varepsilon_{\zeta_0 4}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow (3(n \uparrow\uparrow\uparrow n))\)
\(g_{\varepsilon_{\zeta_0 \omega}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow (n(n \uparrow\uparrow\uparrow n))\)
\(g_{\varepsilon_{\zeta_0^2}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow ({(n \uparrow\uparrow\uparrow n)}^2)\)
\(g_{\varepsilon_{\zeta_0^{\zeta_0}}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow ({(n \uparrow\uparrow\uparrow n)}^{n \uparrow\uparrow\uparrow n})\)
\(g_{\varepsilon_{\varepsilon_{\zeta_0+1}}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow ((n \uparrow\uparrow\uparrow n) \uparrow\uparrow n)\)
\(g_{\varepsilon_{\varepsilon_{\zeta_0 2}}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow ((n \uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow n)) \approx n \uparrow\uparrow\uparrow (n+2)\)
\(g_{\varepsilon_{\varepsilon_{\varepsilon_{\zeta_0+1}}}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow ((n \uparrow\uparrow\uparrow n) \uparrow\uparrow ((n \uparrow\uparrow\uparrow n) \uparrow\uparrow n))\)
\(g_{\zeta_1}(n) \approx n \uparrow\uparrow\uparrow 2n\)
\(g_{\zeta_2}(n) \approx n \uparrow\uparrow\uparrow 3n\)
\(g_{\zeta_\omega}(n) \approx n \uparrow\uparrow\uparrow n^2\)
\(g_{\zeta_{\omega^\omega}}(n) \approx n \uparrow\uparrow\uparrow n^n\)
\(g_{\zeta_{\varepsilon_0}}(n) \approx n \uparrow\uparrow\uparrow (n \uparrow\uparrow n)\)
\(g_{\zeta_{\varepsilon_{\varepsilon_0}}}(n) \approx n \uparrow\uparrow\uparrow (n \uparrow\uparrow (n \uparrow\uparrow n))\)
\(g_{\zeta_{\zeta_0}}(n) \approx n \uparrow\uparrow\uparrow (n \uparrow\uparrow\uparrow n)\)
\(g_{\zeta_{\zeta_{\zeta_0}}}(n) \approx n \uparrow\uparrow\uparrow (n \uparrow\uparrow\uparrow (n \uparrow\uparrow\uparrow n\)))
\(g_{\eta_0}(n) \approx n \uparrow\uparrow\uparrow\uparrow n\)
\(g_{\varepsilon_{\eta_0+1}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow n\)
\(g_{\varepsilon_{\eta_0+2}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow 2n\)
\(g_{\varepsilon_{\eta_0+\omega}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow n^2\)
\(g_{\varepsilon_{\eta_0+\omega^\omega}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow n^n\)
\(g_{\varepsilon_{\eta_0+\varepsilon_0}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow n)\)
\(g_{\varepsilon_{\eta_0+\varepsilon_{\varepsilon_0}}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow n \uparrow\uparrow n)\)
\(g_{\varepsilon_{\eta_0+\zeta_0}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow n)\)
\(g_{\varepsilon_{\eta_0+\zeta_1}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow 2n)\)
\(g_{\varepsilon_{\eta_0+\zeta_\omega}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow n^2)\)
\(g_{\varepsilon_{\eta_0+\zeta_{\omega^\omega}}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow n^n)\)
\(g_{\varepsilon_{\eta_0+\zeta_{\zeta_0}}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow n \uparrow\uparrow\uparrow n)\)
\(g_{\varepsilon_{\eta_0 2}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow\uparrow n)\)
\(g_{\varepsilon_{\eta_0 3}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow 2(n \uparrow\uparrow\uparrow\uparrow n)\)
\(g_{\varepsilon_{\eta_0 \omega}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow n-1(n \uparrow\uparrow\uparrow\uparrow n)\)
\(g_{\zeta_{\eta_0+1}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow\uparrow n\)
\(g_{\varphi(4,0)}(n) \approx n \uparrow\uparrow\uparrow\uparrow\uparrow n\)
\(g_{\varphi(5,0)}(n) \approx n \uparrow\uparrow\uparrow\uparrow\uparrow\uparrow n\)
出典[]
- ↑ Weiermann, A (1997). "Sometimes slow growing is fast growing". Annals of Pure and Applied Logic. 90 (1–3): 91–99. doi:10.1016/S0168-0072(97)00033-X