ゲーデルの不完全性定理：「真だが証明できない」とは何のことか

0. この記事の要点

• 形式体系とは、何が文であり何が証明であるかを、意味を一切参照せず記号の形だけで決めた枠組みです。ペアノ算術 $\mathrm{PA}$ はその代表で、初等整数論の議論の大部分をその内部で再現できます。
• 第一不完全性定理：ごく弱い算術を含み、公理をアルゴリズムで判定でき、無矛盾な理論には、証明も反証もできない閉論理式が存在します。
• 第二不完全性定理：さらにその理論は、自分自身の無矛盾性を表す文 $\mathrm{Con}_T$ を証明できません。「体系の無矛盾性を体系の内側で確かめる」というヒルベルトの計画は、この素朴な形では実現しません。
• 仕掛けは 2 つです。算術が自分自身について語れること（ゲーデル数化）と、自分の名前を含む文を作れること（対角化補題）。「証明可能性」は算術の論理式で書けるのに「真理」は書けない——この非対称性が不完全性の正体です。
• 「真だが証明できない」の「真」は標準モデル $\mathbb{N}$ における真です。$T$ のすべてのモデルで真という意味ではないので、ゲーデルの完全性定理と矛盾しません。
• リーマン予想は $\Pi_1$ 文と同値です。したがって「$\mathrm{PA}$ から独立」と示されたなら、その時点でリーマン予想は真だと分かります。独立性が逃げ道になる余地は、この形の予想については驚くほど狭いのです。

1. 動機：ヒルベルトの計画とその挫折

19 世紀の終わりに、数学の足元は二度揺れました。一度目は非ユークリッド幾何の発見です。2000 年にわたって「疑いようのない真理」とされてきた平行線公準が、取り替え可能な仮定にすぎないと分かりました。二度目はカントールの集合論から出たパラドックスです。「自分自身を要素として含まない集合すべての集合」を考えると矛盾します（ラッセル、1901 年。素朴集合論の限界（注意 6.4）［数学の国語］）。無限を自由に扱う議論が安全なのか、誰にも保証できなくなりました。

ヒルベルトの解決策は大胆で明快でした。数学の議論を、意味を持たない記号の操作に還元してしまう。公理と推論規則を書き下せば、証明とは「規則に従って組み上げられた記号列」にすぎません。すると「この体系は $0=1$ を導くか」という問いは、記号列についての有限的で具体的な問いになります。これに、疑う余地のない初等的手段（有限の立場）だけで「導かない」と答えられれば、無限を扱う数学の安全性が確保できる——これがヒルベルトの計画です。1928 年の国際数学者会議で、彼は形式体系について 3 つの問いを立てました。

1. 完全性：真な命題はすべて証明できるか。
2. 無矛盾性：矛盾しないことを証明できるか。
3. 決定可能性：命題が証明できるかどうかを判定する機械的手続きはあるか。

1930 年 9 月、ケーニヒスベルクでの講演をヒルベルトはこう締めくくりました。「われわれは知らねばならない、われわれは知るであろう」。ところが同じ会合の席上で、25 歳のクルト・ゲーデルが問い 1 の答えが「否」であることを控えめに報告していました。翌 1931 年の論文で問い 1 と 2 が、1936 年のチャーチとチューリングの仕事で問い 3 が、いずれも否定的に解決されます。

以下では「形式体系」「無矛盾」「完全」を正確に定義し、道具立てを組み立てたうえで、2 つの定理を主張として完全に述べます。証明は、深い準備を要する事実だけを黒箱として切り出し、残りは省略せずに書きます。前提として、論理記号と量化子の扱いは 数学の国語 - 集合と論理（全称記号と存在記号（定義 5.2）［数学の国語］）、背理法と数学的帰納法は 証明の技術（背理法の正当性（命題 6.2）［証明の技術］、数学的帰納法の原理（定理 3.2）［証明の技術］）、カントールの対角線論法は 濃度と無限 を使います。

ここから先は Pro プランの内容です。

この章の続き（定義・定理・証明・例・演習）をすべて読むには Pro プランにご登録ください。無料の章は最後まで読めます。

プランを見る ログイン