緩成長階層

緩成長階層（かんせいちょうかいそう、英:slow-growing hierarchy）は順序数 α {\displaystyle \alpha } に対し関数 g a : N → N {\displaystyle g_{a}:N\rightarrow N} （ N {\displaystyle N} は自然数）を定義する階層である。名前の通り、急増加階層やハーディー階層よりも遅く成長する。 g 0 ( n ) = 0 {\displaystyle g_{0}(n)=0} g α + 1 ( n ) = g α ( n ) + 1 {\displaystyle g_{\alpha +1}(n)=g_{\alpha }(n)+1} g α ( n ) = g α [ n ] ( n ) {\displaystyle g_{\alpha }(n)=g_{\alpha [n]}(n)} （ α {\displaystyle \alpha } が極限順序数のとき、 α [ n ] {\displaystyle \alpha [n]} は α {\displaystyle \alpha } の n {\displaystyle n} 番目の順序数） g 0 ( n ) = 0 {\displaystyle g_{0}(n)=0} g 1 ( n ) = 1 {\displaystyle g_{1}(n)=1} g m ( n ) = m {\displaystyle g_{m}(n)=m} g ω ( n ) = n {\displaystyle g_{\omega }(n)=n} g ω + 1 ( n ) = n + 1 = f 0 ( n ) {\displaystyle g_{\omega +1}(n)=n+1=f_{0}(n)} g ω + m ( n ) = n + m {\displaystyle g_{\omega +m}(n)=n+m} g ω 2 ( n ) = 2 n = f 1 ( n ) {\displaystyle g_{\omega 2}(n)=2n=f_{1}(n)} g ω m ( n ) = m n {\displaystyle g_{\omega m}(n)=mn} g ω 2 ( n ) = n 2 ≈ f 2 ( n ) {\displaystyle g_{\omega ^{2}}(n)=n^{2}\approx f_{2}(n)} g ω m ( n ) = n m {\displaystyle g_{\omega ^{m}}(n)=n^{m}} g ω ω ( n ) = n n {\displaystyle g_{\omega ^{\omega }}(n)=n^{n}} g ω ω ω ( n ) = n n n {\displaystyle g_{\omega ^{\omega ^{\omega }}}(n)=n^{n^{n}}} g ϵ 0 ( n ) = n ↑↑ n ≈ f 3 ( n ) {\displaystyle g_{\epsilon _{0}}(n)=n\uparrow \uparrow n\approx f_{3}(n)} g ϵ 1 ( n ) ≈ n ↑↑ ( 2 n ) {\displaystyle g_{\epsilon _{1}}(n)\approx n\uparrow \uparrow (2n)} g ϵ 2 ( n ) ≈ n ↑↑ ( 3 n ) {\displaystyle g_{\epsilon _{2}}(n)\approx n\uparrow \uparrow (3n)} g ϵ ω ( n ) ≈ n ↑↑ ( n 2 ) {\displaystyle g_{\epsilon _{\omega }}(n)\approx n\uparrow \uparrow (n^{2})} g ϵ ω 2 ( n ) ≈ n ↑↑ ( 2 ⋅ n 2 ) {\displaystyle g_{\epsilon _{\omega 2}}(n)\approx n\uparrow \uparrow (2\cdot n^{2})} g ϵ ω 2 ( n ) ≈ n ↑↑ ( n 3 ) {\displaystyle g_{\epsilon _{\omega ^{2}}}(n)\approx n\uparrow \uparrow (n^{3})} g ϵ ω ω ( n ) ≈ n ↑↑ ( n n ) {\displaystyle g_{\epsilon _{\omega ^{\omega }}}(n)\approx n\uparrow \uparrow (n^{n})} g ϵ ω ω ω ( n ) ≈ n ↑↑ ( n n n ) {\displaystyle g_{\epsilon _{\omega ^{\omega ^{\omega }}}}(n)\approx n\uparrow \uparrow (n^{n^{n}})} g ϵ ϵ 0 ( n ) ≈ n ↑↑ n ↑↑ n {\displaystyle g_{\epsilon _{\epsilon _{0}}}(n)\approx n\uparrow \uparrow n\uparrow \uparrow n} g ζ 0 ( n ) ≈ n ↑↑↑ n ≈ f 4 ( n ) {\displaystyle g_{\zeta _{0}}(n)\approx n\uparrow \uparrow \uparrow n\approx f_{4}(n)} g ζ 1 ( n ) ≈ n ↑↑↑ ( 2 n ) {\displaystyle g_{\zeta _{1}}(n)\approx n\uparrow \uparrow \uparrow (2n)} g ζ ω ( n ) ≈ n ↑↑↑ ( n 2 ) {\displaystyle g_{\zeta _{\omega }}(n)\approx n\uparrow \uparrow \uparrow (n^{2})} g ζ ω 2 ( n ) ≈ n ↑↑↑ ( n 3 ) {\displaystyle g_{\zeta _{\omega ^{2}}}(n)\approx n\uparrow \uparrow \uparrow (n^{3})} g ζ ω ω ( n ) ≈ n ↑↑↑ ( n n ) {\displaystyle g_{\zeta _{\omega ^{\omega }}}(n)\approx n\uparrow \uparrow \uparrow (n^{n})} g φ ( 3 , 0 ) ( n ) ≈ n ↑ 4 n ≈ f 5 ( n ) {\displaystyle g_{\varphi (3,0)}(n)\approx n\uparrow ^{4}n\approx f_{5}(n)} g φ ( 4 , 0 ) ( n ) ≈ n ↑ 5 n ≈ f 6 ( n ) {\displaystyle g_{\varphi (4,0)}(n)\approx n\uparrow ^{5}n\approx f_{6}(n)} g φ ( ω , 0 ) ( n ) ≈ n ↑ n n ≈ f ω ( n ) {\displaystyle g_{\varphi (\omega ,0)}(n)\approx n\uparrow ^{n}n\approx f_{\omega }(n)} Gallier, Jean H. (1991). “What's so special about Kruskal's theorem and the ordinal Γ0? A survey of some results in proof theory”. Ann. Pure Appl. Logic 53 (3): 199–260. doi:10.1016/0168-0072(91)90022-E. MR1129778. http://stinet.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA290387.  PDF's: part 1 2 3. (In particular part 3, Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)