ゲーデル不完全性定理

概要

ゲーデル不完全性定理は、1931年にオーストリア・ハンガリー出身の論理学者クルト・ゲーデル（1906-1978）が発表した、数理論理学の根本定理である。論文「『プリンキピア・マテマティカ』およびそれに関連する体系における形式的に決定不能な命題について」に示された。

第一不完全性定理：算術を含む無矛盾な形式体系には、真でありながら証明も反証もできない命題が存在する。第二不完全性定理：そのような体系は、自身の無矛盾性を自身の内部では証明できない。

20世紀初頭、数学の基礎論は危機にあった。ラッセルのパラドックス（1901）、ブラウワーの直観主義、ヒルベルトの形式主義——数学を無矛盾な公理系の上に確立するプログラムが競合していた。

ヒルベルトは、有限的手段のみで無矛盾性を証明することで、数学を究極的に基礎づけようとした（ヒルベルト・プログラム、1920年代）。ゲーデルは1930年までこのプログラムに好意的だったが、1931年の論文で、算術を含む体系では原理的に不可能であると証明した。

核心的技法はゲーデル数化——記号列に自然数を一意に対応させる符号化——により、算術内で算術自身を扱う自己言及命題を構築したことだった。「この命題は証明できない」に相当する命題は、真であれば証明不能、証明可能であれば偽——いずれにせよ体系は不完全か矛盾することが示される。

第二定理はさらに深く、体系が自分自身の無矛盾性を証明できないことを示した。数学を外側からの信頼なしに基礎づける試みは、原理的に閉じないと判明した。

ゲーデル定理は、数学の限界を数学自身で証明した稀有な成果である。以後、数学基礎論、計算機科学、哲学に深い影響を与えた。

1936年、チューリングは計算可能性の観点から同等の結果（停止問題の決定不能性）を示した。ゲーデル・チャーチ・チューリングの仕事は、形式システムで機械的に決定できないものの存在を確立し、計算機科学の理論的基礎となった。

哲学的には、心・物理法則・人工知能の可能性をめぐる論争に引用される。ペンローズは『皇帝の新しい心』（1989）で、人間の数学的理解は形式体系を超えると論じた。反論も多く、現代も論争は続く。