巨大数研究 Wiki
Advertisement
巨大数研究 Wiki
巨大数研究 Wiki
583
ページ
分類: 要修正、順序数表記、順序数、証明論

順序数図形

編集するにはログイン


順序数図形 (ordinal diagram, o.d.) は竹内外史が証明論で用いた順序数表記である．例えば\(\mathrm{O}(2,1)\)での\(<_0\)の順序型はバッハマン・ハワード順序数であり，\(\mathrm{O}(\omega+1,1)\)での\(<_0\)の順序型は竹内・フェファーマン・ブーフホルツ順序数である．

概要[]

ゲンツェンが無矛盾性証明の際に証明図から順序数を見出したように，竹内外史は証明図に対応させる順序数表記として順序数図形を考案した[1][2]．後に順序数図形は簡略化できることを指摘され[3]，後は簡略化されたものが用いられることが多い．

竹内は現代的に言えば二階算術の部分体系\(\Pi^1_1\text{-}\mathsf{CA}_0\)の無矛盾性証明[4][5]，そして\(\Pi^1_1\text{-}\mathsf{CA}+\mathsf{BI}\)の無矛盾性証明を行い[6][注 1]，また八杉満利子とともに\(\Delta^1_2\text{-}\mathsf{CR},\Delta^1_2\text{-}\mathsf{CA}\)の無矛盾性証明を行った[9]．

他の順序数表記との関係もありシュッテの順序数表記\(\Sigma(n)\)との関係性がレヴィッツ[10]によって，現代的な順序数崩壊関数であるブーフホルツのψ関数との関係性が岡田光弘[11]によって提示されている．

最近のより大きな順序数に対する順序数図形は新井敏康[12][13]によって与えられ，それを用いた順序数解析が行われている[14][15][16][17][18][19]．

また順序数表記の整列擬順序に対する一般化は岡田・竹内[20]で与えられ，項書き換えやブーフホルツのヒドラの停止性証明にも用いられている[21]

順序数図形\(\mathrm{O}(\Omega)\)[]

新井敏康[22]にて導入された順序数図形\(\mathrm{O}(\Omega)\)を新井[23]に倣い解説する．これは竹内の\(\mathrm{O}(2,1)\)に対応するものであり，バッハマン・ハワード順序数までの順序数表記となる．

定義2.1

順序数図形\(\mathrm{O}(\Omega)\)の原子図形 (atomic diagram) は記号\(0,\Omega\)であり，構成子 (constructor) は\(+,\omega^\xi,d_\Omega\)からなる．

図形 (diagram) の集合\(\mathrm{O}(\Omega)\)は以下のように帰納的に定義される．

  1. 原子図形は図形である．つまり\(0,\Omega\in\mathrm{O}(\Omega)\)である．
  2. \(n\)が\(2\)以上の自然数でかつ\(\alpha_0,\ldots,\alpha_{n-1}\in\mathrm{O}(\Omega)\)であるとき\(\alpha_0+\cdots+\alpha_{n-1}\in\mathrm{O}(\Omega)\)である．
  3. \(\alpha\in\mathrm{O}(\Omega)\)であるとき，\(\omega^\alpha\in\mathrm{O}(\Omega)\)である．
  4. \(\alpha\in\mathrm{O}(\Omega)\)であるとき，\(d_\Omega(\alpha)\in\mathrm{O}(\Omega)\)であり，この図形を\(\varepsilon\)-図形という．

図形\(\alpha\)に対し図形の集合\( K_\Omega(\alpha)\subseteq\mathrm{O}(\Omega)\)[注 2]を帰納的に定める．

  1. \(K_\Omega(0):=\emptyset\)．
  2. \(K_\Omega(\Omega):=\emptyset\)．
  3. \(K_\Omega(\alpha_0+\cdots+\alpha_{n-1}):=\bigcup_{i<n}K_\Omega(\alpha_i)\)．
  4. \(K_\Omega(\omega^\alpha):=K_\Omega(\alpha)\)．
  5. \(K_\Omega(d_\Omega(\alpha)):=\{d_\Omega(\alpha)\}\)．

とする．

\(\mathrm{O}(\Omega)\)上の\(1\)変数関係\(\mathrm{P}(\alpha)\)を以下のように定める：

  1. \(\alpha=0\)であるとき，\(\mathrm{P}(\alpha)\)でない。
  2. \(\alpha=\Omega\)であるとき，\(\mathrm{P}(\alpha)\)である。
  3. \(\alpha=\alpha_0+\cdots+\alpha_{n-1}\)を満たす\(2\)以上の自然数\(n\)と\(\alpha_0,\ldots,\alpha_{n-1}\in\mathrm{O}(\Omega)\)が存在するとき，\(\mathrm{P}(\alpha)\)でない．
  4. \(\alpha=\omega^\beta\)を満たす\(\beta\in\mathrm{O}(\Omega)\)が存在するとき，\(\mathrm{P}(\alpha)\)である．
  5. \(\alpha=d_{\Omega}(\beta)\)を満たす\(\beta\in\mathrm{O}(\Omega)\)が存在するとき，\(\mathrm{P}(\alpha)\)である．

\(\mathrm{O}(\Omega)\)上の\(2\)変数関係\(\alpha<\beta\)を以下のように再帰的に定める：

  1. \(\alpha=0\)であるとき，\(\alpha<\beta\)は\(\beta\neq 0\)と同値である．
  2. \(\alpha\neq 0\)かつ\(\beta=0\)であるとき，\(\alpha<\beta\)でない．
  3. \(\mathrm{P}(\alpha)\)でありかつ\(\beta=\beta_0+\cdots+\beta_{m-1}\)を満たす\(2\)以上の自然数\(m\)と\(\beta_0,\ldots,\beta_{m-1}\in\mathrm{O}(\Omega)\)が存在するとき，\(\alpha<\beta\)は\(\alpha=\beta_0\)または\(\alpha<\beta_0\)と同値である．
  4. \(\alpha=\alpha_0+\cdots+\alpha_{n-1}\)を満たす\(2\)以上の自然数\(n\)と\(\alpha_0,\ldots,\alpha_{n-1}\in\mathrm{O}(\Omega)\)が存在しかつ\(\mathrm{P}(\beta)\)であるとき，\(\alpha<\beta\)は\(\alpha_0<\beta\)と同値である．
  5. \(\alpha=\alpha_0+\cdots+\alpha_{n-1}\)を満たす\(2\)以上の自然数\(n\)と\(\alpha_0,\ldots,\alpha_{n-1}\in\mathrm{O}(\Omega)\)が存在しかつ\(\beta=\beta_0+\cdots+\beta_{m-1}\)を満たす\(2\)以上の自然数\(m\)と\(\beta_0,\ldots,\beta_{m-1}\in\mathrm{O}(\Omega)\)が存在するとき，\(\alpha<\beta\)は以下のいずれかが成り立つことと同値である：
    1. \(n<m\)かつ\(n\)未満の任意の自然数\(i\)に対し\(\alpha_i=\beta_i\)である．
    2. \(\min\{n,m\}\)未満の自然数\(k\)であって以下を満たすものが存在する：
      1. \(k\)未満の任意の自然数\(i\)に対し\(\alpha_i=\beta_i\)である．
      2. \(\alpha_k<\beta_k\)である．
  6. \(\alpha=\Omega\)かつ\(\beta=\Omega\)であるとき，\(\alpha<\beta\)でない。
  7. \(\alpha=\Omega\)かつ\(\beta=\omega^\delta\)を満たす\(\delta\in\mathrm{O}(\Omega)\)が存在するとき，\(\alpha<\beta\)は\(\alpha<\delta\)と同値である。
  8. \(\alpha=\Omega\)かつ\(\beta=d_\Omega(\delta)\)を満たす\(\delta\in\mathrm{O}(\Omega)\)が存在するとき，\(\alpha<\beta\)でない。
  9. \(\alpha=\omega^\gamma\)を満たす\(\gamma\in\mathrm{O}(\Omega)\)が存在しかつ\(\beta=\Omega\)であるとき，\(\alpha<\beta\)と\(\gamma<\beta\)は同値である．
  10. \(\alpha=\omega^\gamma\)を満たす\(\gamma\in\mathrm{O}(\Omega)\)が存在しかつ\(\beta=\omega^\delta\)を満たす\(\delta\in\mathrm{O}(\Omega)\)が存在するとき，\(\alpha<\beta\)と\(\gamma<\delta\)は同値である．
  11. \(\alpha=\omega^\gamma\)を満たす\(\gamma\in\mathrm{O}(\Omega)\)が存在しかつ\(\beta=d_\Omega(\delta)\)を満たす\(\delta\in\mathrm{O}(\Omega)\)が存在するとき，\(\alpha<\beta\)と\(\gamma<\beta\)は同値である．
  12. \(\alpha=d_\Omega(\gamma)\)を満たす\(\gamma\in\mathrm{O}(\Omega)\)が存在しかつ\(\beta=\Omega\)であるとき，\(\alpha<\beta\)でない．
  13. \(\alpha=d_\Omega(\gamma)\)を満たす\(\gamma\in\mathrm{O}(\Omega)\)が存在しかつ\(\beta=\omega^\delta\)を満たす\(\delta\in\mathrm{O}(\Omega)\)が存在するとき，\(\alpha<\beta\)と\(\alpha<\delta\)は同値である．
  14. \(\alpha=d_\Omega(\gamma)\)を満たす\(\gamma\in\mathrm{O}(\Omega)\)が存在しかつ\(\beta=d_\Omega(\delta)\)を満たす\(\delta\in\mathrm{O}(\Omega)\)が存在するとき，\(\alpha<\beta\)は以下のいずれかが成り立つことと同値である：
    1. 任意の\(\epsilon\in K_\Omega(\gamma)\)に対し\(\epsilon<\beta\)かつ\(\gamma<\delta\)である．
    2. \(\alpha<\eta\)を満たす\(\eta\in K_\Omega(\delta)\)が存在する．
命題2.2

以下が成り立つ．

  1. \(d_\Omega(\alpha)<\Omega\)．
  2. 任意の\(\gamma\in K_\Omega(\alpha)\)に対し\(\gamma<d_\Omega(\alpha)\)．
  3. 任意の\(\gamma\in K_\Omega(\alpha)\)に対し\(\gamma\leq\alpha\)．
  4. \(\beta<\Omega\)かつ任意の\(\gamma\in K_\Omega(\beta)\)に対し\(\gamma<d_\Omega(\alpha)\)であるとき，\(\beta<d_\Omega(\alpha)\)である．
定義2.3

\(\alpha\ll\beta:\Leftrightarrow \alpha<\beta\land(\forall\gamma\in K_\Omega(\alpha))[\gamma<d_\Omega(\beta)]\)とし，\(\alpha\)は\(\beta\)に対して本質的に小さい (essentially less than) あるいは崩壊しても小さい (collapsibly less than) という．

定義2.3

以下が成り立つ．

  1. \(\alpha\ll\beta\)ならば\(d_\Omega\alpha\ll d_\Omega(\beta)\)．
  2. \(\alpha\ll\beta\)ならば\(\alpha+\gamma\ll\beta+\gamma\)．
  3. \(\alpha\ll\beta\)ならば\(\omega^\alpha\ll\omega^\beta\)．
  4. \(\alpha\ll\alpha+\beta\)または\(\alpha=\alpha+\beta\)．
  5. \(\alpha\ll\omega^\alpha\)または\(\alpha=\omega^\alpha\)．
定義2.3

\(\vartheta\)をラティエン・ヴァイアーマンのϑ関数とし，\(\mathrm{O}(\Omega)\)から\(\mathrm{On}\)への写像\(|\cdot|_\mathcal{O}\)を帰納的に定義する．

  1. \(|0|_\mathcal{O}:=0\)．
  2. \(|\Omega|_\mathcal{O}:=\omega_1\)
  3. \(|\alpha_0+\cdots+\alpha_{n-1}|_\mathcal{O}:=|\alpha_0|_\mathcal{O}\#\cdots\#|\alpha_{n-1}|_\mathcal{O}\)．
  4. \(|\omega^\alpha|_\mathcal{O}:=\omega^{|\alpha|_\mathcal{O}}\)．
  5. \(|d_\Omega(\alpha)|_\mathcal{O}:=\vartheta(\alpha)\)．

このとき，\(|\cdot|_\mathbb{O}\)は構造を保存し値域で等しいという同値関係がwell-definedになる．

ただし\(\#\)は可換和である．すなわち\(\alpha=_\mathrm{CNF}\alpha_1+\cdots+\alpha_n,\beta=_\mathrm{CNF}\beta_1+\cdots+\beta_m\)として，\(\alpha_1,\ldots,\alpha_n,\beta_1,\ldots,\beta_m\)を大きい順に並べ直したものを\(\gamma_0,\ldots,\gamma_{n+m}\)とする．すなわち\(\gamma_1\geq\cdots\geq\gamma_{n+m}\)となる．このとき\(\alpha\#\beta:=\gamma_1+\cdots\gamma_{n+m}\)とする．

関連項目[]

脚注[]

  1. ↑ なお，このとき竹内は\(\mathrm{O}(\omega+1,\omega^3)\)までの超限帰納法を用いており，八杉[7]までは，この超限帰納法が正確に証明論的順序数と一致するかは未解決であった．実際は\(\mathrm{O}(\omega+1,1)\)で十分であることが新井[8]にて指摘された．
  2. ↑ 恐らく KoeffizientのKであろう[24]

出典[]

  1. ↑ G. Takeuti. Ordinal diagrams. Journal of the Mathematical Society of Japan 9.4 (1957): 386-394.
  2. ↑ G. Takeuti, Ordinal diagrams II, J. Math. Soc. Japan 12(1960), 385-391.
  3. ↑ A. Kino. On ordinal diagrams" Journal of the Mathematical Society of Japan 13.4 (1961): 346-356.
  4. ↑ G. Takeuti, On the fundamental conjecture of GLC V, J. Math. Soc. Japan 10(1958), 121-134
  5. ↑ G. Takeuti, On the fundamental conjecture of GLC VI, Proc. Japan Acad. 37(1961), 440-443.
  6. ↑ G. Takeuti, Consistency proofs of subsystems of classical analysis, Annals of Mathematics (2) vol.86, 299–348 (1967).
  7. ↑ 八杉満利子. Ordinal Diagram について. 数学 26.2 (1974): 121-136.
  8. ↑ T. Arai. An accessibility proof of ordinal diagrams in intuitionistic theories for iterated inductive definitions. Tsukuba journal of mathematics 8.2 (1984): 209-218.
  9. ↑ G. Takeuti. and M. Yasugi, The ordinals of the systems of second order arithmetic with the provably \(\Delta^1_2\text{-}\mathsf{CA}\)-comprehension axiom and with the \(\Delta^1_2\)-comprehension axiom respectively”, Japanese Journal of Mathematics vol.41, 1-67 (1973).
  10. ↑ H. Levitz. On the Relationship Between Takeuti's Ordinal Diagrams \(\mathrm{O}(n)\) and Schütte's System of Ordinal Notations \(\Sigma(n)\). Studies in Logic and the Foundations of Mathematics. Vol. 60. Elsevier, 1970. 377-405.
  11. ↑ M. Okada. A simple relationship between Buchholz's new system of ordinal notations and Takeuti's system of ordinal diagrams. The Journal of symbolic logic 52.3 (1987): 577-581.
  12. ↑ T. Arai. Ordinal diagrams for recursively Mahlo universes. Archive for Mathematical Logic 39.5 (2000): 353-391.
  13. ↑ T. Arai. Ordinal diagrams for \(\Pi_3\)-reflection. The Journal of Symbolic Logic 65.3 (2000): 1375-1394.
  14. ↑ T. Arai. Proof theory for theories of ordinals—I: recursively Mahlo ordinals. Annals of Pure and applied Logic 122.1-3 (2003): 1-85.
  15. ↑ T. Arai. Proof theory for theories of ordinals II: \(\Pi_3\)-reflection. Annals of Pure and Applied Logic 129.1-3 (2004): 39-92.
  16. ↑ T. Arai. Proof Theory for Theories of Ordinals III: \(\Pi_n\)-Reflection. Gentzen's Centenary. Springer, Cham, 2015. 357-424.
  17. ↑ T. Arai. Wellfoundedness Proofs by Means of Non-Monotonic Inductive Definitions I: \(\Pi^0_2\)-Operators. Journal of Symbolic Logic (2004): 830-850.
  18. ↑ T. Arai. Wellfoundedness proofs by means of non-monotonic inductive definitions II: first order operators. Annals of Pure and Applied Logic 162.2 (2010): 107-143.
  19. ↑ T. Arai. A Sneak Preview of Proof Theory of Ordinals (< Special Section> Infinity in Philosophy and Mathematics). Annals of the Japan Association for Philosophy of Science 20 (2012): 29-47.
  20. ↑ M. Okada and G. Takeuti. (1987): On the theory of quasi-ordinal diagrams. In: Logic and combinatorics (Arcata, Calif., 1985), Contemp. Math. 65, Amer. Math. Soc., Providence, RI, pp. 295–308
  21. ↑ M. Okada, and Y. Takahashi. On quasi ordinal diagram systems. Electronic Proceedings in Theoretical Computer Science, EPTCS 288 (2019): 38-49.
  22. ↑ 新井敏康. 竹内の基本予想について. 数学 40.4 (1988): 322-337.
  23. ↑ T. Arai. An introduction to finitary analyses of proof figures. LONDON MATHEMATICAL SOCIETY LECTURE NOTE SERIES (1999): 1-26.
  24. ↑ W. Buchholz. A survey on ordinal notations around the Bachmann–Howard ordinal. Feferman on Foundations. Springer, Cham, 2017. 71-100.
特に記載のない限り、コミュニティのコンテンツはCC-BY-SAライセンスの下で利用可能です。
Advertisement