順序数解析(ordinal analysis)とは、算術や集合論の形式的な理論に、その理論が超限帰納法を証明できる整列順序の長さの上限などとして定まる順序数(証明論的順序数)を対応させ、理論の強さを測る証明論の分野である。Peano 算術の値は $\varepsilon_0$ で、上からの評価はカット除去と導出の高さにより、下からの評価は Gentzen の跳び上がりの議論により、$\varepsilon_0$ 未満の各順序数までの超限帰納法を理論の中で証明して得られる。より強い理論の値は正規関数の不動点と Veblen の関数で書き表され、$\mathsf{ATR}_0$ の値は $\Gamma_0$ である。
前提知識: Gentzenの無矛盾性証明, Cantor標準形, 超限帰納法
順序数解析(ordinal analysis)は、算術や集合論の形式的な理論 $T$ に、その強さを測る順序数 $|T|$ を対応させる 証明論 の分野である。$|T|$ は、$T$ が超限帰納法を証明できる整列順序の長さの上限、あるいは有限の立場の推論に加えると $T$ の無矛盾性が示せる超限帰納法の長さとして定まり、証明論的順序数 とよばれる。原型は Gentzen による Peano算術 $\mathsf{PA}$ の解析で、答えは $\varepsilon_0$ である。
$\varepsilon_0$ が上限であること、すなわち $\mathsf{PA}$ が順序型 $\varepsilon_0$ 以上の順序に沿った超限帰納法を証明できないことは、Gentzenの無矛盾性証明 の記事の系「超限帰納法が証明できる順序の上限」で証明されている。この記事では、逆に $\varepsilon_0$ 未満のすべての順序数までの超限帰納法が $\mathsf{PA}$ で証明できることを、Gentzen の「跳び上がり」の議論で証明し、両者を合わせて $\mathsf{PA}$ の証明論的順序数が $\varepsilon_0$ にちょうど等しいことを示す。続いて、より強い理論の順序数を書き表すための正規関数と Veblen の関数を述べ、$\Gamma_0$ などの代表的な値を表にまとめる。
| 記号 | 種類 | 内容 |
|---|---|---|
| def-oa-ordinal | 定義 | 証明論的順序数 |
| lem-oa-facts | 補題 | $\varepsilon_0$ の表記についての真な文 |
| lem-oa-jump | 補題 | 跳び上がり:前進的な論理式は $\varphi^+$ も前進的 |
| thm-oa-lower | 定理 | $\varepsilon_0$ 未満の各順序数までの超限帰納法 |
| thm-oa-main | 定理 | $\mathsf{PA}$ の証明論的順序数は $\varepsilon_0$ |
| prop-oa-fixed | 命題 | 正規関数の不動点 |
設定は Gentzenの無矛盾性証明 の記事に合わせる。言語 $L$ は算術の言語に 2 項の関係記号 $\prec$ と 1 項の関係記号 $X$ を加えたもので、$\prec$ には $\mathbb N$ の上の 2 項関係を 1 つ固定して解釈として与え、こうして得た構造を $\mathfrak N$ と書く。$X$ には解釈を与えない。$\mathsf{PA}(X)$ は $L$ のすべての論理式についての帰納法の公理をもつ Peano 算術で、$\mathcal S$ が $\mathfrak N$ で真な $X$ を含まない文の集合のとき $T:=\mathsf{PA}(X)\cup\mathcal S$ とおく(同記事の定義「理論 T」)。$\prec$ の解釈が整礎なとき、$\|\prec\|$ はその階数の上限、整列順序ならその順序型である。
論理式 $\varphi(x)$(他の自由変数を含んでよい)と 2 項の論理式 $R(x,y)$ について、
$$
\mathrm{Prog}_R(\varphi):=\forall x\,\bigl(\forall y\,(R(y,x)\to\varphi(y))\to\varphi(x)\bigr),\qquad
\mathrm{TI}(R,\varphi):=\mathrm{Prog}_R(\varphi)\to\forall x\,\varphi(x)
$$
とおく。$\mathrm{Prog}_R(\varphi)$ は「$\varphi$ は $R$ に沿って 前進的」と読む。$R$ が $\prec$ で $\varphi$ が $X(x)$ のとき、$\mathrm{TI}(\prec,X)$ は同記事のものと同じ文である。$X$ は解釈をもたないので、$T\vdash\mathrm{TI}(\prec,X)$ は、$X$ に任意の論理式を代入した超限帰納法がすべて証明できることを意味する。
$\prec$ の解釈と $\mathcal S$ をすべての可能性にわたって動かしたときの上限
$$
|\mathsf{PA}|:=\sup\bigl\{\|\prec\|\bigm|\prec\text{ の解釈は整礎で、}\mathsf{PA}(X)\cup\mathcal S\vdash\mathrm{TI}(\prec,X)\bigr\}
$$
を $\mathsf{PA}$ の 証明論的順序数 という。
$\mathcal S$ には $X$ を含まない真な文を好きなだけ入れてよいので、$|\mathsf{PA}|$ は「$\prec$ についての事実を何でも使ってよいとき、$X$ についての帰納法の力だけでどこまで超限帰納法が届くか」を測っている。
一般の理論について、Rathjen は有限的に正当化される推論を体現する理論 $\mathsf F$ と、初等的に計算可能な述語についての $\alpha$ までの超限帰納法 $\text{EC-TI}(\alpha)$ を使って、$\mathsf F+\text{EC-TI}(\alpha)\vdash\mathrm{Con}(T)$ となる最小の $\alpha$ を $|T|_{\mathrm{Con}}$ と書き、これを証明論的順序数の定義の候補として挙げている(Rat06 式 (2)、p. 47)。Gentzen の結果は $|\mathsf{PA}|_{\mathrm{Con}}=\varepsilon_0$ と読め、上の定義の $|\mathsf{PA}|$ も $\varepsilon_0$ になる(thm-oa-main)。
$\varepsilon_0$ 未満の順序数は Cantor 標準形 $\omega^{\alpha_1}+\cdots+\omega^{\alpha_n}$($\alpha_1\ge\cdots\ge\alpha_n$)の指数を再び標準形で書くことを繰り返して有限の木で表せる。これを自然数で符号化した $\alpha$ の 符号 $\ulcorner\alpha\urcorner$ と、符号の上の大小 $\lhd$($\ulcorner\alpha\urcorner\lhd\ulcorner\beta\urcorner\iff\alpha<\beta$)、和 $\ulcorner\alpha\urcorner\mathbin{\hat+}\ulcorner\beta\urcorner:=\ulcorner\alpha+\beta\urcorner$、冪 $\hat\omega^{\ulcorner\alpha\urcorner}:=\ulcorner\omega^\alpha\urcorner$ は、どれも初等的に計算可能である(Rat06 Theorem 1.4 と続く段落、pp. 48–49)。符号でない数はどの数とも $\lhd$ の関係にないとする。
計算可能な関係は算術の論理式で定義できる(算術的階層 の記事の定理「算術的な関係と定義可能な関係」)。そこで、符号の全体 $\mathrm{Ord}(x)$、$x\lhd y$、和と冪のグラフを、$X$ と $\prec$ を含まない算術の論理式で表し、和と冪の値を含む論理式はグラフによる略記とし、$\psi(z\mathbin{\hat+}\hat\omega^y)$ は「$v$ が $z\mathbin{\hat+}\hat\omega^y$ の値なら $\psi(v)$」とすべての $v$ について読む。さらに $\mathrm{m}(z,y,0):=z$、$\mathrm{m}(z,y,k+1):=\mathrm m(z,y,k)\mathbin{\hat+}\hat\omega^{y}$($z+\omega^y\cdot k$ の符号)も同様に表す。$\hat0:=\ulcorner0\urcorner$、$\hat1:=\ulcorner1\urcorner$ と書き、$\forall x\lhd a\ \psi$ は $\forall x\,(x\lhd a\to\psi)$ の略記とする。
次の $X$ を含まない文は $\mathfrak N$ で真である($y,z,w$ は符号を動く)。
1〜3 は符号の定め方と、順序数が $0$・後続・極限のどれか 1 つであることから従う。2 の最後は $z+1$ 未満の順序数が $z$ 以下の順序数であることによる。
4:順序数 の記事の定義「順序数の算術」により $\omega^{y'+1}=\omega^{y'}\cdot\omega=\sup_k\omega^{y'}\cdot k$ で、和は右の引数の極限で上限と交換するので $z+\omega^{y'+1}=\sup_k(z+\omega^{y'}\cdot k)$ である。$w< z+\omega^{y'+1}$ ならある $k$ で $w< z+\omega^{y'}\cdot k$ となり、逆は $z+\omega^{y'}\cdot k\le z+\omega^{y'+1}$(Cantor標準形 の補題「和・積・冪の基本法則」の 2 と結合法則)から従う。和はすべて $\varepsilon_0$ 未満にとどまる($\varepsilon_0$ は $\omega$ の冪と和で閉じている。同記事の定義「$\varepsilon$ 数」)。
5:極限の $y$ では $\omega^y=\sup_{y'< y}\omega^{y'}$ で、4 と同様に $z+\omega^y=\sup_{y'< y}(z+\omega^{y'})$ である。$\square$
$\mathcal F$ を lem-oa-facts の文と、符号の定義に使う論理式についての同様の真な文(値の一意性や、$\beta<\gamma<\varepsilon_0$ についての $\hat\omega^{\ulcorner\beta\urcorner}=\ulcorner\omega^\beta\urcorner$ と $\ulcorner\beta\urcorner\lhd\ulcorner\gamma\urcorner$ のような具体的な符号の真な文など、推論で使う分)の集合とする。以下 $\mathcal S\supseteq\mathcal F$ とし、$T$ の中で $\lhd$ と符号の算術を自由に使う。$\mathcal S=\emptyset$ でも、すなわち $\mathsf{PA}$ そのものでも、算術の論理式について $\varepsilon_0$ 未満の各順序数までの超限帰納法が証明できる(Rat06 p. 47)が、表記の性質の証明を $\mathsf{PA}$ の中で行う部分はこの記事では扱わず、$\mathcal F$ を公理として加えた形で進める。
$\varepsilon_0$ 未満の順序数までの超限帰納法を、次の操作の繰り返しで得る。論理式 $\varphi(x)$ について
$$
\varphi^+(y):=\forall z\,\bigl(\forall w\lhd z\ \varphi(w)\to\forall w\lhd z\mathbin{\hat+}\hat\omega^{y}\ \varphi(w)\bigr)
$$
とおく($z$ は符号を動く)。$\varphi^+(y)$ は「$\varphi$ がある所まで成り立てば、そこから $\omega^y$ 先まで成り立つ」という主張である。以下 $\mathrm{Prog}(\varphi)$ は $\lhd$ に沿った前進性 $\mathrm{Prog}_\lhd(\varphi)$ を表す。
$L$ のすべての論理式 $\varphi$ について、$T\vdash\mathrm{Prog}(\varphi)\to\mathrm{Prog}(\varphi^+)$ である。
$T$ の中で議論する。$\mathrm{Prog}(\varphi)$ を仮定する。$y$ が符号でなければ $z\mathbin{\hat+}\hat\omega^y$ の値がないので $\varphi^+(y)$ は空虚に成り立つ。符号 $y$ について $\forall y'\lhd y\ \varphi^+(y')$ を仮定する。$\varphi^+(y)$ を示すため、$z$ をとって $\forall w\lhd z\ \varphi(w)$ を仮定し、$\forall w\lhd z\mathbin{\hat+}\hat\omega^y\ \varphi(w)$ を示す。lem-oa-facts の 3 により 3 つの場合がある。
$y=\hat0$ の場合. $\hat\omega^{\hat0}=\hat1$ なので、lem-oa-facts の 2 により $w\lhd z\mathbin{\hat+}\hat1$ は $w\lhd z$ または $w=z$ である。前者は仮定から、後者は仮定 $\forall w\lhd z\ \varphi(w)$ と $\mathrm{Prog}(\varphi)$ から $\varphi(z)$ である。
$y=y'\mathbin{\hat+}\hat1$ の場合. $y'\lhd y$ なので $\varphi^+(y')$ が使える。$\psi(k):=\forall w\lhd\mathrm m(z,y',k)\ \varphi(w)$ とおき、$k$ についての帰納法の公理($\psi$ は $L$ の論理式)で $\forall k\,\psi(k)$ を示す。$\psi(0)$ は仮定そのものである。$\psi(k)$ を仮定すると、$\varphi^+(y')$ を $z:=\mathrm m(z,y',k)$ に使って $\forall w\lhd\mathrm m(z,y',k)\mathbin{\hat+}\hat\omega^{y'}\ \varphi(w)$、すなわち $\psi(k+1)$ を得る。lem-oa-facts の 4 により、$w\lhd z\mathbin{\hat+}\hat\omega^y$ ならある $k$ で $w\lhd\mathrm m(z,y',k)$ なので、$\varphi(w)$ である。
$y$ が極限の場合. $w\lhd z\mathbin{\hat+}\hat\omega^y$ なら、lem-oa-facts の 5 によりある $y'\lhd y$ で $w\lhd z\mathbin{\hat+}\hat\omega^{y'}$ である。$\varphi^+(y')$ を同じ $z$ に使えば $\varphi(w)$ を得る。
以上で $\varphi^+(y)$ が示され、$\mathrm{Prog}(\varphi^+)$ が得られた。$\square$
この証明で通常の帰納法を使うのは後続の場合だけで、帰納法をかける論理式 $\psi$ は $\varphi$ より量化記号が多い。$\varphi^{++}$、$\varphi^{+++}$ と跳び上がりを重ねるたびに論理式は複雑になる。$\mathsf{PA}$ が $\varepsilon_0$ の手前で止まるのは、有限回しか重ねられないからである。
$\omega_0(\alpha):=\alpha$、$\omega_{k+1}(\alpha):=\omega^{\omega_k(\alpha)}$ とおく(Gentzenの無矛盾性証明 の記事の定義「塔とその上限 $\varepsilon_0$」)。$\omega_{k+1}(1)=\tau_k$ で、$\varepsilon_0=\sup_k\omega_k(1)$ である。
1. $k$ についての(記事の外の)帰納法で、すべての $\varphi$ について同時に示す。
$k=0$:$\omega_0(1)=1$ である。$x\lhd\hat1$ なら lem-oa-facts の 2($z=\hat0$)により $x=\hat0$ で、$\hat0$ の下には何もないので、$\mathrm{Prog}(\varphi)$ から $\varphi(\hat0)$ である。
$k\to k+1$:$c:=\ulcorner\omega_k(1)\urcorner$ とおく。$\mathrm{Prog}(\varphi)$ を仮定すると、lem-oa-jump により $\mathrm{Prog}(\varphi^+)$ である。帰納法の仮定を論理式 $\varphi^+$ に使うと $\forall y\lhd c\ \varphi^+(y)$ で、これと $\mathrm{Prog}(\varphi^+)$ から $\varphi^+(c)$ を得る。$\varphi^+(c)$ を $z:=\hat0$ に使うと、前提 $\forall w\lhd\hat0\ \varphi(w)$ は lem-oa-facts の 2 により空虚に成り立つので、$\forall w\lhd\hat0\mathbin{\hat+}\hat\omega^c\ \varphi(w)$ を得る。$\hat0\mathbin{\hat+}\hat\omega^c=\hat\omega^c=\ulcorner\omega_{k+1}(1)\urcorner$ である。
2. $\|\prec\|=\alpha$ は、$\prec$ が $\alpha$ 未満の符号の上では $\alpha$ の順序と同型で、ほかの数は孤立していることから従う。$\alpha<\varepsilon_0$ なので $\alpha<\omega_k(1)$ となる $k$ があり、$\ulcorner\alpha\urcorner\lhd\ulcorner\omega_k(1)\urcorner$ は $\mathcal F$ に含まれる真な文である。$T$ の中で $\mathrm{Prog}_\prec(X)$ を仮定し、$\varphi(x):=\bigl(x\lhd\ulcorner\alpha\urcorner\to X(x)\bigr)$ とおく。
$\mathrm{Prog}(\varphi)$ を示す。$x$ について $\forall y\lhd x\ \varphi(y)$ を仮定し、$x\lhd\ulcorner\alpha\urcorner$ とする。$D_\alpha$ により $y\prec x$ は $y\lhd x$ を意味し、そのとき $y\lhd\ulcorner\alpha\urcorner$ でもあるので $\varphi(y)$ から $X(y)$ である。よって $\mathrm{Prog}_\prec(X)$ から $X(x)$ で、$\varphi(x)$ が成り立つ。
1 により $\forall x\lhd\ulcorner\omega_k(1)\urcorner\ \varphi(x)$ で、$x\lhd\ulcorner\alpha\urcorner$ なら推移律により $x\lhd\ulcorner\omega_k(1)\urcorner$ なので $X(x)$ である。$x\lhd\ulcorner\alpha\urcorner$ でない $x$ には、$D_\alpha$ により $\prec$ で下にある数がないので、$\mathrm{Prog}_\prec(X)$ から $X(x)$ である。よって $\forall x\,X(x)$ である。$\square$
$|\mathsf{PA}|=\varepsilon_0$ である。さらに上限は達成されない:$\prec$ の解釈が整礎で $\mathsf{PA}(X)\cup\mathcal S\vdash\mathrm{TI}(\prec,X)$ なら $\|\prec\|<\varepsilon_0$ である。
後半は Gentzenの無矛盾性証明 の系「超限帰納法が証明できる順序の上限」そのものである。とくに $|\mathsf{PA}|\le\varepsilon_0$。逆に、thm-oa-lower の 2 により、各 $\alpha$($0< \alpha< \varepsilon_0$)について $\|\prec\|=\alpha$ で超限帰納法が証明できる $\prec$ と $\mathcal S$ があるので、$|\mathsf{PA}|\ge\sup_{\alpha<\varepsilon_0}\alpha=\varepsilon_0$ である。$\square$
上の評価は Gentzen の解析の半分であり、Gentzenの無矛盾性証明 の記事の主定理($\mathsf{PA}$ の証明を高さ $\varepsilon_0$ 未満のカットのない無限の導出に移す)がもう半分である。順序数解析の一般の手順もこの 2 つからなる。理論の証明を無限の導出に埋め込んでカットを除き、導出の高さで超限帰納法の長さを上から抑える。逆に、跳び上がりに当たる議論で理論の中から整列性を証明して、下から抑える。
$\mathsf{PA}$ より強い理論では $\varepsilon_0$ を超える順序数が現れ、Cantor 標準形だけでは名前が足りない。そこで順序数の関数の不動点を順に数え上げる。順序数から順序数への関数 $f$ が 正規関数 であるとは、狭義単調増加で、極限順序数 $\lambda$ で $f(\lambda)=\sup_{\xi<\lambda}f(\xi)$ となることをいう(Rat06 Definition 1.9、p. 54)。$f(\alpha)=\alpha$ となる $\alpha$ を $f$ の 不動点 という。
$f$ が正規関数なら、各順序数 $\alpha$ について、$\alpha$ 以上の $f$ の不動点がある。不動点の集まりの上限(集合であるとき)も不動点である。したがって不動点を小さい順に並べる関数 $f'$ も正規関数である。
$\alpha_0:=\alpha$、$\alpha_{n+1}:=f(\alpha_n)$ とおく。Cantor標準形 の補題「和・積・冪の基本法則」の 4 により $f(\xi)\ge\xi$ なので、列は広義に増加する。ある $n$ で $\alpha_{n+1}=\alpha_n$ なら $\alpha_n$ が求める不動点である。そうでなければ $\beta:=\sup_n\alpha_n$ は極限順序数で、連続性から $f(\beta)=\sup_nf(\alpha_n)=\sup_n\alpha_{n+1}=\beta$ である。不動点の集合 $A$ の上限 $\gamma$ が $A$ に属さなければ $\gamma$ は極限で、$\{f(\xi)\mid\xi\in A\}=A$ は $\gamma$ の中で共終なので、連続性から $f(\gamma)=\gamma$ である。$\square$
Veblen の関数 を $\varphi_0(\beta):=\omega^\beta$、$\varphi_{\alpha+1}:=\varphi_\alpha'$、極限 $\lambda$ では $\varphi_\lambda$ を「すべての $\alpha<\lambda$ の $\varphi_\alpha$ の値域に共通する順序数」を小さい順に並べる関数と定める(Rat06 Definition 1.11、p. 55 の構成を $\omega^\beta$ から始めたもの)。$\varphi_1(\beta)$ は $\beta$ 番目の $\varepsilon$ 数 $\varepsilon_\beta$ で、$\varphi_1(0)=\varepsilon_0$ である。すべての $\alpha,\beta<\gamma$ で $\varphi_\alpha(\beta)<\gamma$ となる最小の $\gamma>0$ を $\Gamma_0$ と書く。$\Gamma_0$ は Feferman と Schütte が述語的な手段で到達できない最小の順序数と定めたものである(Rat06 p. 55)。
代表的な理論の証明論的順序数は次のとおりである($|T|=|T|_{\mathrm{Con}}$ の意味。Rat06 p. 57、p. 61。逆数学 の体系の定義はその記事による)。
| 理論 | 証明論的順序数 |
|---|---|
| $\mathsf{RCA}_0$、$\mathsf{WKL}_0$ | $\omega^\omega$ |
| $\mathsf{PA}$、$\mathsf{ACA}_0$ | $\varepsilon_0$ |
| $\mathsf{ATR}_0$ | $\Gamma_0$ |
| KP集合論(無限公理つき) | Bachmann–Howard順序数 |
$\mathsf{ACA}_0$ は $\mathsf{PA}$ と同じ強さをもつ(Rat06 p. 57)。$\Pi^1_1$ の内包公理をもつ体系の順序数は、Veblen の関数の範囲を超え、Bachmann に始まるつぶし関数による表記を要する(同 pp. 55–57)。
| 外す条件 | 例 | 何が成り立たなくなるか |
|---|---|---|
| thm-oa-lower の 2 の $\alpha<\varepsilon_0$ | $\alpha=\varepsilon_0$($\lhd$ 全体を $\prec$ にする) | 主張そのもの:$\mathrm{TI}(\prec,X)$ は証明できない |
| prop-oa-fixed の連続性 | $f(\xi)=\xi+1$ | 主張そのもの:不動点が 1 つもない |
| prop-oa-fixed の狭義単調性 | $f(\xi)=0$ | 主張そのもの:$1$ 以上の不動点がない |
1 行目:$\prec$ は順序型 $\varepsilon_0$ の整列順序なので、$\mathcal F$ を加えても thm-oa-main の後半により証明できない。証明が止まるのは prf-thm-oa-lower の 2 で $\alpha<\omega_k(1)$ となる $k$ がとれない所である。2 行目:$f$ は狭義単調増加だが、$f(\omega)=\omega+1\ne\omega=\sup_nf(n)$ で連続でなく、すべての $\xi$ で $f(\xi)\ne\xi$ である。3 行目:定数関数は極限で上限と交換するが、不動点は $0$ だけである。
Rathjen は順序数解析の成果を、強い古典的な理論の構成的な理論に対する無矛盾性、保存拡大の形の還元、組合せ論の独立性、証明可能な関数と順序数の分類の 4 つにまとめている(Rat06 §2.5、p. 62)。組合せ論の例として、Goodsteinの定理 と Paris–Harringtonの定理 は $\mathsf{PA}$ で証明できず、その証明や証明できない理由に $\varepsilon_0$ が現れる。順序数の表記系から生まれた結果として、Friedman による Kruskalの木定理 の拡張がある(同 p. 62)。
def-oa-ordinal は Gentzenの無矛盾性証明 の記事の設定に合わせたこの記事の定式化で、Rat06 式 (2)、p. 47 の $|T|_{\mathrm{Con}}$ とは別の定め方である。両者が $\mathsf{PA}$ で一致することは、Gentzen の結果(Rat06 式 (1)、p. 47)と thm-oa-main による。跳び上がりの議論(lem-oa-jump・thm-oa-lower)は Gentzen によるもので、この記事の証明は表記の性質を真な文として加えた形に書き直したものである。表の値は Rat06 の引用で、この記事では証明しない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する