順序数図形 (ordinal diagram, o.d.) は竹内外史 が証明論 で用いた順序数表記である.例えば
O
(
2
,
1
)
{\displaystyle \mathrm {O} (2,1)}
での
<
0
{\displaystyle <_{0}}
の順序型はバッハマン・ハワード順序数 であり,
O
(
ω
+
1
,
1
)
{\displaystyle \mathrm {O} (\omega +1,1)}
での
<
0
{\displaystyle <_{0}}
の順序型は竹内・フェファーマン・ブーフホルツ順序数 である.
概要
ゲンツェンが無矛盾性証明の際に証明図から順序数 を見出したように,竹内外史は証明図に対応させる順序数表記として順序数図形を考案した[1] [2] .後に順序数図形は簡略化できることを指摘され[3] ,後は簡略化されたものが用いられることが多い.
竹内は現代的に言えば二階算術 の部分体系
Π
1
1
-
C
A
0
{\displaystyle \Pi _{1}^{1}{\text{-}}{\mathsf {CA}}_{0}}
の無矛盾性証明[4] [5] ,そして
Π
1
1
-
C
A
+
B
I
{\displaystyle \Pi _{1}^{1}{\text{-}}{\mathsf {CA}}+{\mathsf {BI}}}
の無矛盾性証明を行い[6] [注 1] ,また八杉満利子とともに
Δ
2
1
-
C
R
,
Δ
2
1
-
C
A
{\displaystyle \Delta _{2}^{1}{\text{-}}{\mathsf {CR}},\Delta _{2}^{1}{\text{-}}{\mathsf {CA}}}
の無矛盾性証明を行った[9] .
他の順序数表記との関係もありシュッテの順序数表記
Σ
(
n
)
{\displaystyle \Sigma(n)}
との関係性がレヴィッツ[10] によって,現代的な順序数崩壊関数 であるブーフホルツのψ関数 との関係性が岡田光弘[11] によって提示されている.
最近のより大きな順序数に対する順序数図形は新井敏康[12] [13] によって与えられ,それを用いた順序数解析 が行われている[14] [15] [16] [17] [18] [19] .
また順序数表記の整列擬順序に対する一般化は岡田・竹内[20] で与えられ,項書き換えやブーフホルツのヒドラ の停止性証明にも用いられている[21]
順序数図形
O
(
Ω
)
{\displaystyle \mathrm {O} (\Omega )}
新井敏康[22] にて導入された順序数図形
O
(
Ω
)
{\displaystyle \mathrm {O} (\Omega )}
を新井[23] に倣い解説する.これは竹内の
O
(
2
,
1
)
{\displaystyle \mathrm {O} (2,1)}
に対応するものであり,バッハマン・ハワード順序数 までの順序数表記となる.
定義2.1
順序数図形
O
(
Ω
)
{\displaystyle \mathrm {O} (\Omega )}
の原子図形 (atomic diagram) は記号
0
,
Ω
{\displaystyle 0,\Omega }
であり,構成子 (constructor) は
+
,
ω
ξ
,
d
Ω
{\displaystyle +,\omega ^{\xi },d_{\Omega }}
からなる.
図形 (diagram) の集合
O
(
Ω
)
{\displaystyle \mathrm {O} (\Omega )}
は以下のように帰納的に定義される.
原子図形は図形である.つまり
0
,
Ω
∈
O
(
Ω
)
{\displaystyle 0,\Omega \in \mathrm {O} (\Omega )}
である.
n
{\displaystyle n}
が
2
{\displaystyle 2}
以上の自然数でかつ
α
0
,
…
,
α
n
−
1
∈
O
(
Ω
)
{\displaystyle \alpha _{0},\ldots ,\alpha _{n-1}\in \mathrm {O} (\Omega )}
であるとき
α
0
+
⋯
+
α
n
−
1
∈
O
(
Ω
)
{\displaystyle \alpha _{0}+\cdots +\alpha _{n-1}\in \mathrm {O} (\Omega )}
である.
α
∈
O
(
Ω
)
{\displaystyle \alpha \in \mathrm {O} (\Omega )}
であるとき,
ω
α
∈
O
(
Ω
)
{\displaystyle \omega ^{\alpha }\in \mathrm {O} (\Omega )}
である.
α
∈
O
(
Ω
)
{\displaystyle \alpha \in \mathrm {O} (\Omega )}
であるとき,
d
Ω
(
α
)
∈
O
(
Ω
)
{\displaystyle d_{\Omega }(\alpha )\in \mathrm {O} (\Omega )}
であり,この図形を
ε
{\displaystyle \varepsilon}
-図形という.
図形
α
{\displaystyle \alpha}
に対し図形の集合
K
Ω
(
α
)
⊆
O
(
Ω
)
{\displaystyle K_{\Omega }(\alpha )\subseteq \mathrm {O} (\Omega )}
[注 2] を帰納的に定める.
K
Ω
(
0
)
:=
∅
{\displaystyle K_{\Omega }(0):=\emptyset }
.
K
Ω
(
Ω
)
:=
∅
{\displaystyle K_{\Omega }(\Omega ):=\emptyset }
.
K
Ω
(
α
0
+
⋯
+
α
n
−
1
)
:=
⋃
i
<
n
K
Ω
(
α
i
)
{\displaystyle K_{\Omega }(\alpha _{0}+\cdots +\alpha _{n-1}):=\bigcup _{i<n}K_{\Omega }(\alpha _{i})}
.
K
Ω
(
ω
α
)
:=
K
Ω
(
α
)
{\displaystyle K_{\Omega }(\omega ^{\alpha }):=K_{\Omega }(\alpha )}
.
K
Ω
(
d
Ω
(
α
)
)
:=
{
d
Ω
(
α
)
}
{\displaystyle K_{\Omega }(d_{\Omega }(\alpha )):=\{d_{\Omega }(\alpha )\}}
.
とする.
O
(
Ω
)
{\displaystyle \mathrm {O} (\Omega )}
上の
1
{\displaystyle 1}
変数関係
P
(
α
)
{\displaystyle \mathrm {P} (\alpha )}
を以下のように定める:
α
=
0
{\displaystyle \alpha=0}
であるとき,
P
(
α
)
{\displaystyle \mathrm {P} (\alpha )}
でない。
α
=
Ω
{\displaystyle \alpha =\Omega }
であるとき,
P
(
α
)
{\displaystyle \mathrm {P} (\alpha )}
である。
α
=
α
0
+
⋯
+
α
n
−
1
{\displaystyle \alpha =\alpha _{0}+\cdots +\alpha _{n-1}}
を満たす
2
{\displaystyle 2}
以上の自然数
n
{\displaystyle n}
と
α
0
,
…
,
α
n
−
1
∈
O
(
Ω
)
{\displaystyle \alpha _{0},\ldots ,\alpha _{n-1}\in \mathrm {O} (\Omega )}
が存在するとき,
P
(
α
)
{\displaystyle \mathrm {P} (\alpha )}
でない.
α
=
ω
β
{\displaystyle \alpha = \omega^{\beta}}
を満たす
β
∈
O
(
Ω
)
{\displaystyle \beta \in \mathrm {O} (\Omega )}
が存在するとき,
P
(
α
)
{\displaystyle \mathrm {P} (\alpha )}
である.
α
=
d
Ω
(
β
)
{\displaystyle \alpha =d_{\Omega }(\beta )}
を満たす
β
∈
O
(
Ω
)
{\displaystyle \beta \in \mathrm {O} (\Omega )}
が存在するとき,
P
(
α
)
{\displaystyle \mathrm {P} (\alpha )}
である.
O
(
Ω
)
{\displaystyle \mathrm {O} (\Omega )}
上の
2
{\displaystyle 2}
変数関係
α
<
β
{\displaystyle \alpha < \beta}
を以下のように再帰的に定める:
α
=
0
{\displaystyle \alpha=0}
であるとき,
α
<
β
{\displaystyle \alpha < \beta}
は
β
≠
0
{\displaystyle \beta \neq 0}
と同値である.
α
≠
0
{\displaystyle \alpha\neq 0}
かつ
β
=
0
{\displaystyle \beta=0}
であるとき,
α
<
β
{\displaystyle \alpha < \beta}
でない.
P
(
α
)
{\displaystyle \mathrm {P} (\alpha )}
でありかつ
β
=
β
0
+
⋯
+
β
m
−
1
{\displaystyle \beta =\beta _{0}+\cdots +\beta _{m-1}}
を満たす
2
{\displaystyle 2}
以上の自然数
m
{\displaystyle m}
と
β
0
,
…
,
β
m
−
1
∈
O
(
Ω
)
{\displaystyle \beta _{0},\ldots ,\beta _{m-1}\in \mathrm {O} (\Omega )}
が存在するとき,
α
<
β
{\displaystyle \alpha < \beta}
は
α
=
β
0
{\displaystyle \alpha =\beta _{0}}
または
α
<
β
0
{\displaystyle \alpha <\beta _{0}}
と同値である.
α
=
α
0
+
⋯
+
α
n
−
1
{\displaystyle \alpha =\alpha _{0}+\cdots +\alpha _{n-1}}
を満たす
2
{\displaystyle 2}
以上の自然数
n
{\displaystyle n}
と
α
0
,
…
,
α
n
−
1
∈
O
(
Ω
)
{\displaystyle \alpha _{0},\ldots ,\alpha _{n-1}\in \mathrm {O} (\Omega )}
が存在しかつ
P
(
β
)
{\displaystyle \mathrm {P} (\beta )}
であるとき,
α
<
β
{\displaystyle \alpha < \beta}
は
α
0
<
β
{\displaystyle \alpha _{0}<\beta }
と同値である.
α
=
α
0
+
⋯
+
α
n
−
1
{\displaystyle \alpha =\alpha _{0}+\cdots +\alpha _{n-1}}
を満たす
2
{\displaystyle 2}
以上の自然数
n
{\displaystyle n}
と
α
0
,
…
,
α
n
−
1
∈
O
(
Ω
)
{\displaystyle \alpha _{0},\ldots ,\alpha _{n-1}\in \mathrm {O} (\Omega )}
が存在しかつ
β
=
β
0
+
⋯
+
β
m
−
1
{\displaystyle \beta =\beta _{0}+\cdots +\beta _{m-1}}
を満たす
2
{\displaystyle 2}
以上の自然数
m
{\displaystyle m}
と
β
0
,
…
,
β
m
−
1
∈
O
(
Ω
)
{\displaystyle \beta _{0},\ldots ,\beta _{m-1}\in \mathrm {O} (\Omega )}
が存在するとき,
α
<
β
{\displaystyle \alpha < \beta}
は以下のいずれかが成り立つことと同値である:
n
<
m
{\displaystyle n<m}
かつ
n
{\displaystyle n}
未満の任意の自然数
i
{\displaystyle i}
に対し
α
i
=
β
i
{\displaystyle \alpha _{i}=\beta _{i}}
である.
min
{
n
,
m
}
{\displaystyle \min\{n,m\}}
未満の自然数
k
{\displaystyle k}
であって以下を満たすものが存在する:
k
{\displaystyle k}
未満の任意の自然数
i
{\displaystyle i}
に対し
α
i
=
β
i
{\displaystyle \alpha _{i}=\beta _{i}}
である.
α
k
<
β
k
{\displaystyle \alpha _{k}<\beta _{k}}
である.
α
=
Ω
{\displaystyle \alpha =\Omega }
かつ
β
=
Ω
{\displaystyle \beta =\Omega }
であるとき,
α
<
β
{\displaystyle \alpha < \beta}
でない。
α
=
Ω
{\displaystyle \alpha =\Omega }
かつ
β
=
ω
δ
{\displaystyle \beta =\omega ^{\delta }}
を満たす
δ
∈
O
(
Ω
)
{\displaystyle \delta \in \mathrm {O} (\Omega )}
が存在するとき,
α
<
β
{\displaystyle \alpha < \beta}
は
α
<
δ
{\displaystyle \alpha <\delta }
と同値である。
α
=
Ω
{\displaystyle \alpha =\Omega }
かつ
β
=
d
Ω
(
δ
)
{\displaystyle \beta =d_{\Omega }(\delta )}
を満たす
δ
∈
O
(
Ω
)
{\displaystyle \delta \in \mathrm {O} (\Omega )}
が存在するとき,
α
<
β
{\displaystyle \alpha < \beta}
でない。
α
=
ω
γ
{\displaystyle \alpha =\omega ^{\gamma }}
を満たす
γ
∈
O
(
Ω
)
{\displaystyle \gamma \in \mathrm {O} (\Omega )}
が存在しかつ
β
=
Ω
{\displaystyle \beta =\Omega }
であるとき,
α
<
β
{\displaystyle \alpha < \beta}
と
γ
<
β
{\displaystyle \gamma < \beta}
は同値である.
α
=
ω
γ
{\displaystyle \alpha =\omega ^{\gamma }}
を満たす
γ
∈
O
(
Ω
)
{\displaystyle \gamma \in \mathrm {O} (\Omega )}
が存在しかつ
β
=
ω
δ
{\displaystyle \beta =\omega ^{\delta }}
を満たす
δ
∈
O
(
Ω
)
{\displaystyle \delta \in \mathrm {O} (\Omega )}
が存在するとき,
α
<
β
{\displaystyle \alpha < \beta}
と
γ
<
δ
{\displaystyle \gamma<\delta}
は同値である.
α
=
ω
γ
{\displaystyle \alpha =\omega ^{\gamma }}
を満たす
γ
∈
O
(
Ω
)
{\displaystyle \gamma \in \mathrm {O} (\Omega )}
が存在しかつ
β
=
d
Ω
(
δ
)
{\displaystyle \beta =d_{\Omega }(\delta )}
を満たす
δ
∈
O
(
Ω
)
{\displaystyle \delta \in \mathrm {O} (\Omega )}
が存在するとき,
α
<
β
{\displaystyle \alpha < \beta}
と
γ
<
β
{\displaystyle \gamma < \beta}
は同値である.
α
=
d
Ω
(
γ
)
{\displaystyle \alpha =d_{\Omega }(\gamma )}
を満たす
γ
∈
O
(
Ω
)
{\displaystyle \gamma \in \mathrm {O} (\Omega )}
が存在しかつ
β
=
Ω
{\displaystyle \beta =\Omega }
であるとき,
α
<
β
{\displaystyle \alpha < \beta}
でない.
α
=
d
Ω
(
γ
)
{\displaystyle \alpha =d_{\Omega }(\gamma )}
を満たす
γ
∈
O
(
Ω
)
{\displaystyle \gamma \in \mathrm {O} (\Omega )}
が存在しかつ
β
=
ω
δ
{\displaystyle \beta =\omega ^{\delta }}
を満たす
δ
∈
O
(
Ω
)
{\displaystyle \delta \in \mathrm {O} (\Omega )}
が存在するとき,
α
<
β
{\displaystyle \alpha < \beta}
と
α
<
δ
{\displaystyle \alpha <\delta }
は同値である.
α
=
d
Ω
(
γ
)
{\displaystyle \alpha =d_{\Omega }(\gamma )}
を満たす
γ
∈
O
(
Ω
)
{\displaystyle \gamma \in \mathrm {O} (\Omega )}
が存在しかつ
β
=
d
Ω
(
δ
)
{\displaystyle \beta =d_{\Omega }(\delta )}
を満たす
δ
∈
O
(
Ω
)
{\displaystyle \delta \in \mathrm {O} (\Omega )}
が存在するとき,
α
<
β
{\displaystyle \alpha < \beta}
は以下のいずれかが成り立つことと同値である:
任意の
ϵ
∈
K
Ω
(
γ
)
{\displaystyle \epsilon \in K_{\Omega }(\gamma )}
に対し
ϵ
<
β
{\displaystyle \epsilon <\beta }
かつ
γ
<
δ
{\displaystyle \gamma<\delta}
である.
α
<
η
{\displaystyle \alpha <\eta }
を満たす
η
∈
K
Ω
(
δ
)
{\displaystyle \eta \in K_{\Omega }(\delta )}
が存在する.
定義2.3
ϑ
{\displaystyle \vartheta}
をラティエン・ヴァイアーマンのϑ関数 とし,
O
(
Ω
)
{\displaystyle \mathrm {O} (\Omega )}
から
O
n
{\displaystyle \mathrm{On}}
への写像
|
⋅
|
O
{\displaystyle |\cdot |_{\mathcal {O}}}
を帰納的に定義する.
|
0
|
O
:=
0
{\displaystyle |0|_{\mathcal {O}}:=0}
.
|
Ω
|
O
:=
ω
1
{\displaystyle |\Omega |_{\mathcal {O}}:=\omega _{1}}
|
α
0
+
⋯
+
α
n
−
1
|
O
:=
|
α
0
|
O
#
⋯
#
|
α
n
−
1
|
O
{\displaystyle |\alpha _{0}+\cdots +\alpha _{n-1}|_{\mathcal {O}}:=|\alpha _{0}|_{\mathcal {O}}\#\cdots \#|\alpha _{n-1}|_{\mathcal {O}}}
.
|
ω
α
|
O
:=
ω
|
α
|
O
{\displaystyle |\omega ^{\alpha }|_{\mathcal {O}}:=\omega ^{|\alpha |_{\mathcal {O}}}}
.
|
d
Ω
(
α
)
|
O
:=
ϑ
(
α
)
{\displaystyle |d_{\Omega }(\alpha )|_{\mathcal {O}}:=\vartheta (\alpha )}
.
このとき,
|
⋅
|
O
{\displaystyle |\cdot |_{\mathbb {O} }}
は構造を保存し値域で等しいという同値関係がwell-definedになる.
ただし
#
{\displaystyle \#}
は可換和である.すなわち
α
=
C
N
F
α
1
+
⋯
+
α
n
,
β
=
C
N
F
β
1
+
⋯
+
β
m
{\displaystyle \alpha =_{\mathrm {CNF} }\alpha _{1}+\cdots +\alpha _{n},\beta =_{\mathrm {CNF} }\beta _{1}+\cdots +\beta _{m}}
として,
α
1
,
…
,
α
n
,
β
1
,
…
,
β
m
{\displaystyle \alpha _{1},\ldots ,\alpha _{n},\beta _{1},\ldots ,\beta _{m}}
を大きい順に並べ直したものを
γ
0
,
…
,
γ
n
+
m
{\displaystyle \gamma _{0},\ldots ,\gamma _{n+m}}
とする.すなわち
γ
1
≥
⋯
≥
γ
n
+
m
{\displaystyle \gamma _{1}\geq \cdots \geq \gamma _{n+m}}
となる.このとき
α
#
β
:=
γ
1
+
⋯
γ
n
+
m
{\displaystyle \alpha \#\beta :=\gamma _{1}+\cdots \gamma _{n+m}}
とする.
関連項目
脚注
↑ なお,このとき竹内は
O
(
ω
+
1
,
ω
3
)
{\displaystyle \mathrm {O} (\omega +1,\omega ^{3})}
までの超限帰納法を用いており,八杉[7] までは,この超限帰納法が正確に証明論的順序数と一致するかは未解決であった.実際は
O
(
ω
+
1
,
1
)
{\displaystyle \mathrm {O} (\omega +1,1)}
で十分であることが新井[8] にて指摘された.
↑ 恐らく
KoeffizientのKであろう[24]
出典
↑ G. Takeuti. Ordinal diagrams. Journal of the Mathematical Society of Japan 9.4 (1957): 386-394.
↑ G. Takeuti, Ordinal diagrams II, J. Math. Soc. Japan 12(1960), 385-391.
↑ A. Kino. On ordinal diagrams" Journal of the Mathematical Society of Japan 13.4 (1961): 346-356.
↑ G. Takeuti, On the fundamental conjecture of GLC V, J. Math. Soc. Japan 10(1958), 121-134
↑ G. Takeuti, On the fundamental conjecture of GLC VI, Proc. Japan
Acad. 37(1961), 440-443.
↑ G. Takeuti, Consistency proofs of subsystems of classical analysis, Annals of Mathematics (2) vol.86, 299–348 (1967).
↑ 八杉満利子. Ordinal Diagram について. 数学 26.2 (1974): 121-136.
↑ T. Arai. An accessibility proof of ordinal diagrams in intuitionistic theories for iterated inductive definitions. Tsukuba journal of mathematics 8.2 (1984): 209-218.
↑ G. Takeuti. and M. Yasugi, The ordinals of the systems of second order arithmetic with the provably
Δ
2
1
-
C
A
{\displaystyle \Delta _{2}^{1}{\text{-}}{\mathsf {CA}}}
-comprehension axiom and with the
Δ
2
1
{\displaystyle \Delta _{2}^{1}}
-comprehension axiom respectively”, Japanese Journal of Mathematics vol.41, 1-67 (1973).
↑ H. Levitz. On the Relationship Between Takeuti's Ordinal Diagrams
O
(
n
)
{\displaystyle \mathrm {O} (n)}
and Schütte's System of Ordinal Notations
Σ
(
n
)
{\displaystyle \Sigma(n)}
. Studies in Logic and the Foundations of Mathematics. Vol. 60. Elsevier, 1970. 377-405.
↑ 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.
↑ T. Arai. Ordinal diagrams for recursively Mahlo universes. Archive for Mathematical Logic 39.5 (2000): 353-391.
↑ T. Arai. Ordinal diagrams for
Π
3
{\displaystyle \Pi_3}
-reflection. The Journal of Symbolic Logic 65.3 (2000): 1375-1394.
↑ T. Arai. Proof theory for theories of ordinals—I: recursively Mahlo ordinals. Annals of Pure and applied Logic 122.1-3 (2003): 1-85.
↑ T. Arai. Proof theory for theories of ordinals II:
Π
3
{\displaystyle \Pi_3}
-reflection. Annals of Pure and Applied Logic 129.1-3 (2004): 39-92.
↑ T. Arai. Proof Theory for Theories of Ordinals III:
Π
n
{\displaystyle \Pi_n}
-Reflection. Gentzen's Centenary. Springer, Cham, 2015. 357-424.
↑ T. Arai. Wellfoundedness Proofs by Means of Non-Monotonic Inductive Definitions I:
Π
2
0
{\displaystyle \Pi^0_2}
-Operators. Journal of Symbolic Logic (2004): 830-850.
↑ 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.
↑ 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.
↑ 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
↑ M. Okada, and Y. Takahashi. On quasi ordinal diagram systems. Electronic Proceedings in Theoretical Computer Science, EPTCS 288 (2019): 38-49.
↑ 新井敏康. 竹内の基本予想について. 数学 40.4 (1988): 322-337.
↑ T. Arai. An introduction to finitary analyses of proof figures. LONDON MATHEMATICAL SOCIETY LECTURE NOTE SERIES (1999): 1-26.
↑ W. Buchholz. A survey on ordinal notations around the Bachmann–Howard ordinal. Feferman on Foundations. Springer, Cham, 2017. 71-100.