缓成长阶层

在可计算性理论、计算复杂性理论和证明理论中，缓成长阶层是缓成长函数gα: N → N的序数索引族（其中N是自然数集合, {0, 1, ... }）。缓成长阶层的增长率与急成长阶层形成鲜明对比。

 定义 
令 μ 为一个大的可数序数，以便将基本序列分配给每个小于 μ 的极限序数。函数gα: N → N的缓成长阶层（对于α<μ）定义如下：J. Gallier, What's so special about Kruskal's theorem and the ordinal Γ0? A survey of some results in proof theory  (2012, p.63). Accessed 8 May 2023.



 对于极限序数α，。

这里， α[n] 表示分配给极限序数 α 的基本序列的第n个元素。

关于急成长阶层的文章描述了所有 α<ε0 的基本序列的标准化选择。

 例 










 与急成长阶层的关系 
对于较小的索引，缓成长阶层比急成长阶层增长得慢得多。即使gε0也只相当于f3，并且当α达到巴赫曼-霍华德序数时，gα也只能达到fε0的增长率。皮亚诺算术无法证明偏函数结构中的第一个函数。   

然而与之形成鲜明对比的是，吉拉德证明，缓成长阶层最终会赶上急成长阶层。具体来说，存在一个序数α使得对于所有整数n

 gα(n)<fα(n)<gα(n+1)

其中fα是急成长阶层中的函数。他进一步表明，第一个使之成立的α，是归纳定义的任意有限迭代的理论ID<ω的序数。然而，对于中发现的基本序列的分配，第一次匹配发生在ε0级别。对于Buchholz风格的树序数，可以证明第一次匹配甚至发生在 。

将证明的结果扩展到相当大的序数表明，低于超限迭代序数的序数非常少 -理解缓成长阶层和急成长阶层相匹配的情况。 

缓成长阶层极其敏感地依赖于底层基本序列的选择。   

 参考 

  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".)

 笔记 

Category:证明论
Category:递归论