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

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

概要

この定理には

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

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

の二つがある。

要約すると

一つ目は、数学の体系ではどのように公理を選んできても、その体系内に証明も反証もできない命題が存在することを意味する.仮にその命題を公理として付け加えても、別の証明も反証もできない命題が出てくる。

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

二つ目は、数学の体系の無矛盾性はその体系又はそれより弱い体系からは示せないことを表している。

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

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

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