不完全性定理とは (フカンゼンセイテイリとは) [単語記事]

不完全性定理とは、ゲーデルが1931年に発表した定理である。

概要

この定理には

第一「再帰的で(ω)無矛盾な自然数論を充分に表現できる形式系は完全ではない.」

第二「再帰的で無矛盾な自然数論を充分に表現できる形式系は自分自身の無矛盾性を証明できない.」

の二つがある。

(以下、理論=形式系、仮定=公理とする。)

要約すると

一つ目は、どんな数学理論も正否の判定ができない命題を(その理論内で記述できる命題として)もつということ。

この例として、ZFに対する選択公理、ZFC（ZF＋選択公理）に対する連続体仮説などが存在する。

二つ目は、数学理論の無矛盾性はその理論又はそれより強くない(より多くの仮定を含まない)理論からは示せないということ。

このことから、理論Aにbという仮定を付け加えた理論A+bがあるとして、A+bからAの無矛盾性が示せれば、bはAでは証明できないことが分かる。

ゲーデルは、数学理論をそれ自体の中で(自然数を使って)表現することで、「この命題は証明できない」と解釈できる命題を理論内で表現しこの二つの定理を証明している。この技法(ゲーデル数化)は現在でいうところのコンパイルなどに相当する（論理式(プログラム)->機械語という意味で）。

この定理は数学、情報科学、さらには哲学などにも大きな衝撃と影響を与えた。