証明理論では、順序分析は、数学理論の強さの尺度として、順序数(多くの場合、大きな可算順序数)を割り当てます。理論が同じ証明理論的順序を持っている場合、それらはしばしば等矛盾であり、ある理論の証明理論的順序が他の理論よりも大きい場合、多くの場合、2 番目の理論の無矛盾性を証明できます。
理論の証明論的順序数を得ることに加えて、実際には順序分析は通常、分析対象の理論に関するさまざまな他の情報ももたらします。たとえば、理論の証明可能な再帰的、超算術的、または関数のクラスの特性評価などです。[1]
歴史
順序解析の分野は、1934 年にゲルハルト・ゲンツェンがカット除去法を使用して、現代的な言葉で言えば、ペアノ算術の証明論的順序数がε 0であることを証明したときに形成されました。ゲンツェンの無矛盾性証明を参照してください。
意味
順序分析は、順序表記についての記述を行うために算術の十分な部分を解釈できる、真で有効な(再帰的な)理論に関係します。
このような理論の証明論的順序数は、理論が適切であることを証明できるすべての順序表記法(必然的に再帰的、次のセクションを参照)の順序タイプの上限、つまりが順序表記法であることを証明するKleene の意味での表記法が存在するすべての順序数の上限です。同様に、それは、および でそれを適切に順序付ける再帰的関係が(自然数の集合)上に存在し、が に対する算術ステートメントの超限帰納法を証明するようなすべての順序数の上限です。
序数表記
2 階算術のサブシステムなどの一部の理論には、超限順序数についての概念化や議論の方法がありません。たとえば、Z 2のサブシステムが「順序が適切であることを証明する」とはどういうことかを形式化するために、代わりに順序型 を持つ順序表記法を構築します。これで、 に沿ったさまざまな超限帰納原理を処理できるようになり、集合論的順序数についての推論の代わりとなります。
しかし、予想外に扱いが難しい病的な表記法もいくつか存在します。たとえば、Rathjen は、順序型を持っているにもかかわらず、PA が一貫している場合にのみ整基礎となる原始的な再帰表記法システムを示しています[2] p. 3 。このような表記法を PA の順序分析に含めると、誤った等式 が生じます。
上限
順序表記は再帰的でなければならないため、どの理論の証明理論的順序数もチャーチ・クリーネ順序数 以下になります。特に、 矛盾した理論の証明理論的順序数は に等しくなります。これは、矛盾した理論はすべての順序表記が整根拠を持つことを自明に証明するためです。
-公理化可能かつ-健全な理論の場合、理論が整列していることを証明できない再帰的順序の存在は境界定理から導かれ、前述の証明可能な整列順序表記は実際には -健全性によって整列している。したがって、公理化可能な-健全な理論の証明理論的順序は常に(可算な)再帰的順序数、つまり より厳密に小さいとなる。[2]定理 2.21
例
証明論的順序数 ω を持つ理論
- Q、ロビンソン算術(ただし、そのような弱い理論の証明論的順序数の定義は調整する必要がある)[要出典]。
- PA –、離散的に順序付けられた環の非負部分の第一階理論。
証明論的順序数 ω を持つ理論2
- RFA、初歩的な関数演算。[3]
- IΔ 0、指数関数が完全であることを主張する公理のない Δ 0述語に基づく帰納法による算術。
証明論的順序数 ω を持つ理論3
- EFA、基本関数演算。
- IΔ 0 + exp、指数は完全であることを主張する公理によって拡張されたΔ 0述語に基づく帰納法による算術。
- RCA*
0逆数学で時々使用される EFA の 2 次形式。 - ウィキペディア*
0逆数学で時々使用される EFA の 2 次形式。
フリードマンの壮大な予想は、これを証明論的順序数として持つ弱いシステムで多くの「普通の」数学が証明できることを示唆しています。
証明論的順序数 ω を持つ理論ん(のためにん= 2, 3, ...ω)
- IΔ 0または EFA は、 Grzegorczyk 階層のn番目のレベルの各要素が合計であることを保証する公理によって拡張されます。
証明論的順序数 ω を持つ理論ω
- RCA 0、再帰的理解。
- WKL 0、弱いケーニッヒの補題。
- PRA、原始再帰演算。
- IΣ 1、 Σ 1述語に基づく帰納法による算術。
証明論的順序数 ε を持つ理論0
証明論的順序を持つ理論Feferman–Schütte 序数 Γ 0
- ATR 0、算術超限再帰。
- 任意の数の有限レベルの宇宙を持つMartin-Löf 型理論。
この順序数は、「述語的」理論の上限であると考えられることがあります。
証明論的順序を持つ理論バッハマン・ハワード順序
- ID 1、帰納的定義の最初の理論。
- KP、無限公理を持つクリプキ-プラテック集合論。
- CZF、Aczel の構成的 Zermelo–Fraenkel 集合論。
- EON は、 Fefermanの明示的な数学システム T 0の弱い変種です。
クリプキ-プラテック集合論または CZF 集合論は、すべての部分集合の集合として与えられた完全な冪集合に対する公理を持たない弱い集合論です。代わりに、制限された分離と新しい集合の形成の公理を持つか、より大きな関係から切り出すのではなく、特定の関数空間 (累乗) の存在を認める傾向があります。
証明理論的順序数が大きい理論
- , Π 1 1 の内包には、かなり大きな証明論的順序数があり、これは Takeuti によって「順序数図」[5] p. 13で説明され、 Buchholz の表記法ではψ 0 (Ω ω )で制限されます。これは、有限反復帰納的定義の理論である の順序数でもあります。また、MLW、インデックス付き W 型を持つ Martin-Löf 型理論 Setzer (2004) の順序数でもあります。
- ID ω、ω反復帰納的定義の理論。その証明論的順序数はTakeuti-Feferman-Buchholz 順序数に等しい。
- T 0、フェファーマンの明示的数学の構成的システムはより大きな証明論的順序数を持ち、それはまた、反復許容値およびを持つ KPi、クリプキ-プラテック集合論の証明論的順序数でもある。
- KPiは、再帰的にアクセス不可能な順序数に基づくクリプキ-プラテック集合論の拡張であり、1983年のJägerとPohlersの論文で説明されている非常に大きな証明論的順序数を持ち、Iは最小のアクセス不可能な順序数です。[6]この順序数は、の証明論的順序数でもあります。
- KPMは、再帰的マーロ順序数に基づくクリプキ-プラテック集合論の拡張であり、非常に大きな証明論的順序数θを持ち、これはRathjen (1990)によって記述されました。
- TTM は、Martin-Löf 型理論を 1 つの Mahlo 宇宙で拡張したもので、証明論的順序数がさらに大きくなります。
- は証明論的順序数が に等しい。ここで は最初の弱コンパクトを指す。これは (Rathjen 1993) による。
- は に等しい証明論的順序数を持ち、ここで は最初の-記述不可能な を指し、 は(Stegert 2010) により を指します。
- の証明論的順序数は に等しく、ここでは(Stegert 2010) により、すべての およびに対して -安定である最小の順序数の基数類似体です。
自然数のべき集合を記述できる理論のほとんどは、証明論的順序数が非常に大きいため、明示的な組み合わせ記述がまだ与えられていません。これには、、完全な2階算術( )、およびZFとZFCを含むべき集合を持つ集合論が含まれます。直観主義ZF(IZF)の強さは、ZFの強さに等しいです。
順序分析表
鍵
この表で使用されている記号のリストは次のとおりです。
- ψ は、それぞれの引用で定義されているさまざまな順序崩壊関数を表します。
- Ψ は Rathjen の Psi または Stegert の Psi のいずれかを表します。
- φはヴェブレンの関数を表します。
- ω は最初の超限順序数を表します。
- ε α はイプシロン数を表します。
- Γ α はガンマ数を表します (Γ 0はフェフェルマン・シュッテ序数です)
- Ω α は非可算順序数を表します (Ω 1、略して Ω はω 1 )。順序数が証明理論的であるとみなされるためには可算性が必要であると考えられています。
- は安定した順序数を表す順序数項であり、を超える最小の順序数です。
- は、 となる順序数を表す順序項である。N は、 forallの結果の一連の順序数分析を定義する変数である。N=1 のとき、
この表で使用されている略語の一覧は次のとおりです。
- 一次演算
- ロビンソン算術
- 離散的に順序付けられた環の非負部分の第一階理論です。
- 基本的な関数演算です。
- 指数関数が完全であることを主張する公理がなく、帰納法が Δ 0述語に制限された算術です。
- 基本的な関数の算術です。
- 指数関数は、指数関数が完全であることを主張する公理によって拡張されたΔ 0述語に制限された帰納法による算術です。
- は、 Grzegorczyk 階層のn番目のレベルの各要素が完全であることを保証する公理によって拡張された基本的な関数の算術です。
- グジェゴルチク階層のn番目のレベルの各要素が完全であることを保証する公理によって拡張されます。
- は原始的な再帰演算です。
- は、Σ 1述語に制限された帰納法を伴う算術です。
- ペアノ算術です。
- ただし、帰納法は正の式に対してのみ適用されます。
- PA を単調演算子の ν 反復不動点によって拡張します。
- は、正確には一階算術システムではありませんが、自然数に基づく述語的推論によって得られるものを捉えています。
- 自律的に反復されます(つまり、序数が定義されると、それを使用して新しい一連の定義をインデックスできます)。
- PA を単調演算子の ν 反復最小不動点によって拡張します。
- は、厳密には一階算術システムではありませんが、ν 回反復された一般化された帰納的定義に基づく述語的推論によって得られるものを捉えています。
- 自律的に反復されます。
- W型をベースにした弱体化バージョンです。
- は長さ α が -式以下の超限帰納法です。これは、一階算術で使用される順序表記法の表現になります。
- 2階算術
一般に、下付き文字 0 は、帰納法スキームが単一の帰納法公理に制限されていることを意味します。
- は逆数学で時々使用されるの 2 次形式です。
- 逆数学で時々使用されるの 2 次形式です。
- 再帰的理解です。
- は弱いケーニッヒの補題である。
- 算数の理解です。
- 完全な2次誘導スキームが追加されます。
- 算術超限再帰です。
- 完全な2次誘導スキームが追加されます。
- は、 「パラメータを持つすべての真の-文は、(可算コード化された) -モデルで成り立つ」という主張をプラスします。
- クリプキ・プラテック集合論
- 無限公理を伴うクリプキ-プラテック集合論です。
- はクリプキ-プラテック集合論であり、その宇宙は を含む許容集合です。
- W型をベースにした弱体化バージョンです。
- 宇宙は許容される集合の限界であると主張する。
- W型をベースにした弱体化バージョンです。
- 宇宙はアクセス不可能な集合であると主張します。
- 宇宙は超アクセス不可能である、つまりアクセス不可能な集合とアクセス不可能な集合の限界であると主張します。
- 宇宙はマーロ集合であると主張する。
- 特定の一次反射スキームによって拡張されます。
- は、公理によって拡張された KPi です。
- 「少なくとも 1 つの再帰的な Mahlo 順序数が存在する」というアサーションによって拡張された KPI です。
- は、「空でない推移的な集合 M が存在し、それが成り立つ」という公理を伴います。
上付きのゼロは、-induction が削除されたことを示します (理論が大幅に弱くなります)。
- 型理論
- 原始再帰的構成の Herbelin-Patey 計算です。
- W 型がなく、宇宙がある型理論です。
- W 型がなく、有限個の宇宙を持つ型理論です。
- は、次の宇宙演算子を持つ型理論です。
- W 型がなく、超宇宙を持つ型理論です。
- は、W 型を持たない型理論上の自己同型です。
- 1 つの宇宙と Aczel 型の反復集合を持つ型理論です。
- インデックス付き W 型を持つ型理論です。
- W 型と 1 つの宇宙を持つ型理論です。
- W 型と有限個の宇宙を持つ型理論です。
- は、W 型を持つ型理論上の自己同型です。
- は、Mahlo 宇宙を持つ型理論です。
- System F は、多態的ラムダ計算または 2 次ラムダ計算とも呼ばれます。
- 構成的集合論
- アツェルの構成的集合論です。
- 正規拡張公理を加算したものです。
- 完全な2次誘導スキームが追加されます。
- マーロの宇宙です。
- 明示的な数学
- 基本的な明示的な数学と初歩的な理解力を組み合わせたものです
- プラス結合ルール
- プラス結合公理
- はFefermanの弱い変種です。
- は であり、 は誘導生成です。
- は であり、 は完全な 2 次誘導スキームです。
参照
注記
- 1. ^のために
- 2. ^可算無限反復最小不動点を持つヴェブレン関数。 [説明が必要]
- 3. ^一般的にはマドーレの ψ のように表記されることもあります。
- 4. ^ Buchholz の ψ ではなく Madore の ψ を使用します。
- 5. ^一般的にはマドーレの ψ のように表記されることもあります。
- 6. ^ は最初の再帰的に弱コンパクト順序数を表します。Buchholz の ψ ではなく Arai の ψ を使用します。
- 7. ^の証明理論的順序数も、W タイプによって与えられる弱化の量が十分ではないためである。
- 8. ^ は最初の到達不可能な基数を表します。Buchholz の ψ ではなく Jäger の ψ を使用します。
- 9. ^ は- 到達不可能な基数の極限を表します。おそらく Jäger の ψ を使用します。
- 10. ^ は- 到達不可能な基数の極限を表します。おそらく Jäger の ψ を使用します。
- 11. ^ は最初のマーロ基数を表します。ブッフホルツの ψ ではなく、ラトジェンの ψ を使用します。
- 12. ^ は最初の弱コンパクト基数を表します。Buchholz の ψ ではなく Rathjen の Ψ を使用します。
- 13. ^ は最初の- 記述不可能な基数を表します。Buchholz の ψ ではなく Stegert の Ψ を使用します。
- 14. ^ は、 ' は-記述不可能') かつ'は-記述不可能' )となるような最小のものです。Buchholz の ψ ではなく Stegert の Ψ を使用します。
- 15. ^ は最初のマーロ基数を表します。(おそらく) Rathjen の ψ を使用します。
引用
- ^ M. Rathjen、「許容証明理論とその先」。『論理学と数学の基礎研究』第134巻(1995年)、123~147ページ。
- ^ abc Rathjen、「順序分析の領域」。2021年9月29日にアクセス。
- ^ Krajicek, Jan (1995). 有界算術、命題論理、複雑性理論。ケンブリッジ大学出版局。pp. 18–20。ISBN 9780521452052。基本的な集合と基本的な関数を定義し、それらが自然数に対する Δ 0述語と同値であることを証明します。システムの順序分析は、Rose, HE (1984)のSubrecursion: functions and hierarchiesで参照できます。ミシガン大学: Clarendon Press。ISBN 9780198531890。
- ^ abcdef M. Rathjen、「証明理論:算術から集合論へ」(p.28)。2022年8月14日にアクセス。
- ^ Rathjen, Michael (2006)、「序数解析の技術」(PDF)、国際数学者会議、第2巻、チューリッヒ: Eur. Math. Soc.、pp. 45–69、MR 2275588、2009年12月22日時点のオリジナルよりアーカイブ
{{citation}}: CS1 maint: bot: original URL status unknown (link) - ^ D. Madore、A Zoo of Ordinals (2017、p.2)。 2022 年 8 月 12 日にアクセス。
- ^ abcdefg J. Avigad、R. Sommer、「順序分析へのモデル理論的アプローチ」(1997年)。
- ^ M. Rathjen、W. Carnielli、「Hydrae と算術のサブシステム」(1991)
- ^ ジェロン・ファン・デル・メーレン;ラジーン、マイケル。ワイアーマン、アンドレアス (2014)。 「ハワード・バックマン階層の秩序理論的特徴付け」。arXiv : 1411.4481 [math.LO]。
- ^ abcdefghijk G. Jäger、T. Strahm、「序数と基本的理解を伴う二次理論」。
- ^ abcde G. Jäger、「根拠のない許容性の強さ」。Journal of Symbolic Logic vol. 49, no. 3 (1984)。
- ^ B. Afshari、M. Rathjen、「順序分析と無限ラムゼー定理」(2012)
- ^ ab Marcone, Alberto; Montalbán, Antonio (2011). 「計算可能性理論家のためのヴェブレン関数」The Journal of Symbolic Logic . 76 (2): 575–602. arXiv : 0910.5442 . doi :10.2178/jsl/1305810765. S2CID 675632.
- ^ S. Feferman、「数学的実践に関連する有限型の理論」。『数理論理学ハンドブック』、論理学と数学の基礎研究第90巻(1977年)、J. Barwise編、North Holland出版。
- ^ abcd M. Heissenbüttel、「序数強度 と」の理論(2001)
- ^ abcdefg D. Probst、「2 階算術のメタ述語サブシステムのモジュラー順序分析」(2017)
- ^ A. Cantini、「第2階算術における選択原理と理解原理の関係について」、Journal of Symbolic Logic vol. 51 (1986)、pp. 360--373。
- ^ abcd Fischer, Martin; Nicolai, Carlo; Pablo Dopico Fernandez (2020). 「 非古典的な真実と古典的な強さ。HYPE 上の構成的真実の証明理論的分析」。arXiv : 2007.07188 [math.LO]。
- ^ abc SG Simpson、「Friedman の 2 次演算サブシステムに関する研究」。Harvey Friedman の数学基礎に関する研究、Studies in Logic and the Foundations of Mathematics vol. 117 (1985)、L. Harrington、M. Morley、A. Šcedrov、SG Simpson 編、North-Holland 発行。
- ^ J. Avigad、「順序表記法の再帰を使用した許容集合論の順序分析」。Journal of Mathematical Logic vol. 2, no. 1, pp.91--112 (2002)。
- ^ S. Feferman、「反復帰納的固定点理論:ハンコックの予想への応用」。Patras Logic Symposion、Studies in Logic and the Foundations of Mathematics vol. 109 (1982)。
- ^ S. Feferman、T. Strahm、「非有限主義的算術の展開」、Annals of Pure and Applied Logic vol. 104、no.1--3 (2000)、pp.75--96。
- ^ S. Feferman、G. Jäger、「分析における選択原理、バールール、自律反復理解スキーム」、Journal of Symbolic Logic vol. 48、no. (1983)、pp.63--70。
- ^ abcdefgh U. Buchholtz、G. Jäger、T. Strahm、「証明理論的強度の理論 ψ ( Γ Ω + 1 ) {\displaystyle \psi (\Gamma _{\Omega +1})}」。数学、哲学、コンピュータサイエンスにおける証明の概念(2016年)、D. Probst、P. Schuster編。DOI 10.1515/9781501502620-007。
- ^ T. Strahm、「自律的な固定点進行と固定点超限再帰」(2000 年)。Logic Colloquium '98、編者 SR Buss、P. Hájek、P. Pudlák。DOI 10.1017/9781316756140.031
- ^ G. Jäger、T. Strahm、「固定点理論と依存選択」。Archive for Mathematical Logic vol. 39 (2000)、pp.493--508。
- ^ abc T. Strahm、「自律的な固定点進行と固定点超限再帰」(2000)
- ^ abcd C. Rüede、「超限依存選択とω-モデル反射」。Journal of Symbolic Logic vol. 67, no. 3 (2002)。
- ^ abc C. Rüede、「Σ11 超限依存選択の証明理論的分析」。Annals of Pure and Applied Logic vol. 122 (2003)。
- ^ abcd T. Strahm、「メタ述語的マハロのウェルオーダー証明」。Journal of Symbolic Logic vol. 67, no. 1 (2002)
- ^ F. Ranzi、T. Strahm、「小さなヴェブレン序数のための柔軟な型システム」(2019年)。Archive for Mathematical Logic 58: 711–751。
- ^ K. Fujimoto、「反復帰納的定義と内包のいくつかの2次システムと集合論の関連サブシステムに関するノート」。Annals of Pure and Applied Logic、vol. 166 (2015)、pp. 409--463。
- ^ abc Krombholz, Martin; Rathjen, Michael (2019). 「グラフマイナー定理の上限」. arXiv : 1907.00412 [math.LO].
- ^ W. Buchholz、S. Feferman、W. Pohlers、W. Sieg、「反復帰納的定義と分析のサブシステム:最近の証明理論的研究」
- ^ W. Buchholz,非述語的解析サブシステムの証明理論 (証明理論研究、モノグラフ、第 2 巻(1988))
- ^ abcdefghijklmno M. Rathjen、「Π 1 1 − C A {\displaystyle \Pi _{1}^{1}{\mathsf {-CA}}} と Δ 2 1 − C A + B I {\displaystyle \Delta _{2}^{1}{\mathsf {-CA+BI}}} 間の強度における第 2 次算術および集合論のサブシステムの調査: パート I」。2023 年 9 月 21 日にアクセス。
- ^ M. Rathjen、「いくつかの Martin-Löf 型理論の強さ」
- ^ 保守性の結果については、Rathjen (1996)「The Recursively Mahlo Property in Second Order Arithmetic」( Math. Log. Quart.、42)を参照。同じ序数を与える
- ^ ab A. Setzer、「Mahlo 宇宙を持つ型理論のモデル」(1996)。
- ^ M. Rathjen、「反射の証明理論」。Annals of Pure and Applied Logic vol. 68, iss. 2 (1994)、pp.181--224。
- ^ ab Stegert, Jan-Carl、「強い反射原理によって強化されたクリプキ-プラテック集合論の順序証明理論」(2010年)。
- ^ abc 新井 俊康 (2023-04-01). 「順序解析講義」. arXiv : 2304.00246 [math.LO].
- ^ Arai, Toshiyasu (2023-04-07). 「-reflection の Well-foundedness 証明」. arXiv : 2304.03851 [math.LO].
- ^ ab 新井 敏康 (2024-02-12). 「-Collection の順序分析」. arXiv : 2311.12459 [math.LO].
- ^ Valentin Blot. 「更新再帰による2次演算の直接計算解釈」(2022年)。
参考文献
- Buchholz, W.; Feferman, S.; Pohlers, W.; Sieg, W. (1981)、反復帰納的定義と分析のサブシステム、数学講義ノート、第897巻、ベルリン:Springer-Verlag、doi:10.1007/BFb0091894、ISBN 978-3-540-11170-2
- ポーラーズ、ウォルフラム(1989)、証明理論、数学講義ノート、第1407巻、ベルリン:シュプリンガー出版社、doi:10.1007/978-3-540-46825-7、ISBN 3-540-51842-8、MR 1026933
- ポーラーズ、ウォルフラム(1998)「集合論と第2次数論」、証明理論ハンドブック、論理学と数学の基礎研究、第137巻、アムステルダム:エルゼビアサイエンスBV、pp. 210–335、doi:10.1016 / S0049-237X(98)80019-0、ISBN 0-444-89840-9、MR 1640328
- Rathjen, Michael (1990)、「弱 Mahlo 基数に基づく序数表記法」、Arch. Math. Logic、29 (4): 249–263、doi :10.1007/BF01651328、MR 1062729、S2CID 14125063
- Rathjen, Michael (2006)、「順序分析の技術」(PDF)、国際数学者会議、第 2 巻、チューリッヒ: Eur. Math. Soc.、pp. 45–69、MR 2275588、2009 年 12 月 22 日にオリジナルからアーカイブ
{{citation}}: CS1 maint: bot: original URL status unknown (link) - Rose, HE (1984)、「サブ再帰。関数と階層」、オックスフォード ロジック ガイド、第 9 巻、オックスフォード、ニューヨーク: クラレンドン プレス、オックスフォード大学出版局
- シュッテ、クルト (1977)、証明理論、Grundlehren der Mathematischen Wissenschaften、vol. 225、ベルリン-ニューヨーク: Springer-Verlag、pp. xii+299、ISBN 3-540-07911-4、MR 0505313
- Setzer、Anton (2004)、「Martin-Löf 型理論の証明理論。概要」、数学と科学、ヒューメイン。数学と社会科学(165): 59–99
- 竹内ガイシ(1987)「証明理論」『論理学と数学の基礎研究』第81巻(第2版)、アムステルダム:ノースホランド出版社、ISBN 0-444-87943-9、MR 0882549
- ラトジェン、マイケル(1994)、「反射の証明理論」、純粋および応用論理学年報、68(2):181-224、doi:10.1016/0168-0072(94)90074-4
- ステガート、ヤン・カール(2010)、強い反射原理によって強化されたクリプキ・プラテック集合論の順序証明理論
