ゆっくりと成長する階層

計算可能性理論、計算複雑性理論、および証明理論において、緩増加階層とは、緩増加関数g _α : N → N（ただし、Nは自然数の集合、{0, 1, ...}）の順序数添字付き族である。これは急増加階層とは対照的である。

意味

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

$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 _{ε ₀}の増加（ペアノ算術では階層内で全関数であることが証明できない最初の関数）に達するのは、 αがバッハマン・ハワード順序数であるときのみです。^[2]^[3]^[4]

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

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

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

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

緩やかに増加する階層構造は、基礎となる基本配列の選択に非常に敏感に依存する。^[6]^[8]^[9]

参考文献

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

注記

^ 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). 2023年5月8日にアクセス。
^ ab ジラール, ジャン＝イヴ(1981). 「Π12論理. I. ディレーター」. Annals of Mathematical Logic . 21 (2): 75– 219. doi : 10.1016/0003-4843(81)90016-4 . ISSN 0003-4843. MR 0656793.
^ ab Cichon (1992). 「終了性証明と計算量特性」. P. Aczel, H. Simmons, S. Wainer (編).証明理論. ケンブリッジ大学出版局. pp. 173– 193.
^ Cichon, EA; Wainer, SS (1983). 「緩やかな成長とグジェゴルチク階層」. The Journal of Symbolic Logic . 48 (2): 399– 408. doi :10.2307/2273557. ISSN 0022-4812. JSTOR 2273557. MR 0704094. S2CID 1390729.
^ ab Wainer, SS (1989). 「緩やかな成長と急速な成長」. The Journal of Symbolic Logic . 54 (2): 608– 614. doi :10.2307/2274873. JSTOR 2274873. S2CID 19848720.
^ ab Weiermann, A (1997). 「時にはゆっくりと成長することが急速に成長する」. Annals of Pure and Applied Logic . 90 ( 1–3 ): 91–99 . doi : 10.1016/S0168-0072(97)00033-X .
^ Weiermann, A. (1995). 「緩やかな増加と急速な増加に関する調査：緩やかな増加関数を急速な増加関数によって非自明に主要化する方法」Archive for Mathematical Logic . 34 (5): 313– 330. doi :10.1007/BF01387511. S2CID 34180265.
^ Weiermann, A. (1999), 「（点ごとの）部分再帰階層の成長速度を遅くする要因は何か？」 Cooper, S. Barry (編) 他『集合と証明』。論理コロキウム '97 招待論文、記号論理学会ヨーロッパ会議、リーズ、英国、1997年7月6日～13日。ケンブリッジ：ケンブリッジ大学出版局。ロンドン数学協会講演録第258巻、403-423ページ。
^ Weiermann, Andreas (2001). 「Γ ₀は極小部分再帰的にアクセス不可能な可能性がある」. Mathematical Logic Quarterly . 47 (3): 397– 408. doi :10.1002/1521-3870(200108)47:3<397::AID-MALQ397>3.0.CO;2-Y.

[1] 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). 2023年5月8日にアクセス。

[girard81-2] ジラール, ジャン＝イヴ(1981). 「Π12論理. I. ディレーター」. Annals of Mathematical Logic . 21 (2): 75– 219. doi : 10.1016/0003-4843(81)90016-4 . ISSN 0003-4843. MR 0656793.

[cichon-3] Cichon (1992). 「終了性証明と計算量特性」. P. Aczel, H. Simmons, S. Wainer (編).証明理論. ケンブリッジ大学出版局. pp. 173– 193.

[wainer83-4] Cichon, EA; Wainer, SS (1983). 「緩やかな成長とグジェゴルチク階層」. The Journal of Symbolic Logic . 48 (2): 399– 408. doi :10.2307/2273557. ISSN 0022-4812. JSTOR 2273557. MR 0704094. S2CID 1390729.

[wainer89-5] Wainer, SS (1989). 「緩やかな成長と急速な成長」. The Journal of Symbolic Logic . 54 (2): 608– 614. doi :10.2307/2274873. JSTOR 2274873. S2CID 19848720.

[weier1997-6] Weiermann, A (1997). 「時にはゆっくりと成長することが急速に成長する」. Annals of Pure and Applied Logic . 90 ( 1–3 ): 91–99 . doi : 10.1016/S0168-0072(97)00033-X .

[weier1995-7] Weiermann, A. (1995). 「緩やかな増加と急速な増加に関する調査：緩やかな増加関数を急速な増加関数によって非自明に主要化する方法」Archive for Mathematical Logic . 34 (5): 313– 330. doi :10.1007/BF01387511. S2CID 34180265.

[weier1999-8] Weiermann, A. (1999), 「（点ごとの）部分再帰階層の成長速度を遅くする要因は何か？」 Cooper, S. Barry (編) 他『集合と証明』。論理コロキウム '97 招待論文、記号論理学会ヨーロッパ会議、リーズ、英国、1997年7月6日～13日。ケンブリッジ：ケンブリッジ大学出版局。ロンドン数学協会講演録第258巻、403-423ページ。

[weier2001-9] Weiermann, Andreas (2001). 「Γ ₀は極小部分再帰的にアクセス不可能な可能性がある」. Mathematical Logic Quarterly . 47 (3): 397– 408. doi :10.1002/1521-3870(200108)47:3<397::AID-MALQ397>3.0.CO;2-Y.