ゲーデルの第一不完全性定理｜記号論理学が明らかにした数学の限界
ゲーデルの第一不完全性定理は、1931年にクルト・ゲーデルが証明した、数学史上最も重要な結果の一つです。十分に強い形式的体系は、自分自身の中で証明も反証もできない命題を必ず含むことを示しました。
第一不完全性定理の主張
ゲーデルの第一不完全性定理は次のように述べられます。
ペアノ算術を含む無矛盾な帰納的公理化可能な理論 T には、T で証明も反証もできない文が存在する。
言い換えれば、十分に強い理論は不完全です。すべての算術的真理を証明できるわけではありません。
「十分に強い」：自然数の加法・乗法を扱える。「無矛盾」：矛盾がない。「帰納的公理化」：公理が機械的に判定できる。
T で証明できず、かつ T で反証もできない文 G が存在する。
ゲーデル文
定理の証明では、特殊な文 G を構成します。この G は「G は T で証明不可能である」という内容を算術的に表現したものです。
G が T で証明可能だと仮定すると、G は「自分は証明不可能」と言っているので、G は偽になります。しかし T が健全なら、証明可能な文は真のはずです。矛盾です。
よって G は T で証明不可能です。すると G は真です（G は「証明不可能」と言っていて、実際にそうだから）。しかし G は証明できません。
G は「証明不可能」と主張 → G は偽 → 健全性に矛盾
G は証明不可能かつ真。T は不完全。
自己言及のトリック
ゲーデルの証明の核心は、自己言及を算術の中で実現したことです。
「この文は証明できない」という文を直接書くことはできません。しかし、ゲーデル数化を使えば、証明可能性を算術的な述語として表現できます。そして対角化論法により、「自分自身のゲーデル数について、証明不可能性を主張する文」を構成できます。
この技法は、カントールの対角線論法やチューリングの停止問題と深く関連しています。
証明の概略
証明の大まかな流れを示します。
まず、「n が文 φ の証明のゲーデル数である」という関係 Proof(n, φ) を算術で定義します。これは帰納的な関係なので、算術で表現可能です。
次に、「φ は証明可能である」を ∃n Proof(n, φ) と表します。
対角化補題を使って、G ↔ ¬∃n Proof(n, ⌜G⌝) となる文 G を構成します。ここで ⌜G⌝ は G のゲーデル数です。
証明可能性を算術で表現
対角化補題でゲーデル文 G を構成
G が証明可能なら矛盾
G は証明不可能（かつ真）
不完全性の帰結
第一不完全性定理は深い帰結を持ちます。
数学は「完全に機械化」できません。すべての真理を導くアルゴリズムは存在しません。
どんなに公理を追加しても、不完全性は解消しません。G を公理に加えても、新しい体系にはまた別のゲーデル文が存在します。
ヒルベルトは数学を完全かつ無矛盾な形式的体系として完成させることを目指していた。不完全性定理はこの計画が不可能であることを示した。
不完全性は「欠陥」ではなく、数学の本質的な性質。形式的体系の限界を知ることで、数学をより深く理解できる。
真理と証明可能性
ゲーデル文 G は真ですが証明不可能です。これは「真理」と「証明可能性」が一致しないことを示しています。
真理は意味論的な概念、証明可能性は構文論的な概念です。述語論理全体では完全性定理により一致しますが、特定の理論の中では一致しません。
次回は、第二不完全性定理について学びます。
