ゲーデルの第二不完全性定理｜無矛盾性は証明できない

ゲーデルの第二不完全性定理は、第一不完全性定理をさらに深化させた結果です。十分に強い理論は、自分自身の無矛盾性を証明できないことを示しました。この定理は数学基礎論に決定的な影響を与えました。

第二不完全性定理の主張

ゲーデルの第二不完全性定理は次のように述べられます。

ペアノ算術を含む無矛盾な帰納的公理化可能な理論 T は、T 自身の無矛盾性を T の中で証明できない。

ここで「T の無矛盾性」とは、「T から矛盾（たとえば 0 = 1）が証明できない」という主張を算術的に表現した文 Con(T) のことです。

定理の意味

T が無矛盾であっても、そのことを T 自身の中では証明できない。

Con(T) の形式化

Con(T) は「0 = 1 の証明が存在しない」、つまり ¬∃n Proof(n, ⌜0=1⌝) と表せる。

第二不完全性定理は、第一不完全性定理から導かれます。

ゲーデル文 G は「G は証明不可能」を主張します。第一不完全性定理の証明で、「T が無矛盾ならば G は証明不可能」が示されました。これを形式化すると、T 自身の中で Con(T) → ¬Prov(G)、つまり Con(T) → G が証明できます。

もし T で Con(T) が証明できるなら、モーダスポネンスで G が証明できます。しかし G は証明不可能です。よって Con(T) は T で証明不可能です。

第一不完全性定理より T ⊢ Con(T) → G

もし T ⊢ Con(T) なら T ⊢ G

しかし G は証明不可能

よって T ⊬ Con(T)

第二不完全性定理は、ヒルベルトのプログラムに決定的な打撃を与えました。

ヒルベルトは、数学の無矛盾性を有限の手段で証明することを目指していました。具体的には、強い理論（たとえば集合論）の無矛盾性を、より弱い理論（有限数学）で証明しようとしました。

しかし第二不完全性定理により、十分に強い理論の無矛盾性は、その理論自身（または弱い理論）では証明できないことがわかりました。

ヒルベルトの目標

数学の無矛盾性を「安全な」有限の方法で証明する。数学の基礎を確立する。

ゲーデルの結果

無矛盾性の証明には、元の理論より強い手段が必要。基礎は自己完結しない。

第二不完全性定理は、無矛盾性証明が不可能だとは言っていません。T より強い理論 S で T の無矛盾性を証明することは可能です。

実際、ゲンツェンは超限帰納法を使ってペアノ算術の無矛盾性を証明しました。ただし、この証明自体はペアノ算術の中では行えません。

ゲンツェンの無矛盾性証明

ε₀ までの超限帰納法を使う。ペアノ算術では証明できない原理を用いる。

相対的無矛盾性

「ZFC が無矛盾なら ZFC + 連続体仮説も無矛盾」のような結果は証明できる。

第二不完全性定理は、数学の哲学に深い問いを投げかけます。

数学の無矛盾性を「信じる」根拠は何でしょうか。ペアノ算術が無矛盾であることは、直観的には確かに思えますが、それを形式的に保証することはできません。

また、より強い理論を使えば無矛盾性を証明できますが、その強い理論の無矛盾性はどう保証するのか、という無限後退の問題が生じます。

第二不完全性定理にはいくつかの技術的な注意点があります。

Con(T) の「標準的な」形式化について成り立ちます。非標準的な形式化では、自己の無矛盾性を「証明」できる場合もあります（ただし意味のある主張ではなくなります）。

また、T が無矛盾でなければ定理は適用されません。矛盾した理論では Con(T) も（その否定も）証明できてしまいます。

次回は、決定可能性と決定不能性について学びます。