ゲーデルの不完全性定理：「真だが証明できない」とは何のことか
Prerequisite:濃度と無限：全単射で測る「無限の大小」
This content is not available in your language yet.
0. この記事の要点
Section titled “0. この記事の要点”- 形式体系とは、何が文であり何が証明であるかを、意味を一切参照せず記号の形だけで決めた枠組みです。ペアノ算術 はその代表で、初等整数論の議論の大部分をその内部で再現できます。
- 第一不完全性定理：ごく弱い算術を含み、公理をアルゴリズムで判定でき、無矛盾な理論には、証明も反証もできない閉論理式が存在します。
- 第二不完全性定理：さらにその理論は、自分自身の無矛盾性を表す文 を証明できません。「体系の無矛盾性を体系の内側で確かめる」というヒルベルトの計画は、この素朴な形では実現しません。
- 仕掛けは 2 つです。算術が自分自身について語れること（ゲーデル数化）と、自分の名前を含む文を作れること（対角化補題）。「証明可能性」は算術の論理式で書けるのに「真理」は書けない——この非対称性が不完全性の正体です。
- 「真だが証明できない」の「真」は標準モデル における真です。 のすべてのモデルで真という意味ではないので、ゲーデルの完全性定理と矛盾しません。
- リーマン予想は 文と同値です。したがって「 から独立」と示されたなら、その時点でリーマン予想は真だと分かります。独立性が逃げ道になる余地は、この形の予想については驚くほど狭いのです。
1. 動機：ヒルベルトの計画とその挫折
Section titled “1. 動機：ヒルベルトの計画とその挫折”19 世紀の終わりに、数学の足元は二度揺れました。一度目は非ユークリッド幾何の発見です。2000 年にわたって「疑いようのない真理」とされてきた平行線公準が、取り替え可能な仮定にすぎないと分かりました。二度目はカントールの集合論から出たパラドックスです。「自分自身を要素として含まない集合すべての集合」を考えると矛盾します（ラッセル、1901 年。素朴集合論の限界（Remark 6.4）［The Grammar of Mathematics］）。無限を自由に扱う議論が安全なのか、誰にも保証できなくなりました。
ヒルベルトの解決策は大胆で明快でした。数学の議論を、意味を持たない記号の操作に還元してしまう。公理と推論規則を書き下せば、証明とは「規則に従って組み上げられた記号列」にすぎません。すると「この体系は を導くか」という問いは、記号列についての有限的で具体的な問いになります。これに、疑う余地のない初等的手段（有限の立場）だけで「導かない」と答えられれば、無限を扱う数学の安全性が確保できる——これがヒルベルトの計画です。1928 年の国際数学者会議で、彼は形式体系について 3 つの問いを立てました。
- 完全性：真な命題はすべて証明できるか。
- 無矛盾性：矛盾しないことを証明できるか。
- 決定可能性：命題が証明できるかどうかを判定する機械的手続きはあるか。
1930 年 9 月、ケーニヒスベルクでの講演をヒルベルトはこう締めくくりました。「われわれは知らねばならない、われわれは知るであろう」。ところが同じ会合の席上で、25 歳のクルト・ゲーデルが問い 1 の答えが「否」であることを控えめに報告していました。翌 1931 年の論文で問い 1 と 2 が、1936 年のチャーチとチューリングの仕事で問い 3 が、いずれも否定的に解決されます。
以下では「形式体系」「無矛盾」「完全」を正確に定義し、道具立てを組み立てたうえで、2 つの定理を主張として完全に述べます。証明は、深い準備を要する事実だけを黒箱として切り出し、残りは省略せずに書きます。前提として、論理記号と量化子の扱いは 数学の国語 - 集合と論理（全称記号と存在記号（Definition 5.2）［The Grammar of Mathematics］）、背理法と数学的帰納法は 証明の技術（背理法の正当性（Proposition 6.2）［Techniques of Proof］、数学的帰納法の原理（Theorem 3.2）［Techniques of Proof］）、カントールの対角線論法は 濃度と無限 を使います。
2. 形式体系とペアノ算術
Section titled “2. 形式体系とペアノ算術”2.1. 証明を機械が検査できるようにする
Section titled “2.1. 証明を機械が検査できるようにする”普段の数学で「証明」と呼んでいるものは日本語や英語の文章で、行間には読者の理解が詰まっています。それでは「この体系では証明できない」という否定的な主張を扱えません。何が証明かが決まっていなければ、証明が存在しないことも言えないからです。そこで、証明を完全に機械的な対象に置き換えます。
Definition 2.1（形式体系と証明）
形式体系は次の 3 つの組で与えられる。
- 言語 ：定数記号・関数記号・述語記号の集合。これと論理記号 および変数記号から、項と論理式が文法規則によって定まる。自由変数を持たない論理式を閉論理式（文）という。
- 公理： の論理式の集合。述語論理の論理公理と、理論固有の公理からなる。
- 推論規則：有限個の論理式から 1 つの論理式を導く規則の有限リスト（たとえば と から を導く三段論法）。
論理式の有限列 が理論 における の証明であるとは、 が と一致し、かつ各 が公理であるか、 のいくつかに推論規則を適用して得られることをいう。 の証明が存在するとき と書き、存在しないとき と書く。
決定的に重要なのは、与えられた記号列が証明かどうかの判定に、意味の理解が一切要らないことです。各行が公理の形をしているか、規則の形に当てはまるかを照合するだけで済みます。この性質が、証明という概念を算術の中に持ち込む足場になります。
2.2. ペアノ算術
Section titled “2.2. ペアノ算術”Definition 2.2（ペアノ算術 PA とロビンソン算術 Q）
言語を とする（ は定数、 は 1 変数関数記号、 と は 2 変数関数記号）。 は の、 は の略記とする。自然数 に対し数項 を で定める。
ロビンソン算術 は次の 7 つの公理からなる。
ペアノ算術 は から (Q3) を除いたものに、次の帰納法図式を加えた理論である：自由変数を持つ各論理式 に対し
を公理とする。
では (Q3) が帰納法から証明できるので、 は のすべての公理を証明します。 は帰納法を欠くきわめて弱い理論で、 すら証明できません。それでも不完全性定理には で足ります。ここが定理の射程の広さを生みます。
帰納法は 1 本の公理ではなく、論理式ごとに 1 本ずつ用意される無限個の公理の族です。「すべての部分集合について」と量化したいのに、一階の言語では集合を量化できないので、「論理式で定義できる部分集合について」に弱めるほかないからです。その代わり、与えられた論理式が帰納法図式の形をしているかは機械的に判定できます。この「公理集合が機械的に判定できる」という性質が第 3 節の主役になります。なお が有限個の公理では書けないことも知られています（Kaye の本を参照）。
デデキントの元来のペアノ公理（ペアノの公理（Axiom 4.1）［Techniques of Proof］）は二階のもので、帰納法を「 を含み で閉じたすべての部分集合は全体である」と述べます。この形なら、公理を満たす構造は同型を除き ただ 1 つです。しかし二階論理には、健全でありかつ完全な、有限的に検査できる証明体系が存在しません。一階に降りることで証明の機械的検査を手に入れ、代償として「 以外のモデル」（Example 5.4）を招き入れるわけです。
3. 体系に何を望むか
Section titled “3. 体系に何を望むか”3.1. メタな性質を定義する
Section titled “3.1. メタな性質を定義する”Definition 3.1（無矛盾性・完全性・健全性・帰納的公理化可能性）
を の理論（閉論理式の集合）とする。
- が無矛盾であるとは、 と が同時に成り立つような閉論理式 が存在しないことをいう。
- が完全であるとは、任意の閉論理式 について または が成り立つことをいう。
- が健全であるとは、 ならば （標準モデル で真）が成り立つことをいう。
- が帰納的公理化可能であるとは、与えられた論理式が の公理かどうかを判定するアルゴリズムが存在することをいう。
- が決定可能であるとは、与えられた閉論理式 について か否かを判定するアルゴリズムが存在することをいう。
- が**-無矛盾**であるとは、 でありながらすべての自然数 について となるような論理式 が存在しないことをいう。
「完全」という語は 2 つの意味で使われます。ここでの完全性は「どの文についても賛否のどちらかを言える」という理論の完全性です。ゲーデルの完全性定理（1929 年）の完全性は「すべてのモデルで真な文は証明できる」という証明体系の完全性で、別物です。第 7 節でこの 2 つを突き合わせます。
強さの序列は です。健全なら のとき なので、ある で となり、健全性から です。また矛盾する理論はすべての文を証明するので -無矛盾ではありません。逆向きはどちらも成り立ちません（Exercise 9.2）。
3.2. 完全な理論は決定できてしまう
Section titled “3.2. 完全な理論は決定できてしまう”Lemma 3.2（定理の枚挙）
が帰納的公理化可能ならば、 の定理をすべて（重複を許して）順に出力し続けるアルゴリズムが存在する。
Proof（Lemma 3.2）
の記号は可算個なので、記号列全体を「長さの短い順、同じ長さなら辞書式順」に機械的に並べられる。証明は記号列の有限列なので、同じ要領で証明の候補すべてを機械的に並べられる。
候補を 1 つずつ取り出し、それが Definition 2.1 の意味で証明かを検査する。検査には (i) 各行が公理かの判定と、(ii) 各行が先行する行から推論規則で得られるかの判定が要る。(i) は が帰納的公理化可能だから可能、(ii) は推論規則が有限個で、各規則の適用が記号列の形の照合にすぎないから可能である。合格した候補については、その最終行を出力する。
ならば の証明が実在し、それは有限の記号列なので有限時間でこの枚挙に現れ、 はいつか出力される。逆に出力されるのは合格した証明の最終行だけなので、 の定理に限られる。
Proposition 3.3（完全性から決定可能性へ）
が帰納的公理化可能かつ完全ならば、 は決定可能である。
Proof（Proposition 3.3）
まず が無矛盾な場合。閉論理式 に対し Lemma 3.2 の枚挙器を走らせ、出力に または が現れるまで待つ。完全性より少なくとも一方は定理なので待ち時間は有限である。無矛盾性より両方が定理になることはないから、先に現れたほうが答になる。 が先なら「」、 が先なら「」と出力すればよい。
が矛盾する場合は、 がすべての閉論理式を証明するので、入力によらず「」と答える手続きが決定手続きになる。いずれの場合にも決定アルゴリズムが存在する。
対偶が効きます。決定不可能な理論は、帰納的公理化可能なら完全ではありえません。 チャーチとチューリングは 1936 年に、 を含む無矛盾な理論はどれも決定不可能であることを示しました。 の公理集合は機械的に判定できるので、この結果と Proposition 3.3 だけで「 は完全でない」が出ます。ただしこの経路では、証明できない文が何であるかは分かりません。ゲーデルの議論は、その文を名指しで与えるところに価値があります。
3.3. 仮定を落とすとどうなるか
Section titled “3.3. 仮定を落とすとどうなるか”第一不完全性定理は「十分な算術を含む」「帰納的公理化可能」「無矛盾」の 3 つを仮定します。どれ 1 つ落としても定理は成り立ちません。
Example 3.4（掛け算を捨てると完全になる）
言語を に制限し、公理を (Q1)(Q2)(Q4)(Q5) とこの言語の論理式に対する帰納法図式にした理論をプレスブルガー算術といいます。プレスブルガーは 1929 年に、これが完全かつ決定可能であることを示しました。
たとえば「どの数も偶数か奇数か」を表す は についての帰納法で証明できます。準備として補題 を の帰納法で示します（ なら (Q4) から両辺とも 、 で成り立てば (Q5) から ）。 では と取れば (Q4) から で第 1 項が成り立ちます。 なら (Q5)(Q4) より なので、同じ で が第 2 項を満たします。 なら を新しい に取ると、(Q5) と補題から となり第 1 項を満たします。
完全になる理由の核心は、掛け算がないと定義できる集合が「最終的に周期的」なものに限られ、量化子除去ができる点にあります。裏を返せば、掛け算がないためゲーデル数化に必要な符号化（第 4 節）が行えません。この決定手続きは今日、整数線形算術を扱う SMT ソルバに実装されています。
Example 3.5（真の算術は完全だが公理化できない）
、すなわち標準モデルで真な閉論理式すべての集合は完全です（どの についても か が真だからです）。 をモデルに持つので無矛盾でもあります。
ではなぜこれで話が終わらないのか。 は帰納的公理化可能ではないからです。もしそうなら Proposition 3.3 により決定可能になり、 を含む理論の決定不可能性に反します。この「完全な公理系」は、何が公理かを機械的に確かめる手段がなく、証明の検査ができません。使える公理系ではないのです。
矛盾する理論は爆発律によりすべての文を証明するので完全です（Exercise 9.1）。こうして 3 つの仮定はいずれも外せないと分かります。
4. 算術が自分自身について語る
Section titled “4. 算術が自分自身について語る”4.1. ゲーデル数化
Section titled “4.1. ゲーデル数化”第一の鍵は、記号列としての論理式や証明に自然数の背番号を与え、「証明である」というメタな性質を、自然数についての性質に翻訳することです。
Definition 4.1（ゲーデル数）
の各記号 に相異なる正の整数 を割り当てる。記号列 に対し
（ は 番目の素数）と定め、これをゲーデル数という。論理式の有限列（証明）に対しても、各項のゲーデル数を同じ方法で束ねて符号を与える。素因数分解の一意性により は単射であり、 から を機械的に復元できる。数項 を の名前と呼ぶ。
たとえば , と決めておくと、 のゲーデル数は 、 のそれは です。数は巨大になりますが、有限であることと復元可能であることだけが問題なので効率は気にしません。
こうして自然数と論理式の間に機械的な辞書ができました。すると「 は の証明である」というメタな関係は、自然数の対についての関係になり、素因数分解・列の分解・公理判定・規則の照合だけで判定できるのでアルゴリズムで計算できます。あとはこの関係を の論理式で書ければよく、それを保証するのが次の黒箱です。
Definition 4.2（証明可能性述語と無矛盾性の文）
を帰納的公理化可能な理論とする。自然数の関係
はアルゴリズムで判定できる。(B1) によりこれを表現する論理式 を 1 つ固定し、
を証明可能性述語という。また を閉論理式 （ が (Q1) から否定を証明する偽な文）とし、
を の無矛盾性を表す文という。
は「 の証明は存在しない」と読める、自然数についての文です。ここで注意してほしいのは、 というメタなレベルの事実と、 という** の内部での主張**が別物だということです。前者から後者は出ます（証明が実在すればその符号 について が言えるからです）が、逆は一般に成り立ちません。この非対称性が第 6 節の核心になります。
4.2. 対角化補題
Section titled “4.2. 対角化補題”第二の鍵は、自分自身の名前について語る文を作ることです。
Lemma 4.3（対角化補題（不動点補題））
を のすべての公理を証明する の理論とする。自由変数がちょうど 一つである任意の論理式 に対し、閉論理式 が存在して
が成り立つ。
Proof（Lemma 4.3）
2 変数関数 を、 が自由変数 を持つ論理式 のゲーデル数であるときは 、それ以外のときは と定める。この関数は計算できる。実際、 を素因数分解して を復元し、 の各出現を記号列 （ が 個）に置き換え、再び符号化すればよく、どの段階も有限回の機械的操作である。
したがって (B1) の後半により、論理式 が存在して、すべての について
が成り立つ（ は の公理を証明するので、 で証明できることは でも証明できる）。ここで
と置き、、 とする。 は の自由変数に を代入したものだから、 の定義そのものにより である。
上の表現可能性の式に を代入すると を得る。これを の内部で使えば
となり、主張が示された。
この証明のどこにも神秘はありません。 は自分自身の名前を「含んで」いるのではなく、 の名前 を含み、 という代入の仕組みを通して自分の名前を計算する構造になっています。 に 自身の番号を食わせるという手つきは、濃度と無限 で見たカントールの対角線論法（実数全体は非可算（Theorem 6.3）［濃度と無限］）と同じで、名前もそこから来ています。
4.3. 真理は算術で書けない
Section titled “4.3. 真理は算術で書けない”対角化補題の威力を、まず不完全性定理より短い定理で見ておきます。
Theorem 4.4（タルスキの真理定義不可能性）
の論理式 （自由変数は のみ）で、すべての の閉論理式 について
を満たすものは存在しない。
Proof（Theorem 4.4）
そのような が存在したとする。 は の公理をすべて含む（ の公理は で真だから）ので、Lemma 4.3 を に適用できる。すると閉論理式 が存在して
となる。 の公理はすべて で真であり、推論規則は真理を保つので、その定理は で真である。したがって である。一方、 についての仮定を に適用すると である。2 つを合わせると となり、矛盾する。
この は「私は真ではない」と述べる文、すなわち嘘つきのパラドックスの算術版です。ここから見通しが立ちます。証明可能性は算術の論理式 で書けるのに、真理は算術の論理式では書けない。 もし の定理が の真な文とちょうど一致するなら が真理述語になってしまい、Theorem 4.4 に反します。だから一致しません。証明できる文の集合は、真な文の集合より狭いのです。
flowchart TD A["論理式・証明<br/>（記号列）"] -->|ゲーデル数化| B["自然数"] B --> C["「y は x の証明である」<br/>という判定できる関係"] C -->|表現可能性 B1| D["論理式 Pf(y, x)"] D --> E["Prov(x) ≡ ∃y Pf(y, x)"] E --> F["対角化補題"] F --> G["G ↔ ¬Prov(G の名前)<br/>「私は証明できない」"] G --> H["第一不完全性定理"] H --> I["この証明自体を形式化<br/>（導出可能性条件）"] I --> J["第二不完全性定理<br/>T が Con(T) を証明できない"]
5. 第一不完全性定理
Section titled “5. 第一不完全性定理”Theorem 5.1（第一不完全性定理（ゲーデル、1931 年））
の理論 が次の 3 条件を満たすとする。
- (i) は のすべての公理を証明する。
- (ii) は帰納的公理化可能である。
- (iii) は無矛盾である。
Definition 4.2 の証明可能性述語 に対し、Lemma 4.3 を に適用して得られる閉論理式を とする。すなわち である。このとき次が成り立つ。
- (a) 。
- (b) さらに が -無矛盾ならば 。
とくに (i)(ii) と -無矛盾性のもとで、 は完全ではない。
Proof（Theorem 5.1）
(a) と仮定する。すると の証明が実際に存在するので、その符号を とすれば である。 は (B1) の意味で を表現するから であり、存在汎化により
一方 の取り方から であり、仮定 と三段論法により を得る。これで は とその否定の両方を証明したことになり、(iii) に反する。よって である。
(b) と仮定する。 の取り方から なので
ところが (a) より だから、どの自然数 も の証明の符号ではない。つまりすべての について であり、(B1) の関係についての条項（成り立たない場合）によりすべての について
この 2 つは、 に対して -無矛盾性の定義が禁じている状況そのものである。よって は -無矛盾ではなく、対偶により -無矛盾なら である。
(a) の証明で使ったのは無矛盾性だけです。これは第 6 節でもう一度使います。では、証明も反証もできない は、結局のところ真なのでしょうか。
Corollary 5.2（G は真である）
が (i)(ii) を満たし、かつ健全であるとする。このとき は で真であり、しかも である。
Proof（Corollary 5.2）
健全性から は無矛盾である（ かつ なら で と が同時に真になってしまう）。よって Theorem 5.1(a) が使えて である。すると の証明は 1 つも存在しないので、どの自然数 も を満たさない。 は を表現しており、標準モデルではこの表現は実際の関係と一致するので、、すなわち である。 とふたたび健全性から、この同値式も で真である。したがって を得る。
これが「真であるが証明できない命題」の正体です。 は「私は では証明できない」と述べており、実際に証明できない。だから の言っていることは正しい。自己言及の含みを取り除けば、 は「ある種の巨大な有限探索が決して当たりを引かない」という、ごく普通の算術の主張です。
Remark 5.3（ロッサーによる改良）
Theorem 5.1(b) は -無矛盾性という強い仮定を使っていました。ロッサーは 1936 年に、 の代わりに次の不動点 を取れば仮定 (iii) だけで済むことを示しました。
は「私の証明があるなら、それ以下の符号を持つ私の否定の証明がある」と述べています（ は から計算できるので、この形の不動点も Lemma 4.3 の議論で作れます）。骨子はこうです。 なら符号 の証明があるので が出ます。一方 (iii) より なので、 から までの各 について です。 は を証明するので、有界量化子を有限個の場合に展開して矛盾が出ます。 の場合も対称的です。
Example 5.4（G が偽になるモデル）
が無矛盾だとします。Theorem 5.1(a) より なので、 は無矛盾です（矛盾するなら背理法で となってしまいます）。ゲーデルの完全性定理により無矛盾な理論はモデルを持つので、 のモデル を取りましょう。
では が成り立つので となる元 が存在します。ところが各自然数 については が成り立つので（Theorem 5.1(b) の証明で見たとおりです）、 でも です。つまり はどの数項の値とも異なる、すべての自然数より大きい元、いわば「無限大の自然数」です。 は と同型ではありません。これを非標準モデルといいます。
の住人にとって は立派な自然数であり、 の証明の符号です。ただしその「証明」は、外から見れば無限に長い記号列で、私たちが証明と呼ぶものではありません。数とは何かという問いが、ここでもう一度立ち上がってきます（数とは何か？。実数の側でこの種の「無限大の元」を締め出しているのは アルキメデスの原理（Proposition 5.4）［What Is a Number? From the Naturals to the Reals, and Why 1 = 0.999… Is True］ でした）。
6. 第二不完全性定理
Section titled “6. 第二不完全性定理”Corollary 5.2 で使った推論は「 が無矛盾なら は証明できない、ゆえに は真」というごく初等的なものでした。初等的ということは、 の内部で再現できるかもしれないということです。実際それができ、結論として は自分の無矛盾性を証明できなくなります。この形式化を支えるのが、ヒルベルトとベルナイス、そしてレープが整理した次の 3 条件です。
Theorem 6.1（第二不完全性定理（ゲーデル、1931 年））
を のすべての公理を証明する帰納的公理化可能な理論とし、 は無矛盾であるとする。さらに が (D1)(D2)(D3) を満たすように構成されているとする。このとき
である。すなわち は自分自身の無矛盾性を証明できない。
Proof（Theorem 6.1）
を Theorem 5.1 の文とする。目標は を示すことで、そこから結論はすぐ出る。以下 で を略記する。
第 1 段： の取り方から である。(D1) をこの定理に適用すると 、これに (D2) を使うと
第 2 段：(D3) を に適用すると 。
第 3 段：任意の閉論理式 について は述語論理の定理だから、(D1) と (D2) を 2 回使うと
を得る。ここで と取り、第 2 段と第 1 段を順に代入すると となる。
第 4 段：対偶を取ると 、すなわち Definition 4.2 の記法で である。 の取り方から なので、合わせて
第 5 段：もし ならば、三段論法により となる。ところが は無矛盾なので Theorem 5.1(a) により であり、矛盾する。したがって である。
第 4 段で得た は、それ自体が味わい深い式です。 という一見奇怪な自己言及の文が、「 は無矛盾である」という自然な主張と の内部で結びついています。実際、逆向きの も成り立つので、 と は 上で同値です。
Remark 6.2（レープの定理と、証明可能性の作法）
同じ道具立てからレープの定理（1955 年）が出ます。 ならば である、というものです。「証明できるなら本当だ」と が言えるのは、そもそも が証明できる場合に限るわけで、 と取れば Theorem 6.1 が再現されます。
なお第二不完全性定理には、第一定理にはない微妙さがあります。主張が「」という文の書き方に依存するのです。フェファーマンが指摘したように、公理集合を別の（外延的には同じ集合を定める）論理式で書いたり、ロッサー流の証明可能性述語を使ったりすると、「無矛盾性を表す文」でありながら で証明できてしまうものが作れます。(D1)(D2)(D3) を満たす自然な構成に限る、という条件が本質的です。
Remark 6.3（ゲンツェンの無矛盾性証明とヒルベルトの計画）
の無矛盾性が証明できないわけではありません。ゲンツェンは 1936 年に、順序数 までの超限帰納法を初等的手段に付け加えれば の無矛盾性が証明できることを示しました。Theorem 6.1 と矛盾しないのは、 までの超限帰納法が では証明できない原理だからです。ここに「体系の強さ」を測る目盛りが生まれ、証明論順序数の研究につながりました。
同じことは集合論にも当てはまり、 が無矛盾なら です。数学の標準的な基礎の無矛盾性を、その基礎の内部で確かめることはできません。ヒルベルトの計画は当初の形では成立しませんが、「どの追加原理を認めればどの体系の無矛盾性が出るか」を測る相対的な計画としては、証明論の形で今も生きています。
7. 「真だが証明できない」の読み方
Section titled “7. 「真だが証明できない」の読み方”7.1. 完全性定理と不完全性定理は矛盾しない
Section titled “7.1. 完全性定理と不完全性定理は矛盾しない”ゲーデルは 1929 年の学位論文で完全性定理を証明しました。一階述語論理について、 のすべてのモデルで真な文は から証明できる（ ならば ）という定理です。一方 1931 年の不完全性定理は、 かつ となる の存在を主張します。この 2 つを並べると
が従います。つまり が真になる のモデルと偽になる のモデルの両方が存在するということで、Example 5.4 で作った非標準モデルは後者の実例でした。 が「真」だというのは、標準モデル を特別扱いしたうえでの言明です。証明できるのは「すべてのモデルで真な文」だけですから、 が証明できないのは当然のことでした。
すると次の問いが残ります。「標準モデル 」とは何なのか。一階の算術の内側からは、 を他のモデルと区別する手段がありません。 を素朴に把握できるものとして認めるかどうかは、数学の中の問いというより数学の哲学の問いになります。
7.2. よくある誤解
Section titled “7.2. よくある誤解”| よく見る言い方 | 正確には |
|---|---|
| 証明も反証もできない問題があるのだから、数学は不完全だ | 特定の理論 に対して独立な文があるだけです。 に移れば は証明できます。ただし にも新しい独立命題が現れます |
| 不完全性定理は数学が矛盾していることを示した | 逆です。 の無矛盾性を仮定したうえでの結論であり、矛盾する理論はむしろ完全です |
| どんな公理系も不完全である | 「 を含む」「帰納的公理化可能」「無矛盾」の 3 つが必要です。Example 3.4 と Example 3.5 が反例になります |
| が真だと人間には分かるのだから、心は機械を超える | 人間に分かるのは「 が無矛盾ならば は真」という条件付きの主張です。Theorem 6.1 が示すのは、その条件を体系の内部では正当化できないということです |
最後の行はルーカスとペンローズの議論に関わります。人間の数学的能力が形式体系を超える証拠だという主張ですが、標準的な反論は 2 つです。 の真理を「知る」のは の無矛盾性を前提にしたときだけで、その前提を無条件には正当化できないこと。そして、人間の推論がアルゴリズム で記述されるとしても、私たち自身が を特定し が無矛盾だと知ることはできないこと。私はこの反論のほうが説得的だと思いますが、決着した論争ではありません。
7.3. 体系を強くしても追いつけない
Section titled “7.3. 体系を強くしても追いつけない”とし、 と定めます。 が健全なら は で真なので も健全で、帰納的に各 が健全かつ無矛盾になります。各段階で 1 つ前の体系の無矛盾性は証明できるようになりますが、Theorem 6.1 が各 にそのまま適用されるので、 は自分の無矛盾性を証明できません。この階層は超限順序数に沿って伸ばすことができ、チューリングの学位論文（1939 年）とフェファーマンの研究（1962 年）が扱っています。不完全性は、公理を機械的に足していく限り、どこまで行っても解消されません。
8. リーマン予想は証明不可能か
Section titled “8. リーマン予想は証明不可能か”8.1. 論理式の複雑さで見分ける
Section titled “8.1. 論理式の複雑さで見分ける”不完全性定理は「証明できない文が存在する」と言うだけで、私たちが関心を持つ具体的な予想がそうだとは言いません。では、未解決問題が独立である可能性はどれくらいあるのでしょうか。ここで論理式の形が効いてきます。
すべての量化子が や の形（有界量化子）である論理式を 論理式といいます。 閉論理式の真偽は有限回の計算で確定します。 論理式 を用いて の形に書ける文を 文、 の形に書ける文を 文といいます。
Proposition 8.1（Π₁ 文が反証できないなら、それは真である）
を のすべての公理を証明する の理論とし、 を 閉論理式（ は 論理式）とする。このとき ならば である。
Proof（Proposition 8.1）
対偶を示す。 とすると、ある自然数 について である。 は有界量化子しか含まない閉論理式、すなわち真な 文だから、(B2) により である。 は の公理をすべて証明するので 、存在汎化により 、すなわち を得る。
文が偽ならば、その反例は必ず有限の計算で確認でき、 程度の弱い理論でも反証できるということです。したがって 文 が「 から独立」と示されたなら、後半の「反証できない」から Proposition 8.1 により は真だと分かります。 文の独立性証明は、同時にその真理の証明でもあるのです。 ただし独立性を示す議論は の外側のメタ理論（通常は など）で行われるので、「真である」という結論もそのメタ理論の中での結論です。
8.2. リーマン予想の場合
Section titled “8.2. リーマン予想の場合”Example 8.2（リーマン予想は Π₁ 文と同値）
リーマン予想（ 関数の非自明な零点はすべて実部 を持つ）は、一見すると複素解析の主張で算術の階層とは無縁に見えます。ところがラガリアスは 2002 年に、次の初等的な言明と同値であることを示しました。 を約数の総和、 を調和数とするとき、
が成り立つことと、リーマン予想は同値です（等号が成り立つのは のときだけです）。
では 、 なので右辺は となり、両辺とも で等号です。 では 、 で、、 ですから右辺は
となり、 で不等式が成り立っています。
この不等式の両辺は から有限回の計算で任意の精度に評価できるので、各 に対する成否は有限の計算で判定できます。したがってリーマン予想は の形の 文と同値です。さらに、マチャセビッチによるヒルベルトの第 10 問題の解決から、どんな 文も「ある整数係数多項式方程式が自然数解を持たない」という形に書き換えられることが知られており、リーマン予想も具体的なディオファントス方程式の非可解性として書けます。
ここから Proposition 8.1 の含意が効いてきます。もし将来「リーマン予想は から独立である」と証明されたら、その瞬間にリーマン予想は真だと分かります。「独立だから真偽が定まらない」という結末は、 文についてはあり得ません。あり得るのは「真だが では証明が届かない、より強い体系が要る」という結末だけです。同じことはゴールドバッハ予想やフェルマー予想にも当てはまります。
現時点で、リーマン予想が から独立かどうかは分かっていません。多くの数学者は独立ではないだろうと考えていますが、それは経験に基づく見通しであって定理ではありません。私も同意見ですが、根拠は「数論の主要定理はこれまで通常の数学の範囲で証明されてきた」という帰納的なものにすぎない、とは言っておきます。
8.3. 実際に独立と分かっている命題
Section titled “8.3. 実際に独立と分かっている命題”Example 8.3（グッドスタインの定理）
自然数を遺伝的 進表記で書くとは、 進表記の指数もまた 進で書き、その指数も…と再帰的に書き下すことです。たとえば が遺伝的 2 進表記です。グッドスタイン数列は、 を遺伝的 2 進で書いて底 をすべて に置き換えてから を引いたものを とし、 を遺伝的 3 進で書いて底を に置き換えて を引いたものを とし、と続けて作ります。グッドスタインの定理（1944 年）は、どの から始めてもこの数列が有限回で に到達すると主張します。
で最後まで計算します。 の底を にすると 、 を引いて 。 の底を にすると 、 を引いて 。 は底 の表記では単に で底が現れないので、置き換えても 、 を引いて 。同様に 、。数列は です。
なぜ必ず に届くのか。遺伝的表記の底を記号 に置き換えると順序数が得られ、上の例では と狭義単調減少します。順序数の減少列は無限には続かないので、数列は有限で終わります。この議論には 未満の順序数についての超限帰納法が要り、カービーとパリスは 1982 年にこの定理が から独立であることを示しました（L. Kirby and J. Paris, Bulletin of the London Mathematical Society 14 (1982), 285–293）。数列は途中で猛烈に増大し、 から始めると に届くまでに 段階かかります。これは 文なので Proposition 8.1 は使えませんが、独立でありかつ真であることが、より強い体系の中で証明されています。
Remark 8.4（連続体仮説は事情が違う）
集合論で最も有名な独立命題は連続体仮説（ と の間に濃度がない）です。ゲーデルは 1938 年に構成可能宇宙 を使って の無矛盾性を、コーエンは 1963 年に強制法を使って の無矛盾性を示しました（濃度と無限、連続体濃度（Definition 6.5）［濃度と無限］）。
ただし連続体仮説は算術の文ではないので Proposition 8.1 は適用できません。 文なら「反例があるなら見つかる」という有限性が支えになりますが、連続体仮説にはその支えがなく、「真偽が客観的に定まっているのか」という論争が付きまといます。集合論の実在論を取るか取らないかで、独立性の受け止め方が変わるのです。
チャイティンによる別種の不完全性も知られています。各理論 に定数 が存在し、 はどんな文字列についても「その文字列のコルモゴロフ複雑性は より大きい」を証明できません。ほとんどすべての文字列についてそれは真なのに、です。不完全性は自己言及という仕掛けだけの現象ではありません。
矛盾する理論は完全であることを示せ。これにより Theorem 5.1 から無矛盾性の仮定を落とせないことを確認せよ。
Solution
が矛盾するとは、ある閉論理式 について かつ となることである。任意の閉論理式 を取る。 は述語論理の定理（爆発律）なので、 と三段論法から 、さらに と三段論法から を得る。よって はすべての閉論理式を証明するので、完全である。
したがって矛盾する理論は (i)(ii) を満たしても完全になりうる。Theorem 5.1 の仮定 (iii) は外せない。
(1) -無矛盾な理論は無矛盾であることを示せ。(2) が無矛盾であるとき、 は無矛盾だが -無矛盾ではないことを示せ。
Solution
(1) 対偶を示す。 が矛盾するなら Exercise 9.1 によりすべての閉論理式を証明する。そこで論理式 を何でも 1 つ取れば、 であり、同時にすべての について である。これは -無矛盾性の定義が禁じる状況なので、 は -無矛盾ではない。
(2) 無矛盾性：もし が矛盾すれば、演繹定理により 、すなわち となる。これは Theorem 6.1 に反する。よって は無矛盾である。
-無矛盾でないこと： と置く。 は 、すなわち を公理として持つ。一方 は無矛盾なので の証明は存在せず、どの自然数 も を満たさない。(B1) によりすべての について 、したがって である。これで -無矛盾性の定義が禁じる状況が実現しているので、 は -無矛盾ではない。
この は「自分は矛盾している」と主張する無矛盾な理論である。そのモデルには、 の証明の符号を演じる非標準の元が含まれる（Example 5.4）。
ゴールドバッハ予想 を「 以上のすべての偶数は 2 つの素数の和として表せる」とする。(1) が 文として書けることを確かめよ。(2) 将来 が証明されたとき、 の真偽について何が言えるか。(3) 双子素数予想に同じ議論が使えない理由を述べよ。
Solution
(1) 「 は素数」は と書け、量化子が で有界なので である（ は と書ける）。そこで
と置く。 の探索範囲が で有界であることが本質的で、これにより は 論理式になる。 は と書けるので 文である。
(2) Proposition 8.1 を 、 に適用する。 は の公理をすべて証明するので仮定を満たす。よって から が従い、ゴールドバッハ予想は真である。とくに「 から独立」と示されれば、それは同時に「真であるが では証明できない」という結論になる。真偽が宙に浮くことはない。
(3) 双子素数予想は と書ける。内側の には上界がなく有界量化子にできないので、この文は であって ではない。Proposition 8.1 の証明では「 が偽なら有限の計算で確認できる反例がある」ことを使ったが、双子素数予想が偽である場合に生じるのは「ある より先に双子素数が存在しない」という無限個の条件であり、有限回の計算では確認できない。したがって (B2) が使えず、議論は成立しない。
- 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 — 非標準モデルと の性質（有限公理化不可能性を含む）。
- J. C. Lagarias, “An Elementary Problem Equivalent to the Riemann Hypothesis”, American Mathematical Monthly 109 (2002), 534–543. arXiv:math/0008177
Report an error in this article ・Operated by: Mugen Giken LLC ・Pricing ・Terms ・Legal notice
© 2026 夢現技研合同会社 ・Feeding the text to an LLM is welcome. Code samples are MIT licensed.