ゲーデルの不完全性定理
ゲーデルの不完全性定理は、ゲーデルが1931年の論文で証明した次の内容である。
『数学原理(プリンキピア・マセマティカ)』の体系や公理的集合論の中には、証明も反証もできない自然数論の命題が存在する。
また、これらの体系に公理を追加しても公理が有限個であれば、前述の命題の存在を解消できない。
より正確には、不完全性定理は第一と第二に分かれている。
第一不完全性定理 ― "初等的な自然数論"を含むω無矛盾な公理的理論 T {\displaystyle T} は不完全である,つまりそこで証明も反証もされない命題(決定不能命題(undecidable proposition),あるいは独立命題)が存在する。
第二不完全性定理 ― "初等的な自然数論"を含む理論 T {\displaystyle T} が無矛盾ならば, T {\displaystyle T} の無矛盾性を表す命題 Con( T {\displaystyle T} ) がその体系で証明できない。
なお「有限の立場」とは、数学の形式主義における「記号の有限的な操作のみから構成される」立場を指す。
さて、ゲーデル文Gが証明可能であれば、Σ1完全性により命題「Gは証明できる」もまた証明可能である。一方Gは命題「Gは証明できない」と同値であることが証明可能であるので、両者から矛盾が導かれる。つまり
「Gは証明できる」ならば「矛盾が証明できる」 ... (A)
したがって、対偶を取れば
「矛盾が証明できない」ならば「Gは証明できない」 ... (B)
となる。
また、¬Gが証明可能であれば、Gの性質から命題「Gは証明できる」も証明可能である。この際、もしGそのものが証明不能だとすると、ω矛盾ということになる。ω無矛盾であればGも証明可能である。しかしGが証明可能であれば「Gは証明できない」も証明可能であるので、やはり両者から矛盾が導かれる。したがってω無矛盾であれば¬Gも証明できないのである。よってω無矛盾であれば、Gも¬Gも証明できない(第一不完全性定理)。
なお、証明可能性の代わりに真理性を用いれば、パラドックスが導かれることから、帰納的公理化された自然数論(以下、自然数論)における真理性は自然数論の中では算術的述語として表現できない、と示される(タルスキの定理)。
不完全性定理を踏まえても、数学の形式体系の公理は真であり無矛盾であるし、数学の完全性も成立し続けている。しかし“不完全性定理は数学や理論の「不完全性」を証明した”といった誤解や、“数学には「不完全」な部分があると証明済みであり、数学以外の分野に「不完全」な部分があってもおかしくない”といった誤解が一般社会・哲学・宗教・神学等によって広まり、誤用されている。
数学の「無矛盾性」を証明することを目指したヒルベルト・プログラムに関して「不完全性定理がヒルベルトのプログラムを破壊した」という類の哲学的発言はよくあるが、これは実際の不完全性定理やゲーデルの見解とは異なる、とフランセーン達は解説している。正確には、ゲーデルはヒルベルトと同様の見解を持っており、彼が不完全性定理を証明して示したのは、ヒルベルトの目的(「無矛盾性証明」)を実現するためには手段(ヒルベルト・プログラム)を拡張する必要がある、ということだった。これについて日本数学会編集の『岩波数学辞典』では「彼〔ゲーデル〕の結果はヒルベルトの企図を直接否定するものではなく,実際この定理の発見後に無矛盾性証明のための様々な方法論が開発されている」と記されている。