缓成长阶层

在可计算性理论、计算复杂性理论和证明理论中，缓成长阶层是缓成长函数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".)