順序数表記 (ordinal notation, ordinal representation system) は計算可能順序数を順序型として持つ計算可能二項関係である[1][2]

概要

順序数表記は文字列集合上の二項関係の組で以下を満たすものである.

  1. は計算可能である.
  2. は整列順序である.

ただしここでの整列順序は整礎な全順序ではなく整礎な狭義全順序を表す.詳しくは順序数#整列集合を参照.2つ目の条件を緩めてが整礎狭義半順序であるとすることもある.

また以下,文字列集合は算術で扱うために自然数の部分集合に限定することとする.

順序数表記には標準性 (canonicity) と呼ばれる,順序数表記に何かしら数学的に自然である背景が要求されることが多い.これは自然でない順序数表記に対して証明論的に病的な振る舞いを起こすことが知られていることと哲学的背景による.詳細は証明論的順序数を参照.

またカントール標準形ヴェブレン関数順序数崩壊関数などは全て集合論的な対象であり,順序数表記ではなく,それから誘導される順序数表記とは異なることに注意されたい.


クリーネの

クリーネによって定義されたある意味で万能な順序数表記であり,これはチャーチ・クリーネ順序数を順序型として持つ.これは上の定義での順序数表記ではない.なぜなら再帰的ではないからである.このような再帰的ではない順序数表記というのも計算理論において考えられることがある.

関連記事

出典

  1. W. Pohlers. Proof Theory the first step into impredicativity, Springer, 2009.
  2. M. Rathjen: The realm of ordinal analysis. S.B. Cooper and J.K. Truss (eds.): Sets and Proofs. (Cambridge University Press, 1999) 219–279.
  3. P. Aczel. Describing ordinals using functionals of transfinite type." Journal of Symbolic Logic (1972): 35-47.
  4. J.Y. Girard. -logic, Part 1: Dilators. Annals of Mathematical Logic 21.2-3 (1981): 75-219.
  5. J.Y. Girard. and J. Vauzeilles. Functors and ordinal notations. I: A functorial construction of the Veblen hierarchy. The Journal of symbolic logic 49.3 (1984): 713-729.
  6. J.Y. Girard. and J. Vauzeilles. Functors and ordinal notations. II: A functorial construction of the Bachmann hierarchy. The Journal of symbolic logic 49.4 (1984): 1079-1114.
  7. V. Jacqueline. Functors and Ordinal Notations III-Dilators and Gardens. Studies in Logic and the Foundations of Mathematics. Vol. 107. Elsevier, 1982. 333-364.
  8. J. Vauzeilles. Functors and Ordinal Notations. IV: The Howard Ordinal and the Functor . The Journal of symbolic logic 50.2 (1985): 331-338.
  9. T.J. Carlson. Ordinal arithmetic and -elementarity. Archive for Mathematical Logic 38.7 (1999): 449-460.
特に記載のない限り、コミュニティのコンテンツはCC-BY-SAライセンスの下で利用可能です。