順序数表記

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

概要

順序数表記は文字列集合$\mathsf{OT}$と$\mathsf{OT}$上の二項関係$\prec$の組$\langle\mathsf{OT},\prec\rangle$で以下を満たすものである．

1. $\mathsf{OT}$と$\prec$は計算可能である．
2. $\prec$は整列順序である．

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

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

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

例

• 集合論的な背景を持つもの
  • カントール標準形による順序数表記
  • ヴェブレン関数による順序数表記
  • 順序数崩壊関数による順序数表記
• 証明論的な背景を持つもの
  • 順序数図形による順序数表記
• 圏論的な背景を持つもの
  • アクゼルやジラールやを参照．
• モデル理論的背景を持つもの
  • カールソンを参照．

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

クリーネの$\mathcal{O}$

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

関連記事

• カントール標準形
• ヴェブレン関数
• ヴェブレンのϕ表記
• 順序数崩壊関数
• 順序数図形
• 証明論的順序数