ゆっくりと成長する階層

計算可能性理論、計算複雑性理論、証明理論において、緩やかに増加する階層とは、緩やかに増加する関数g _α : N → Nの順序付きファミリです（ここで、Nは自然数の集合、{0, 1, ...}）。これは急増加階層とは対照的です。

μを大きな可算順序数とし、μ未満のすべての極限順序数に基本列が割り当てられるとする_。α <μのときの関数gα : N → Nの緩やかに増加する階層は次のように定義される: ^[1]

• ${\displaystyle g_{0}(n)=0}$
• ${\displaystyle g_{\alpha +1}(n)=g_{\alpha }(n)+1}$
• ${\displaystyle g_{\alpha }(n)=g_{\alpha [n]}(n)}$極限順序数αの場合。

ここでα[ n ]は極限順序数αに割り当てられた基本数列の n^{番目の要素を表します。}

急成長階層に関する記事では、すべての α < ε ₀に対する基本シーケンスの標準化された選択について説明します。

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

緩やかに増加する階層は、急激に増加する階層よりもはるかにゆっくりと増加する。αがバッハマン・ハワード順序数であるとき、g ε 0 でさえ f 3 にしか等しくなく、g α は f ε 0 （階層内でペアノ算術が完全で_あることを_証明できない最初_の関数_）の増加にしか達しない。[ ^{2] [3] [4]}

しかし、ジラールは、緩やかに増加する階層が、最終的には急速に増加する階層に追いつくことを証明した。 ^{[2]具体的には、すべての整数}nに対して、

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

ここで、f _{α は}急成長階層の関数である。彼はさらに、これが成り立つ最初の α は、帰納的定義の任意の有限反復の理論ID _{<ωの順序数であることを示した。} ^{[5]しかし、 [3]}で見つかった基本シーケンスの割り当てでは、最初の一致はレベル ε ₀で発生します。^[6] Buchholz スタイルのツリー順序数では、最初の一致は でも発生することが示されました。 ${\displaystyle \omega^{2}}$

^[5]で証明された結果をかなり大きな順序数に拡張すると、無限反復の-理解の順序数より下で、緩やかに増加する階層と急速に増加する階層が一致する順序数はほとんどないことが示される。^[7]${\displaystyle \Pi _{1}^{1}}$

緩やかに成長する階層構造は、基礎となる基本シーケンスの選択に非常に敏感に依存します。^{[6] [8] [9]}

• Gallier, Jean H. (1991). 「クラスカルの定理と順序数 Γ0 の何が特別なのか? 証明理論におけるいくつかの結果の調査」. Ann. Pure Appl. Logic . 53 (3): 199–260. doi :10.1016/0168-0072(91)90022-E. MR  1129778.特に、リンクされたバージョンの 59 ～ 64 ページの「急速に増加する関数と緩やかに増加する関数の階層の概要」を参照してください。