順序数図形

順序数図形 (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 {CR}},\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 )$でない。 $\alpha =\Omega$であるとき，$\mathrm {P} (\alpha )$である。 $\alpha =\alpha _{0}+\cdots +\alpha _{n-1}$を満たす$2$以上の自然数$n$と$\alpha _{0},\ldots ,\alpha _{n-1}\in \mathrm {O} (\Omega )$が存在するとき，$\mathrm {P} (\alpha )$でない． $\alpha = \omega^{\beta}$を満たす$\beta \in \mathrm {O} (\Omega )$が存在するとき，$\mathrm {P} (\alpha )$である． $\alpha =d_{\Omega }(\beta )$を満たす$\beta \in \mathrm {O} (\Omega )$が存在するとき，$\mathrm {P} (\alpha )$である． $\mathrm {O} (\Omega )$上の$2$変数関係$\alpha < \beta$を以下のように再帰的に定める： $\alpha=0$であるとき，$\alpha < \beta$は$\beta \neq 0$と同値である． $\alpha\neq 0$かつ$\beta=0$であるとき，$\alpha < \beta$でない． $\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}$と同値である． $\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$と同値である． $\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$は以下のいずれかが成り立つことと同値である： $n<m$かつ$n$未満の任意の自然数$i$に対し$\alpha _{i}=\beta _{i}$である． $\min\{n,m\}$未満の自然数$k$であって以下を満たすものが存在する： $k$未満の任意の自然数$i$に対し$\alpha _{i}=\beta _{i}$である． $\alpha _{k}<\beta _{k}$である． $\alpha =\Omega$かつ$\beta =\Omega$であるとき，$\alpha < \beta$でない。 $\alpha =\Omega$かつ$\beta =\omega ^{\delta }$を満たす$\delta \in \mathrm {O} (\Omega )$が存在するとき，$\alpha < \beta$は$\alpha <\delta$と同値である。 $\alpha =\Omega$かつ$\beta =d_{\Omega }(\delta )$を満たす$\delta \in \mathrm {O} (\Omega )$が存在するとき，$\alpha < \beta$でない。 $\alpha =\omega ^{\gamma }$を満たす$\gamma \in \mathrm {O} (\Omega )$が存在しかつ$\beta =\Omega$であるとき，$\alpha < \beta$と$\gamma < \beta$は同値である． $\alpha =\omega ^{\gamma }$を満たす$\gamma \in \mathrm {O} (\Omega )$が存在しかつ$\beta =\omega ^{\delta }$を満たす$\delta \in \mathrm {O} (\Omega )$が存在するとき，$\alpha < \beta$と$\gamma<\delta$は同値である． $\alpha =\omega ^{\gamma }$を満たす$\gamma \in \mathrm {O} (\Omega )$が存在しかつ$\beta =d_{\Omega }(\delta )$を満たす$\delta \in \mathrm {O} (\Omega )$が存在するとき，$\alpha < \beta$と$\gamma < \beta$は同値である． $\alpha =d_{\Omega }(\gamma )$を満たす$\gamma \in \mathrm {O} (\Omega )$が存在しかつ$\beta =\Omega$であるとき，$\alpha < \beta$でない． $\alpha =d_{\Omega }(\gamma )$を満たす$\gamma \in \mathrm {O} (\Omega )$が存在しかつ$\beta =\omega ^{\delta }$を満たす$\delta \in \mathrm {O} (\Omega )$が存在するとき，$\alpha < \beta$と$\alpha <\delta$は同値である． $\alpha =d_{\Omega }(\gamma )$を満たす$\gamma \in \mathrm {O} (\Omega )$が存在しかつ$\beta =d_{\Omega }(\delta )$を満たす$\delta \in \mathrm {O} (\Omega )$が存在するとき，$\alpha < \beta$は以下のいずれかが成り立つことと同値である： 任意の$\epsilon \in K_{\Omega }(\gamma )$に対し$\epsilon <\beta$かつ$\gamma<\delta$である． $\alpha <\eta$を満たす$\eta \in K_{\Omega }(\delta )$が存在する．

命題2.2
以下が成り立つ． $d_{\Omega }(\alpha )<\Omega$． 任意の$\gamma \in K_{\Omega }(\alpha )$に対し$\gamma <d_{\Omega }(\alpha )$． 任意の$\gamma \in K_{\Omega }(\alpha )$に対し$\gamma \leq \alpha$． $\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
以下が成り立つ． $\alpha \ll \beta$ならば$d_{\Omega }\alpha \ll d_{\Omega }(\beta )$． $\alpha \ll \beta$ならば$\alpha +\gamma \ll \beta +\gamma$． $\alpha \ll \beta$ならば$\omega ^{\alpha }\ll \omega ^{\beta }$． $\alpha \ll \alpha +\beta$または$\alpha =\alpha +\beta$． $\alpha \ll \omega ^{\alpha }$または$\alpha = \omega^{\alpha}$．

定義2.3

$\vartheta$をラティエン・ヴァイアーマンのϑ関数とし，$\mathrm {O} (\Omega )$から$\mathrm{On}$への写像$|\cdot |_{\mathcal {O}}$を帰納的に定義する． $|0|_{\mathcal {O}}:=0$． $|\Omega |_{\mathcal {O}}:=\omega _{1}$ $|\alpha _{0}+\cdots +\alpha _{n-1}|_{\mathcal {O}}:=|\alpha _{0}|_{\mathcal {O}}\#\cdots \#|\alpha _{n-1}|_{\mathcal {O}}$． $|\omega ^{\alpha }|_{\mathcal {O}}:=\omega ^{|\alpha |_{\mathcal {O}}}$． $|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}$とする．

関連項目

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