算術の部分体系(subsystems of arithmetic)とは、Peano 算術の帰納法の公理や二階算術の内包公理を制限して得られる、弱い算術の理論の族である。帰納法を $\Sigma_n$ 論理式に制限した理論 $\mathsf{I\Sigma}_n$ は階段をなし、段ごとに証明できる関数の範囲と無矛盾性の強さが変わる。たとえば $\mathsf{I\Sigma}_1$ の $\Sigma_1$ 定義可能関数は原始再帰関数と一致し、$\mathsf{I\Sigma}_{n+1}$ からは $\mathsf{I\Sigma}_n$ の無矛盾性が導ける。
前提知識: Peano算術, 算術的階層, Gödelの不完全性定理
算術の部分体系(subsystems of arithmetic)とは、Peano算術 の帰納法の公理や二階算術の内包公理を制限して得られる、弱い算術の理論の族である。中心の問いは、ある定理の証明に帰納法がどれだけ要るか、帰納法を弱めると全域であると証明できる関数と示せる無矛盾性がどう変わるか、の 2 つである。
$\mathsf{PA}$ は自然数の性質のほとんどを証明するが、普通の証明で使う帰納法は、ごく単純な形の論理式についてのものであることが多い。そこで、帰納法を当てる論理式を量化子の複雑さで制限すると、理論の強さの階段ができる。階段の 1 段ごとに証明できる関数の範囲と無矛盾性の強さが対応し、それらを測ることが分野の基本の仕事になる。この記事はその地図で、個々の定理の証明は多く持ち込まず、入る記事と文献を示す。
量化子の数え方を先に決める。算術の言語は $0,S,+,\cdot,\le$ からなり、$t$ を項として $(\forall x\le t)$、$(\exists x\le t)$ の形の量化子を有界量化子という。
すべての量化子が有界である論理式を $\Delta_0$ 論理式といい、$\Sigma_0=\Pi_0=\Delta_0$ とする。$n\ge0$ について、$\exists\vec x\,\varphi$($\varphi$ は $\Pi_n$)の形の論理式を $\Sigma_{n+1}$ 論理式、$\forall\vec x\,\varphi$($\varphi$ は $\Sigma_n$)の形の論理式を $\Pi_{n+1}$ 論理式という。ここで $\vec x$ は空でもよい。
これは集合の階層である 算術的階層 を、論理式の形で述べたものである。
論理式の族 $\Phi$ について、$\Phi$-帰納法とは、$A\in\Phi$(他の自由変数を許す)についての図式
$$
A(0)\land\forall x\,(A(x)\to A(Sx))\ \to\ \forall x\,A(x)
$$
である。$\Phi$-収集とは、$A\in\Phi$ についての図式
$$
(\forall x\le t)\,\exists y\,A(x,y)\ \to\ \exists z\,(\forall x\le t)(\exists y\le z)\,A(x,y)
$$
である。$\mathsf{Q}$ を $\le$ の定義つきの Robinson算術 として、次のように定める。
$\mathsf{PA}$ は全部の論理式についての帰納法をもつ理論だから、$\mathsf{PA}=\bigcup_n\mathsf{I\Sigma}_n$ である。理論 $T$ が関数 $f$ を $\Sigma_1$ 定義するとは、$f$ のグラフが $\Sigma_1$ 論理式 $A$ で書け、$T\vdash\forall\vec x\,\exists!y\,A(\vec x,y)$ であることをいう。このとき $f$ を $T$ の証明可能全域関数ともいう。
二階の体系は、数と集合の 2 種類の変数をもつ理論で、集合の存在を保証する内包公理の強さで分ける。定義は 逆数学 が持つ。
次の表が分野の問いの全体である。結果の詳しい形は、右の列の記事か文献で確かめられる。
| 問い | 代表的な結果 | 入る先 |
|---|---|---|
| 帰納法の強さは階段になるか | $\mathsf{I\Sigma}_{n+1}\Rightarrow\mathsf{B\Sigma}_{n+1}\Rightarrow\mathsf{I\Sigma}_n$。$n\ge1$ でどちらの含意も逆にならない | Bus98a §1.2.4, §3.4 |
| 帰納法の向きは効くか | $n\ge1$ で $\mathsf{I\Sigma}_n$ と $\mathsf{I\Pi}_n$ は同じ定理をもつ | この記事の prop-sa-sigma-pi |
| 帰納法のない算術はどこまでできるか | 真な $\Sigma_1$ 文はすべて $\mathsf{Q}$ で証明できる | Robinson算術 |
| 乗法を除くとどうなるか | 加法だけの算術は決定可能で、乗法は定義できない | Presburger算術 |
| 全域と証明できる関数は何か | $\mathsf{I\Sigma}_1$ の $\Sigma_1$ 定義可能関数は原始再帰関数とちょうど一致する | 原始再帰関数、Bus98a §1.2.10, Thm 3.1.1 |
| 有界な理論の成長の限界は何か | 有界な理論(公理が $\Pi_1$ 論理式で書ける理論)が $\forall\vec x\,\exists y\,A$($A$ は有界)を証明すれば、$y$ は項で抑えられる(Parikh の定理) | Bus98a §1.2.7 |
| 無矛盾性はどの段で示せるか | $\mathsf{I\Sigma}_{n+1}\vdash\mathrm{Con}(\mathsf{I\Sigma}_n)$。$\mathsf{I\Delta}_0$ に指数関数の全域性を加えても $\mathrm{Con}(\mathsf{Q})$ は証明できない(Wilkie–Paris) | Bus98a §3.4, Thm 4.3、Gödelの不完全性定理 |
| 公理を足しても増えない文はどれか | $\mathsf{B\Sigma}_{n+1}$ は $\mathsf{I\Sigma}_n$ 上で $\Pi_{n+2}$ 文について保存的である(Parsons) | 保存拡大、Bus98a §3.4.1 |
| $\mathsf{PA}$ の外にある自然な命題は何か | 色分けに対して「最小元より多くの元をもつ同色の有限集合」が見つかる $m$ の存在は、真だが $\mathsf{PA}$ で証明できない(Paris–Harringtonの定理) | Hal12 Cor. 2.6, p. 22、Bus98a p. 122 |
| $\mathsf{PA}$ の強さを順序数で測れるか | 超限帰納法を $\varepsilon_0$ まで許すと $\mathrm{Con}(\mathsf{PA})$ が示せる | Gentzenの無矛盾性証明 |
| 計算量と対応する理論はあるか | 有界算術 $S^1_2$ の $\Sigma^b_1$ 定義可能関数は多項式時間計算可能関数とちょうど一致する(Buss) | Bus98a Thm 1.3.4.1, §3.2 |
| 普通の定理に要る公理はどれか | 多くの定理が 5 つの二階の体系のどれかと同値になる | 逆数学、Sim09 §§I.7–I.11 |
二階の側を、一階の階段と結ぶ表にすると次のようになる。
| 二階の体系 | 同値または証明できる定理の例 | 一階の部分 |
|---|---|---|
| $\mathsf{RCA}_0$ | 中間値の定理、Baireのカテゴリー定理 | $\mathsf{I\Sigma}_1$ 相当 |
| $\mathsf{WKL}_0$ | 閉区間の Heine–Borel 被覆、Gödel の完全性定理 | $\mathsf{RCA}_0$ と同じ |
| $\mathsf{ACA}_0$ | Bolzano–Weierstrass の定理、König の補題 | $\mathsf{PA}$ |
| $\mathsf{ATR}_0$ | 可算整列順序の比較、開ゲームの決定性 | この表では扱わない |
| $\Pi^1_1\text{-}\mathsf{CA}_0$ | Cantor–Bendixsonの定理 | この表では扱わない |
出典は Sim09 の Thm I.8.3, I.9.3, I.10.3, I.11.5, I.9.4 と Remark I.3.3, I.7.6, I.10.5 である。$\mathsf{RCA}_0$ と $\mathsf{WKL}_0$ は一階の部分が同じで、集合についての定理の強さだけが違う。
最初の例は、帰納法の向きを変えても理論が変わらないことの完全な証明である。$\mathsf{I\Delta}_0$ で次の基本性質が帰納法で示せることだけを使う。$0+y=y$、$Sz+y=S(z+y)$、$z+a=a\to z=0$、$Sy\le a\to y\le a$。
$n\ge1$ のとき、$\mathsf{I\Sigma}_n$ と $\mathsf{I\Pi}_n$ は同じ定理をもつ。
$n\ge1$ なので $\Delta_0$ 論理式は $\Sigma_n$ でも $\Pi_n$ でもあり、どちらの理論も $\mathsf{I\Delta}_0$ を含む。
$\mathsf{I\Pi}_n$ が $\Sigma_n$-帰納法を導くことを示す。$\varphi$ を $\Sigma_n$ 論理式とし、$\varphi(0)$ と $\forall x\,(\varphi(x)\to\varphi(Sx))$ を仮定する。ある $a$ で $\neg\varphi(a)$ が成り立つとして矛盾を導く。
$$
\psi(y):=\forall z\,(z+y=a\to\neg\varphi(z))
$$
は(全称量化子を前に出すと)$\Pi_n$ 論理式と同値である。$\psi(0)$ は $\neg\varphi(a)$ である。$\psi(y)$ を仮定し、$z+Sy=a$ とすると $Sz+y=a$ なので $\neg\varphi(Sz)$ となり、仮定の対偶から $\neg\varphi(z)$ を得る。よって $\psi(Sy)$ が成り立つ。$\Pi_n$-帰納法から $\psi(a)$ を得る。$0+a=a$ だから $\neg\varphi(0)$ となり、$\varphi(0)$ と矛盾する。
$\mathsf{I\Sigma}_n$ が $\Pi_n$-帰納法を導くことを示す。$\varphi$ を $\Pi_n$ 論理式とし、同じ仮定をおいて $\neg\varphi(a)$ とする。今度は
$$
\chi(y):=y\le a\to\exists z\,(z+y=a\land\neg\varphi(z))
$$
をとると、$\chi$ は $\Sigma_n$ 論理式と同値である。$\chi(0)$ は $z=a$ で成り立つ。$\chi(y)$ を仮定し $Sy\le a$ とする。$y\le a$ だから $z+y=a$、$\neg\varphi(z)$ となる $z$ がある。$\varphi(0)$ なので $z\ne0$ であり、$z=Sw$ と書ける。$w+Sy=Sw+y=a$ で、仮定の対偶から $\neg\varphi(w)$ となる。よって $\chi(Sy)$ が成り立つ。$\Sigma_n$-帰納法から $\chi(a)$ を得る。$z+a=a$ から $z=0$ となるので $\neg\varphi(0)$ であり、矛盾する。
次の例は、1 段の差が関数の成長の差として見えることを示す。
$2^x=y$ というグラフは $\Delta_0$ 論理式 $\mathrm{Exp}(x,y)$ で書け、$\mathsf{I\Delta}_0$ は $\mathrm{Exp}(0,1)$ と $\mathrm{Exp}(x,y)\to\mathrm{Exp}(Sx,2y)$ を証明する(Bus98a §1.3.1)。
$\exists y\,\mathrm{Exp}(x,y)$ は $\Sigma_1$ 論理式だから、$\mathsf{I\Sigma}_1$ はこの論理式の帰納法で $\forall x\,\exists y\,\mathrm{Exp}(x,y)$ を証明する。
一方、$\mathsf{I\Delta}_0$ はこの文を証明しない。$\mathsf{I\Delta}_0$ は有界な理論なので、証明できるとすると Parikh の定理から項 $t(x)$ があって $\forall x\,(\exists y\le t(x))\,\mathrm{Exp}(x,y)$ が証明できる。$\mathbb N$ は $\mathsf{I\Delta}_0$ のモデルだから、すべての $x$ で $2^x\le t(x)$ となるが、$t(x)$ は $x$ の多項式の値であり、これは成り立たない。
この例は、証明論的な強さの測り方の見本でもある。$\Sigma_1$ 定義可能関数の族は、$\mathsf{I\Delta}_0$ では多項式の増大に抑えられ、$\mathsf{I\Sigma}_1$ では原始再帰関数全体に広がる。
「すべての数値 $\bar n$ について $T\vdash A(\bar n)$ なら $T\vdash\forall x\,A(x)$」という含意は成り立たない。$T=\mathsf{I\Delta}_0$、$A(x):=\exists y\,\mathrm{Exp}(x,y)$ がその反例である。
最後に、階段が無限に続くことから分かる帰結を述べる。
$\mathsf{PA}$ は有限個の公理で公理化できない。
$\mathsf{PA}$ が有限個の文で公理化できるとする。それらの文の証明は有限個の帰納法の公理しか使わないので、ある $n\ge1$ で $\mathsf{I\Sigma}_n$ から証明できる。よって $\mathsf{PA}=\mathsf{I\Sigma}_n$ である。$\mathsf{I\Sigma}_{n+1}\vdash\mathrm{Con}(\mathsf{I\Sigma}_n)$(Bus98a §3.4)だから $\mathsf{I\Sigma}_n\vdash\mathrm{Con}(\mathsf{I\Sigma}_n)$ となる。$\mathsf{I\Sigma}_n$ は $\mathbb N$ をモデルにもつので無矛盾であり、これは Gödelの不完全性定理 の第 2 定理に反する。
| 段階 | 読む記事 | 得るもの |
|---|---|---|
| 1 | Robinson算術、Peano算術 | 公理と $\Sigma_1$ 完全性、超準モデルの感覚 |
| 2 | 算術的階層、原始再帰関数 | 量化子の数え方と関数の階層 |
| 3 | Gödelの不完全性定理、Hilbertの第2問題 | 無矛盾性の文の意味 |
| 4 | 証明論、Gentzenの無矛盾性証明 | 順序数による測り方 |
| 5 | 逆数学、保存拡大 | 二階の体系と保存性 |
一階の階段に進みたい読者には Bus98a が、二階の体系に進みたい読者には Sim09 の第 I 章が案内になる。有限の組合せ論の独立命題から入るなら Ramseyの定理 が近い。
有界算術 の理論の列 $S^1_2\subseteq T^1_2\subseteq S^2_2\subseteq T^2_2\subseteq\cdots$ が互いに異なるかどうかは、Bus98a の時点で未解決の問題である。階層の和 $S_2$ が有限個の公理で書けることと、$S_2$ が多項式階層の崩壊を証明することは同値である(Bus98a §3.3)。したがってこの問題は、計算量の階層が崩壊しないという予想と結びついている。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する