## 2. 形式体系とペアノ算術
### 2.1. 証明を機械が検査できるようにする
普段の数学で「証明」と呼んでいるものは日本語や英語の文章で、行間には読者の理解が詰まっています。それでは「この体系では証明できない」という否定的な主張を扱えません。何が証明かが決まっていなければ、証明が存在しないことも言えないからです。そこで、証明を完全に機械的な対象に置き換えます。
形式体系は次の 3 つの組で与えられる。
1. **言語** $\mathcal{L}$：定数記号・関数記号・述語記号の集合。これと論理記号 $\neg,\wedge,\vee,\to,\forall,\exists,=$ および変数記号から、**項**と**論理式**が文法規則によって定まる。自由変数を持たない論理式を**閉論理式**（文）という。
2. **公理**：$\mathcal{L}$ の論理式の集合。述語論理の論理公理と、理論固有の公理からなる。
3. **推論規則**：有限個の論理式から 1 つの論理式を導く規則の有限リスト（たとえば $\varphi$ と $\varphi\to\psi$ から $\psi$ を導く三段論法）。
論理式の有限列 $\varphi_1,\varphi_2,\dots,\varphi_k$ が理論 $T$ における $\varphi$ の**証明**であるとは、$\varphi_k$ が $\varphi$ と一致し、かつ各 $\varphi_i$ が公理であるか、$\varphi_1,\dots,\varphi_{i-1}$ のいくつかに推論規則を適用して得られることをいう。$\varphi$ の証明が存在するとき $T\vdash\varphi$ と書き、存在しないとき $T\nvdash\varphi$ と書く。
決定的に重要なのは、**与えられた記号列が証明かどうかの判定に、意味の理解が一切要らない**ことです。各行が公理の形をしているか、規則の形に当てはまるかを照合するだけで済みます。この性質が、証明という概念を算術の中に持ち込む足場になります。
### 2.2. ペアノ算術
言語を $\mathcal{L}_A=\{0,S,+,\cdot\}$ とする（$0$ は定数、$S$ は 1 変数関数記号、$+$ と $\cdot$ は 2 変数関数記号）。$x < y$ は $\exists z\,(x+Sz=y)$ の、$x\le y$ は $\exists z\,(x+z=y)$ の略記とする。自然数 $n$ に対し**数項** $\overline{n}$ を $\underbrace{S\cdots S}_{n\ \text{個}}0$ で定める。
**ロビンソン算術 $Q$** は次の 7 つの公理からなる。
$$
\begin{aligned}
&\text{(Q1)}\ \forall x\,(Sx\ne 0) &&\text{(Q2)}\ \forall x\forall y\,(Sx=Sy\to x=y)\\
&\text{(Q3)}\ \forall x\,(x\ne 0\to\exists y\,(x=Sy)) &&\text{(Q4)}\ \forall x\,(x+0=x)\\
&\text{(Q5)}\ \forall x\forall y\,(x+Sy=S(x+y)) &&\text{(Q6)}\ \forall x\,(x\cdot 0=0)\\
&\text{(Q7)}\ \forall x\forall y\,(x\cdot Sy=x\cdot y+x) &&
\end{aligned}
$$
**ペアノ算術 $\mathrm{PA}$** は $Q$ から (Q3) を除いたものに、次の**帰納法図式**を加えた理論である：自由変数を持つ各論理式 $\varphi(x,\boldsymbol{y})$ に対し
$$
\forall\boldsymbol{y}\Big[\big(\varphi(0,\boldsymbol{y})\wedge\forall x\,(\varphi(x,\boldsymbol{y})\to\varphi(Sx,\boldsymbol{y}))\big)\to\forall x\,\varphi(x,\boldsymbol{y})\Big]
$$
を公理とする。
$\mathrm{PA}$ では (Q3) が帰納法から証明できるので、$\mathrm{PA}$ は $Q$ のすべての公理を証明します。$Q$ は帰納法を欠くきわめて弱い理論で、$\forall x\,(x+0=0+x)$ すら証明できません。それでも不完全性定理には $Q$ で足ります。ここが定理の射程の広さを生みます。
帰納法は 1 本の公理ではなく、論理式ごとに 1 本ずつ用意される**無限個**の公理の族です。「すべての部分集合について」と量化したいのに、一階の言語では集合を量化できないので、「論理式で定義できる部分集合について」に弱めるほかないからです。その代わり、与えられた論理式が帰納法図式の形をしているかは機械的に判定できます。この「公理集合が機械的に判定できる」という性質が第 3 節の主役になります。なお $\mathrm{PA}$ が有限個の公理では書けないことも知られています（Kaye の本を参照）。
デデキントの元来のペアノ公理（
）は二階のもので、帰納法を「$0$ を含み $S$ で閉じた**すべての部分集合**は全体である」と述べます。この形なら、公理を満たす構造は同型を除き $\mathbb{N}$ ただ 1 つです。しかし二階論理には、健全でありかつ完全な、有限的に検査できる証明体系が存在しません。一階に降りることで証明の機械的検査を手に入れ、代償として「$\mathbb{N}$ 以外のモデル」（
）を招き入れるわけです。
## 3. 体系に何を望むか
### 3.1. メタな性質を定義する
$T$ を $\mathcal{L}_A$ の理論（閉論理式の集合）とする。
- $T$ が**無矛盾**であるとは、$T\vdash\varphi$ と $T\vdash\neg\varphi$ が同時に成り立つような閉論理式 $\varphi$ が存在しないことをいう。
- $T$ が**完全**であるとは、任意の閉論理式 $\varphi$ について $T\vdash\varphi$ または $T\vdash\neg\varphi$ が成り立つことをいう。
- $T$ が**健全**であるとは、$T\vdash\varphi$ ならば $\mathbb{N}\models\varphi$（標準モデル $\mathbb{N}$ で真）が成り立つことをいう。
- $T$ が**帰納的公理化可能**であるとは、与えられた論理式が $T$ の公理かどうかを判定するアルゴリズムが存在することをいう。
- $T$ が**決定可能**であるとは、与えられた閉論理式 $\varphi$ について $T\vdash\varphi$ か否かを判定するアルゴリズムが存在することをいう。
- $T$ が**$\omega$-無矛盾**であるとは、$T\vdash\exists x\,\varphi(x)$ でありながらすべての自然数 $n$ について $T\vdash\neg\varphi(\overline{n})$ となるような論理式 $\varphi(x)$ が存在しないことをいう。
「完全」という語は 2 つの意味で使われます。ここでの完全性は「どの文についても賛否のどちらかを言える」という**理論の完全性**です。ゲーデルの**完全性定理**（1929 年）の完全性は「すべてのモデルで真な文は証明できる」という**証明体系の完全性**で、別物です。第 7 節でこの 2 つを突き合わせます。
強さの序列は $\text{健全}\Rightarrow\omega\text{-無矛盾}\Rightarrow\text{無矛盾}$ です。健全なら $T\vdash\exists x\,\varphi(x)$ のとき $\mathbb{N}\models\exists x\,\varphi(x)$ なので、ある $n$ で $\mathbb{N}\models\varphi(\overline{n})$ となり、健全性から $T\nvdash\neg\varphi(\overline{n})$ です。また矛盾する理論はすべての文を証明するので $\omega$-無矛盾ではありません。逆向きはどちらも成り立ちません（
）。
### 3.2. 完全な理論は決定できてしまう
$T$ が帰納的公理化可能ならば、$T$ の定理をすべて（重複を許して）順に出力し続けるアルゴリズムが存在する。
$\mathcal{L}_A$ の記号は可算個なので、記号列全体を「長さの短い順、同じ長さなら辞書式順」に機械的に並べられる。証明は記号列の有限列なので、同じ要領で証明の候補すべてを機械的に並べられる。
候補を 1 つずつ取り出し、それが
対偶が効きます。**決定不可能な理論は、帰納的公理化可能なら完全ではありえません。** チャーチとチューリングは 1936 年に、$Q$ を含む無矛盾な理論はどれも決定不可能であることを示しました。$\mathrm{PA}$ の公理集合は機械的に判定できるので、この結果と
だけで「$\mathrm{PA}$ は完全でない」が出ます。ただしこの経路では、証明できない文が何であるかは分かりません。ゲーデルの議論は、その文を名指しで与えるところに価値があります。
### 3.3. 仮定を落とすとどうなるか
第一不完全性定理は「十分な算術を含む」「帰納的公理化可能」「無矛盾」の 3 つを仮定します。どれ 1 つ落としても定理は成り立ちません。
言語を $\{0,S,+\}$ に制限し、公理を (Q1)(Q2)(Q4)(Q5) とこの言語の論理式に対する帰納法図式にした理論を**プレスブルガー算術**といいます。プレスブルガーは 1929 年に、これが完全かつ決定可能であることを示しました。
たとえば「どの数も偶数か奇数か」を表す $\forall x\,\exists y\,(x=y+y\vee x=y+y+S0)$ は $x$ についての帰納法で証明できます。準備として補題 $\forall u\forall v\,(Su+v=S(u+v))$ を $v$ の帰納法で示します（$v=0$ なら (Q4) から両辺とも $Su$、$v$ で成り立てば (Q5) から $Su+Sv=S(Su+v)=SS(u+v)=S(u+Sv)$）。$x=0$ では $y=0$ と取れば (Q4) から $0=0+0$ で第 1 項が成り立ちます。$x=y+y$ なら (Q5)(Q4) より $y+y+S0=S(y+y+0)=S(y+y)=Sx$ なので、同じ $y$ で $Sx$ が第 2 項を満たします。$x=y+y+S0=S(y+y)$ なら $Sy$ を新しい $y$ に取ると、(Q5) と補題から $Sy+Sy=S(Sy+y)=SS(y+y)=Sx$ となり第 1 項を満たします。
完全になる理由の核心は、掛け算がないと定義できる集合が「最終的に周期的」なものに限られ、量化子除去ができる点にあります。裏を返せば、掛け算がないためゲーデル数化に必要な符号化（第 4 節）が行えません。この決定手続きは今日、整数線形算術を扱う SMT ソルバに実装されています。
$\mathrm{Th}(\mathbb{N})=\{\varphi:\mathbb{N}\models\varphi\}$、すなわち標準モデルで真な閉論理式すべての集合は完全です（どの $\varphi$ についても $\varphi$ か $\neg\varphi$ が真だからです）。$\mathbb{N}$ をモデルに持つので無矛盾でもあります。
ではなぜこれで話が終わらないのか。$\mathrm{Th}(\mathbb{N})$ は帰納的公理化可能ではないからです。もしそうなら
矛盾する理論は爆発律によりすべての文を証明するので完全です（
）。こうして 3 つの仮定はいずれも外せないと分かります。
## 4. 算術が自分自身について語る
### 4.1. ゲーデル数化
第一の鍵は、記号列としての論理式や証明に自然数の背番号を与え、「証明である」というメタな性質を、自然数についての性質に翻訳することです。
$\mathcal{L}_A$ の各記号 $s$ に相異なる正の整数 $c(s)$ を割り当てる。記号列 $s_1s_2\cdots s_k$ に対し
$$
\#(s_1s_2\cdots s_k)=p_1^{c(s_1)}p_2^{c(s_2)}\cdots p_k^{c(s_k)}
$$
（$p_i$ は $i$ 番目の素数）と定め、これを**ゲーデル数**という。論理式の有限列（証明）に対しても、各項のゲーデル数を同じ方法で束ねて符号を与える。素因数分解の一意性により $\#$ は単射であり、$\#\varphi$ から $\varphi$ を機械的に復元できる。数項 $\overline{\#\varphi}$ を $\varphi$ の**名前**と呼ぶ。
たとえば $c(0)=1$, $c(S)=3$ と決めておくと、$\overline{1}=S0$ のゲーデル数は $\#(S0)=2^{3}\cdot 3^{1}=24$、$\overline{2}=SS0$ のそれは $2^{3}\cdot 3^{3}\cdot 5^{1}=8\cdot 27\cdot 5=1080$ です。数は巨大になりますが、有限であることと復元可能であることだけが問題なので効率は気にしません。
こうして自然数と論理式の間に機械的な辞書ができました。すると「$y$ は $x$ の証明である」というメタな関係は、自然数の対についての関係になり、素因数分解・列の分解・公理判定・規則の照合だけで判定できるのでアルゴリズムで計算できます。あとはこの関係を $\mathcal{L}_A$ の論理式で書ければよく、それを保証するのが次の黒箱です。
$T$ を帰納的公理化可能な理論とする。自然数の関係
$$
\mathrm{pf}_T=\{(m,n)\ :\ m\ \text{は、ゲーデル数}\ n\ \text{の論理式の}\ T\ \text{における証明の符号}\}
$$
はアルゴリズムで判定できる。(B1) によりこれを表現する論理式 $\mathrm{Pf}_T(y,x)$ を 1 つ固定し、
$$
\mathrm{Prov}_T(x)\ :\equiv\ \exists y\,\mathrm{Pf}_T(y,x)
$$
を**証明可能性述語**という。また $\bot$ を閉論理式 $0=S0$（$Q$ が (Q1) から否定を証明する偽な文）とし、
$$
\mathrm{Con}_T\ :\equiv\ \neg\mathrm{Prov}_T(\overline{\#\bot})
$$
を $T$ の**無矛盾性を表す文**という。
$\mathrm{Con}_T$ は「$0=S0$ の証明は存在しない」と読める、自然数についての文です。ここで注意してほしいのは、$T\vdash\varphi$ という**メタなレベルの事実**と、$T\vdash\mathrm{Prov}_T(\overline{\#\varphi})$ という**$T$ の内部での主張**が別物だということです。前者から後者は出ます（証明が実在すればその符号 $p$ について $T\vdash\mathrm{Pf}_T(\overline{p},\overline{\#\varphi})$ が言えるからです）が、逆は一般に成り立ちません。この非対称性が第 6 節の核心になります。
### 4.2. 対角化補題
第二の鍵は、自分自身の名前について語る文を作ることです。
$T$ を $Q$ のすべての公理を証明する $\mathcal{L}_A$ の理論とする。自由変数がちょうど $x$ 一つである任意の論理式 $\psi(x)$ に対し、閉論理式 $\sigma$ が存在して
$$
T\vdash\ \sigma\leftrightarrow\psi(\overline{\#\sigma})
$$
が成り立つ。
2 変数関数 $\mathrm{sub}$ を、$m$ が自由変数 $x$ を持つ論理式 $\theta$ のゲーデル数であるときは $\mathrm{sub}(m,n)=\#\big(\theta(\overline{n})\big)$、それ以外のときは $\mathrm{sub}(m,n)=0$ と定める。この関数は計算できる。実際、$m$ を素因数分解して $\theta$ を復元し、$x$ の各出現を記号列 $S\cdots S0$（$S$ が $n$ 個）に置き換え、再び符号化すればよく、どの段階も有限回の機械的操作である。
したがって (B1) の後半により、論理式 $\mathrm{Sub}(x,y,z)$ が存在して、すべての $m,n$ について
$$
T\vdash\forall z\,\big(\mathrm{Sub}(\overline{m},\overline{n},z)\leftrightarrow z=\overline{\mathrm{sub}(m,n)}\big)
$$
が成り立つ（$T$ は $Q$ の公理を証明するので、$Q$ で証明できることは $T$ でも証明できる）。ここで
$$
\theta(x)\ :\equiv\ \exists z\,\big(\mathrm{Sub}(x,x,z)\wedge\psi(z)\big)
$$
と置き、$m:=\#\theta$、$\sigma:\equiv\theta(\overline{m})$ とする。$\sigma$ は $\theta$ の自由変数に $\overline{m}$ を代入したものだから、$\mathrm{sub}$ の定義そのものにより $\#\sigma=\mathrm{sub}(m,m)$ である。
上の表現可能性の式に $n:=m$ を代入すると $T\vdash\forall z\,(\mathrm{Sub}(\overline{m},\overline{m},z)\leftrightarrow z=\overline{\#\sigma})$ を得る。これを $\sigma\equiv\exists z\,(\mathrm{Sub}(\overline{m},\overline{m},z)\wedge\psi(z))$ の内部で使えば
$$
T\vdash\ \sigma\ \leftrightarrow\ \exists z\,\big(z=\overline{\#\sigma}\wedge\psi(z)\big)\ \leftrightarrow\ \psi(\overline{\#\sigma})
$$
となり、主張が示された。
この証明のどこにも神秘はありません。$\sigma$ は自分自身の名前を「含んで」いるのではなく、$\theta$ の名前 $\overline{m}$ を含み、$\mathrm{Sub}$ という代入の仕組みを通して自分の名前を**計算する**構造になっています。$\theta$ に $\theta$ 自身の番号を食わせるという手つきは、[濃度と無限](/mathematics/foundations/cardinality-and-infinity) で見たカントールの対角線論法（
）と同じで、名前もそこから来ています。
### 4.3. 真理は算術で書けない
対角化補題の威力を、まず不完全性定理より短い定理で見ておきます。
$\mathcal{L}_A$ の論理式 $\mathrm{True}(x)$（自由変数は $x$ のみ）で、すべての $\mathcal{L}_A$ の閉論理式 $\varphi$ について
$$
\mathbb{N}\models\mathrm{True}(\overline{\#\varphi})\quad\Longleftrightarrow\quad\mathbb{N}\models\varphi
$$
を満たすものは存在しない。
そのような $\mathrm{True}(x)$ が存在したとする。$T:=\mathrm{Th}(\mathbb{N})$ は $Q$ の公理をすべて含む（$Q$ の公理は $\mathbb{N}$ で真だから）ので、
この $\lambda$ は「私は真ではない」と述べる文、すなわち嘘つきのパラドックスの算術版です。ここから見通しが立ちます。**証明可能性は算術の論理式 $\mathrm{Prov}_T$ で書けるのに、真理は算術の論理式では書けない。** もし $T$ の定理が $\mathbb{N}$ の真な文とちょうど一致するなら $\mathrm{Prov}_T$ が真理述語になってしまい、
に反します。だから一致しません。証明できる文の集合は、真な文の集合より狭いのです。
（記号列）"] -->|ゲーデル数化| B["自然数"]
B --> C["「y は x の証明である」
という判定できる関係"]
C -->|表現可能性 B1| D["論理式 Pf(y, x)"]
D --> E["Prov(x) ≡ ∃y Pf(y, x)"]
E --> F["対角化補題"]
F --> G["G ↔ ¬Prov(G の名前)
「私は証明できない」"]
G --> H["第一不完全性定理"]
H --> I["この証明自体を形式化
（導出可能性条件）"]
I --> J["第二不完全性定理
T が Con(T) を証明できない"]`} />
## 5. 第一不完全性定理
$\mathcal{L}_A$ の理論 $T$ が次の 3 条件を満たすとする。
- (i) $T$ は $Q$ のすべての公理を証明する。
- (ii) $T$ は帰納的公理化可能である。
- (iii) $T$ は無矛盾である。
(a) の証明で使ったのは無矛盾性だけです。これは第 6 節でもう一度使います。では、証明も反証もできない $G$ は、結局のところ真なのでしょうか。
$T$ が (i)(ii) を満たし、かつ健全であるとする。このとき $G$ は $\mathbb{N}$ で真であり、しかも $T\nvdash G$ である。
健全性から $T$ は無矛盾である（$T\vdash\varphi$ かつ $T\vdash\neg\varphi$ なら $\mathbb{N}$ で $\varphi$ と $\neg\varphi$ が同時に真になってしまう）。よって
これが「真であるが証明できない命題」の正体です。$G$ は「私は $T$ では証明できない」と述べており、実際に証明できない。だから $G$ の言っていることは正しい。自己言及の含みを取り除けば、$G$ は「ある種の巨大な有限探索が決して当たりを引かない」という、ごく普通の算術の主張です。
## 6. 第二不完全性定理
で使った推論は「$T$ が無矛盾なら $G$ は証明できない、ゆえに $G$ は真」というごく初等的なものでした。初等的ということは、$T$ の内部で再現できるかもしれないということです。実際それができ、結論として $T$ は自分の無矛盾性を証明できなくなります。この形式化を支えるのが、ヒルベルトとベルナイス、そしてレープが整理した次の 3 条件です。
$T$ を $\mathrm{PA}$ のすべての公理を証明する帰納的公理化可能な理論とし、$T$ は無矛盾であるとする。さらに $\mathrm{Prov}_T$ が (D1)(D2)(D3) を満たすように構成されているとする。このとき
$$
T\nvdash\mathrm{Con}_T
$$
である。すなわち $T$ は自分自身の無矛盾性を証明できない。
$G$ を
第 4 段で得た $T\vdash\mathrm{Con}_T\to G$ は、それ自体が味わい深い式です。$G$ という一見奇怪な自己言及の文が、「$T$ は無矛盾である」という自然な主張と $T$ の内部で結びついています。実際、逆向きの $T\vdash G\to\mathrm{Con}_T$ も成り立つので、$G$ と $\mathrm{Con}_T$ は $T$ 上で同値です。
同じ道具立てからレープの定理（1955 年）が出ます。$T\vdash\mathrm{Prov}_T(\overline{\#\varphi})\to\varphi$ ならば $T\vdash\varphi$ である、というものです。「証明できるなら本当だ」と $T$ が言えるのは、そもそも $\varphi$ が証明できる場合に限るわけで、$\varphi:=\bot$ と取れば
## 7. 「真だが証明できない」の読み方
### 7.1. 完全性定理と不完全性定理は矛盾しない
ゲーデルは 1929 年の学位論文で**完全性定理**を証明しました。一階述語論理について、$T$ のすべてのモデルで真な文は $T$ から証明できる（$T\models\varphi$ ならば $T\vdash\varphi$）という定理です。一方 1931 年の不完全性定理は、$T\nvdash G$ かつ $T\nvdash\neg G$ となる $G$ の存在を主張します。この 2 つを並べると
$$
T\nvdash G\ \text{かつ}\ T\nvdash\neg G\ \Longrightarrow\ T\not\models G\ \text{かつ}\ T\not\models\neg G
$$
が従います。つまり $G$ が真になる $T$ のモデルと偽になる $T$ のモデルの**両方が存在する**ということで、
で作った非標準モデルは後者の実例でした。$G$ が「真」だというのは、標準モデル $\mathbb{N}$ を特別扱いしたうえでの言明です。証明できるのは「すべてのモデルで真な文」だけですから、$G$ が証明できないのは当然のことでした。
すると次の問いが残ります。「標準モデル $\mathbb{N}$」とは何なのか。一階の算術の内側からは、$\mathbb{N}$ を他のモデルと区別する手段がありません。$\mathbb{N}$ を素朴に把握できるものとして認めるかどうかは、数学の中の問いというより数学の哲学の問いになります。
### 7.2. よくある誤解
| よく見る言い方 | 正確には |
|---|---|
| 証明も反証もできない問題があるのだから、数学は不完全だ | 特定の理論 $T$ に対して独立な文があるだけです。$T+G$ に移れば $G$ は証明できます。ただし $T+G$ にも新しい独立命題が現れます |
| 不完全性定理は数学が矛盾していることを示した | 逆です。$T$ の無矛盾性を仮定したうえでの結論であり、矛盾する理論はむしろ完全です |
| どんな公理系も不完全である | 「$Q$ を含む」「帰納的公理化可能」「無矛盾」の 3 つが必要です。
と
が反例になります |
| $G$ が真だと人間には分かるのだから、心は機械を超える | 人間に分かるのは「$T$ が無矛盾ならば $G$ は真」という条件付きの主張です。
が示すのは、その条件を体系の内部では正当化できないということです |
最後の行はルーカスとペンローズの議論に関わります。人間の数学的能力が形式体系を超える証拠だという主張ですが、標準的な反論は 2 つです。$G$ の真理を「知る」のは $T$ の無矛盾性を前提にしたときだけで、その前提を無条件には正当化できないこと。そして、人間の推論がアルゴリズム $A$ で記述されるとしても、私たち自身が $A$ を特定し $A$ が無矛盾だと知ることはできないこと。私はこの反論のほうが説得的だと思いますが、決着した論争ではありません。
### 7.3. 体系を強くしても追いつけない
$T_0:=\mathrm{PA}$ とし、$T_{n+1}:=T_n+\mathrm{Con}_{T_n}$ と定めます。$\mathrm{PA}$ が健全なら $\mathrm{Con}_{\mathrm{PA}}$ は $\mathbb{N}$ で真なので $T_1$ も健全で、帰納的に各 $T_n$ が健全かつ無矛盾になります。各段階で 1 つ前の体系の無矛盾性は証明できるようになりますが、
が各 $T_n$ にそのまま適用されるので、$T_n$ は自分の無矛盾性を証明できません。この階層は超限順序数に沿って伸ばすことができ、チューリングの学位論文（1939 年）とフェファーマンの研究（1962 年）が扱っています。不完全性は、公理を機械的に足していく限り、どこまで行っても解消されません。
## 8. リーマン予想は証明不可能か
### 8.1. 論理式の複雑さで見分ける
不完全性定理は「証明できない文が存在する」と言うだけで、私たちが関心を持つ具体的な予想がそうだとは言いません。では、未解決問題が独立である可能性はどれくらいあるのでしょうか。ここで論理式の形が効いてきます。
すべての量化子が $\forall x\le t$ や $\exists x\le t$ の形（有界量化子）である論理式を $\Delta_0$ 論理式といいます。$\Delta_0$ 閉論理式の真偽は有限回の計算で確定します。$\Delta_0$ 論理式 $R$ を用いて $\exists x\,R(x)$ の形に書ける文を $\Sigma_1$ 文、$\forall x\,R(x)$ の形に書ける文を $\Pi_1$ 文といいます。
$T$ を $Q$ のすべての公理を証明する $\mathcal{L}_A$ の理論とし、$\varphi\equiv\forall x\,R(x)$ を $\Pi_1$ 閉論理式（$R$ は $\Delta_0$ 論理式）とする。このとき $T\nvdash\neg\varphi$ ならば $\mathbb{N}\models\varphi$ である。
対偶を示す。$\mathbb{N}\not\models\varphi$ とすると、ある自然数 $n$ について $\mathbb{N}\models\neg R(\overline{n})$ である。$\neg R(\overline{n})$ は有界量化子しか含まない閉論理式、すなわち真な $\Delta_0$ 文だから、(B2) により $Q\vdash\neg R(\overline{n})$ である。$T$ は $Q$ の公理をすべて証明するので $T\vdash\neg R(\overline{n})$、存在汎化により $T\vdash\exists x\,\neg R(x)$、すなわち $T\vdash\neg\varphi$ を得る。
$\Pi_1$ 文が偽ならば、その反例は必ず有限の計算で確認でき、$Q$ 程度の弱い理論でも反証できるということです。したがって $\Pi_1$ 文 $\varphi$ が「$T$ から独立」と示されたなら、後半の「反証できない」から
により $\varphi$ は真だと分かります。**$\Pi_1$ 文の独立性証明は、同時にその真理の証明でもあるのです。** ただし独立性を示す議論は $T$ の外側のメタ理論（通常は $\mathrm{ZFC}$ など）で行われるので、「真である」という結論もそのメタ理論の中での結論です。
### 8.2. リーマン予想の場合
リーマン予想（$\zeta$ 関数の非自明な零点はすべて実部 $1/2$ を持つ）は、一見すると複素解析の主張で算術の階層とは無縁に見えます。ところがラガリアスは 2002 年に、次の初等的な言明と同値であることを示しました。$\sigma(n)=\sum_{d\mid n}d$ を約数の総和、$H_n=\sum_{k=1}^{n}1/k$ を調和数とするとき、
$$
\text{すべての } n\ge 1 \text{ について }\quad \sigma(n)\ \le\ H_n+\exp(H_n)\log H_n
$$
が成り立つことと、リーマン予想は同値です（等号が成り立つのは $n=1$ のときだけです）。
$n=1$ では $\sigma(1)=1$、$H_1=1$ なので右辺は $1+e^{1}\cdot\log 1=1+e\cdot 0=1$ となり、両辺とも $1$ で等号です。$n=4$ では $\sigma(4)=1+2+4=7$、$H_4=1+\tfrac12+\tfrac13+\tfrac14=\tfrac{25}{12}=2.08333\ldots$ で、$\exp(2.08333\ldots)=8.0312\ldots$、$\log(2.08333\ldots)=0.73397\ldots$ ですから右辺は
$$
2.08333\ldots+8.0312\ldots\times 0.73397\ldots=2.08333\ldots+5.8947\ldots=7.978\ldots
$$
となり、$7\le 7.978\ldots$ で不等式が成り立っています。
この不等式の両辺は $n$ から有限回の計算で任意の精度に評価できるので、各 $n$ に対する成否は有限の計算で判定できます。したがってリーマン予想は $\forall n\,R(n)$ の形の $\Pi_1$ 文と同値です。さらに、マチャセビッチによるヒルベルトの第 10 問題の解決から、どんな $\Pi_1$ 文も「ある整数係数多項式方程式が自然数解を持たない」という形に書き換えられることが知られており、リーマン予想も具体的なディオファントス方程式の非可解性として書けます。
ここから
の含意が効いてきます。もし将来「リーマン予想は $\mathrm{PA}$ から独立である」と証明されたら、その瞬間にリーマン予想は真だと分かります。「独立だから真偽が定まらない」という結末は、$\Pi_1$ 文についてはあり得ません。あり得るのは「真だが $\mathrm{PA}$ では証明が届かない、より強い体系が要る」という結末だけです。同じことはゴールドバッハ予想やフェルマー予想にも当てはまります。
現時点で、リーマン予想が $\mathrm{ZFC}$ から独立かどうかは分かっていません。多くの数学者は独立ではないだろうと考えていますが、それは経験に基づく見通しであって定理ではありません。私も同意見ですが、根拠は「数論の主要定理はこれまで通常の数学の範囲で証明されてきた」という帰納的なものにすぎない、とは言っておきます。
### 8.3. 実際に独立と分かっている命題
自然数を**遺伝的 $b$ 進表記**で書くとは、$b$ 進表記の指数もまた $b$ 進で書き、その指数も…と再帰的に書き下すことです。たとえば $266=2^{2^{2+1}}+2^{2+1}+2$ が遺伝的 2 進表記です。グッドスタイン数列は、$g_1=m$ を遺伝的 2 進で書いて底 $2$ をすべて $3$ に置き換えてから $1$ を引いたものを $g_2$ とし、$g_2$ を遺伝的 3 進で書いて底を $4$ に置き換えて $1$ を引いたものを $g_3$ とし、と続けて作ります。**グッドスタインの定理**（1944 年）は、どの $m$ から始めてもこの数列が有限回で $0$ に到達すると主張します。
$m=3$ で最後まで計算します。$g_1=3=2+1$ の底を $3$ にすると $3+1=4$、$1$ を引いて $g_2=3$。$g_2=3=3^1$ の底を $4$ にすると $4$、$1$ を引いて $g_3=3$。$g_3$ は底 $4$ の表記では単に $3$ で底が現れないので、置き換えても $3$、$1$ を引いて $g_4=2$。同様に $g_5=1$、$g_6=0$。数列は $3,3,3,2,1,0$ です。
なぜ必ず $0$ に届くのか。遺伝的表記の底を記号 $\omega$ に置き換えると順序数が得られ、上の例では $\omega+1,\ \omega,\ 3,\ 2,\ 1,\ 0$ と狭義単調減少します。順序数の減少列は無限には続かないので、数列は有限で終わります。この議論には $\varepsilon_0$ 未満の順序数についての超限帰納法が要り、カービーとパリスは 1982 年にこの定理が $\mathrm{PA}$ から独立であることを示しました（L. Kirby and J. Paris, *Bulletin of the London Mathematical Society* 14 (1982), 285–293）。数列は途中で猛烈に増大し、$m=4$ から始めると $0$ に届くまでに $3\cdot 2^{402653211}-2$ 段階かかります。これは $\Pi_2$ 文なので
チャイティンによる別種の不完全性も知られています。各理論 $T$ に定数 $c_T$ が存在し、$T$ はどんな文字列についても「その文字列のコルモゴロフ複雑性は $c_T$ より大きい」を証明できません。ほとんどすべての文字列についてそれは真なのに、です。不完全性は自己言及という仕掛けだけの現象ではありません。
## 9. 演習
矛盾する理論は完全であることを示せ。これにより
## 参考文献
- K. Gödel, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I", *Monatshefte für Mathematik und Physik* 38 (1931), 173–198. 原論文。英訳は J. van Heijenoort (ed.), *From Frege to Gödel*, Harvard University Press, 1967 に収録。
- 前原昭二『数学基礎論入門』朝倉書店、1977 — 形式体系の定義から不完全性定理の証明までを日本語で完結させた古典的な教科書。
- 菊池誠『不完全性定理』共立出版、2014 — 表現可能性・導出可能性条件・第二不完全性定理を現代的な形で詳しく扱っています。
- P. Smith, *An Introduction to Gödel's Theorems*, 2nd ed., Cambridge University Press, 2013 — ロビンソン算術と表現可能性の扱いが丁寧で、第二不完全性定理が証明可能性述語の作り方に依存する点も議論しています。
- R. Kaye, *Models of Peano Arithmetic*, Oxford University Press, 1991 — 非標準モデルと $\mathrm{PA}$ の性質（有限公理化不可能性を含む）。
- J. C. Lagarias, "An Elementary Problem Equivalent to the Riemann Hypothesis", *American Mathematical Monthly* 109 (2002), 534–543. [arXiv:math/0008177](https://arxiv.org/abs/math/0008177)