順序数図形

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

概要

ゲンツェンが無矛盾性証明の際に証明図から順序数を見出したように，竹内外史は証明図に対応させる順序数表記として順序数図形を考案した．それを用いて，現代的に言えば二階算術の部分体系$\Pi _{1}^{1}{\text{-}}{\mathsf {CA}}_{0}$の無矛盾性証明，そして$\Pi _{1}^{1}{\text{-}}{\mathsf {CA}}+{\mathsf {BI}}$の無矛盾性証明を行い，また八杉満利子とともに$\Delta _{2}^{1}{\text{-}}{\mathsf {CA}}$の無矛盾性証明を行った．

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

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

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

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

定義2.1

順序数図形$\mathrm {O} (\Omega )$の原子図形 (atomic diagram) は記号$0,\Omega$であり，構成子 (constructor) は$+,\omega ^{\xi },d_{\Omega }$からなる． 図形 (diagram) の集合$\mathrm {O} (\Omega )$は以下のように帰納的に定義される． 原子図形は図形である．つまり$0,\Omega \in \mathrm {O} (\Omega )$である． $n$が$2$以上の自然数でかつ$\alpha _{0},\ldots ,\alpha _{n-1}\in \mathrm {O} (\Omega )$であるとき$\alpha _{0}+\cdots +\alpha _{n-1}\in \mathrm {O} (\Omega )$である． $\alpha \in \mathrm {O} (\Omega )$であるとき，$\omega ^{\alpha }\in \mathrm {O} (\Omega )$である． $\alpha \in \mathrm {O} (\Omega )$であるとき，$d_{\Omega }(\alpha )\in \mathrm {O} (\Omega )$であり，この図形を$\varepsilon$-図形という． 図形$\alpha$に対し図形の集合$K_{\Omega }(\alpha )\subseteq \mathrm {O} (\Omega )$を帰納的に定める． $K_{\Omega }(0):=\emptyset$． $K_{\Omega }(\Omega ):=\emptyset$． $K_{\Omega }(\alpha _{0}+\cdots +\alpha _{n-1}):=\bigcup _{i<n}K_{\Omega }(\alpha _{i})$． $K_{\Omega }(\omega ^{\alpha }):=K_{\Omega }(\alpha )$． $K_{\Omega }(d_{\Omega }(\alpha )):=\{d_{\Omega }(\alpha )\}$． とする． $\mathrm {O} (\Omega )$上の$1$変数関係$\mathrm {P} (\alpha )$を以下のように定める： $\alpha=0$であるとき，$\mathrm {P} (\alpha )$でない。 $2$以上の自然数$n$と$\alpha _{0},\ldots ,\alpha _{n-1}\in \mathrm {O} (\Omega )$を用いて$\alpha =\alpha _{0}+\cdots +\alpha _{n-1}$と表せるとき，$\mathrm {P} (\alpha )$でない． $\beta \in \mathrm {O} (\Omega )$を用いて$\alpha = \omega^{\beta}$と表せるとき，$\mathrm {P} (\alpha )$である． $\beta \in \mathrm {O} (\Omega )$を用いて構文解析に失敗 (不明な関数「\d」): {\displaystyle \alpha=\d_{\Omega}(\beta)} と表せるとき，$\mathrm {P} (\alpha )$である． $\mathrm {O} (\Omega )$上の全順序$\alpha < \beta$を以下のように再帰的に定める： $\alpha=0$であるとき，$\alpha < \beta$は構文解析に失敗 (構文エラー): {\displaystyle \beta\neq 0<math>と同値である． # <math>\alpha\neq 0} かつ$\beta=0$であるとき，$\alpha < \beta$でない． 任意の$\alpha$に対し$d_{\Omega }(\alpha )<\Omega$である． 書き途中 $\alpha <d_{\Omega }(\beta )$ならばである． $d_{\Omega }(\alpha )<d_{\Omega }(\beta )$が成り立つのは以下のいずれかが成り立つときである． $(\exists \delta \in K_{\Omega }(\beta ))[d_{\Omega }(\alpha )<\delta ]$． $(\forall \gamma \in K_{\Omega }(\alpha ))[\gamma <d_{\Omega }(\beta )]\land \alpha <\beta$．

この順序数図形は以下のように定められる順序数崩壊関数と関係がある． $\mathcal{H}_\alpha(X)$を$\{0,\Omega\}\cup X$の$+,\xi \mapsto \omega ^{\xi },\xi \mapsto \psi _{\Omega }(\xi )$閉包，ただし，$\psi_\Omega$の定義域を$\alpha$に制限しているとし$\psi _{\Omega }(\alpha ):=\min\{\xi |\xi \notin {\mathcal {H}}_{\alpha }(\emptyset )\}$と定める．

関連項目

• 順序数崩壊関数
• 証明論的順序数