緩成長階層

在可計算性理論、計算複雜性理論和證明理論中，緩成長階層是緩成長函數g_α: N → N的序數索引族（其中N是自然數集合, {0, 1, ... }）。緩成長階層的增長率與急成長階層形成鮮明對比。

定義

令 μ 為一個大的可數序數，以便將基本序列分配給每個小於 μ 的極限序數。函數g_α: N → N的緩成長階層（對於α<μ）定義如下：

• $g_{0}(n)=0$
• $g_{\alpha +1}(n)=g_{\alpha }(n)+1$
• 對於極限序數α，$g_{\alpha }(n)=g_{\alpha [n]}(n)$。

這裡， α[n] 表示分配給極限序數 α 的基本序列的第n個元素。

關於急成長階層的文章描述了所有 α<ε₀ 的基本序列的標準化選擇。

例

• $g_{1}(n)=1$
• $g_{m}(n)=m$
• $g_{\omega }(n)=n$
• $g_{\omega +m}(n)=n+m$
• $g_{\omega m}(n)=mn$
• $g_{\omega ^{m}}(n)=n^{m}$
• $g_{\omega ^{\omega }}(n)=n^{n}$
• $g_{\varepsilon _{0}}(n)=n\uparrow \uparrow n$

與急成長階層的關係

對於較小的索引，緩成長階層比急成長階層增長得慢得多。即使g_ε0也只相當於f₃，並且當α達到巴赫曼-霍華德序數時，g_α也只能達到f_ε0的增長率。皮亞諾算術無法證明偏函數結構中的第一個函數。

然而與之形成鮮明對比的是，吉拉德證明，緩成長階層最終會趕上急成長階層。具體來說，存在一個序數α使得對於所有整數n

g_α(n)<f_α(n)<g_α(n+1)

其中f_α是急成長階層中的函數。他進一步表明，第一個使之成立的α，是歸納定義的任意有限迭代的理論ID_<ω的序數。然而，對於中發現的基本序列的分配，第一次匹配發生在ε₀級別。對於Buchholz風格的樹序數，可以證明第一次匹配甚至發生在$\omega ^{2}$ 。

將證明的結果擴展到相當大的序數表明，低於超限迭代序數的序數非常少$\Pi _{1}^{1}$ -理解緩成長階層和急成長階層相匹配的情況。

緩成長階層極其敏感地依賴於底層基本序列的選擇。

參考

• Gallier, Jean H. What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory. Ann. Pure Appl. Logic. 1991, 53 (3): 199–260. MR 1129778. doi:10.1016/0168-0072(91)90022-E.  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".)