緩成長階層

緩成長階層（かんせいちょうかいそう、英:slow-growing hierarchy）は順序数${\displaystyle \alpha }$に対し関数${\displaystyle g_{a}:N\rightarrow N}$（${\displaystyle N}$は自然数）を定義する階層である。名前の通り、急増加階層やハーディー階層よりも遅く成長する。

定義

${\displaystyle g_{0}(n)=0}$

${\displaystyle g_{\alpha 1}(n)=g_{\alpha }(n) 1}$

${\displaystyle g_{\alpha }(n)=g_{\alpha [n]}(n)}$（${\displaystyle \alpha }$が極限順序数のとき、${\displaystyle \alpha [n]}$は${\displaystyle \alpha }$の${\displaystyle n}$番目の順序数）

出典

• Gallier, Jean H. (1991). “What's so special about Kruskal's theorem and the ordinal Γ₀? 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".)

脚注