8件
不完全性定理とは、ゲーデルが1931年に発表した定理である。
概要
この定理には
第一「再帰的で(ω)無矛盾な自然数論を充分に表現できる形式系は完全ではない.」
第二「再帰的で無矛盾な自然数論を充分に表現できる形式系は自分自身の無矛盾性を証明できない.」
の二つがある。
(以下、理論=形式系、仮定=公理、主張=論理式(命題)とする。)
要約すると
一つ目は、どんな数学理論にもその理論の中で表現できる主張で正否の判定ができないものが存在する。
この例として、ZFに対する選択公理、ZFC（ZF＋選択公理）に対する連続体仮説などが存在する。
二つ目は、数学理論の無矛盾性はその理論又はそれより強くない(より多くの仮定を含まない)理論からは示せないということ。
このことから、理論Aにbという仮定を付け加えた理論A+bがあるとき、A+bからAの無矛盾性が示せれば、bはAでは証明できないことが分かる。
ゲーデルは、数学理論をそれ自体の中で(自然数を使って)表現することで、「この命題は証明できない」と解釈できる命題を理論内で表現しこの二つの定理を証明している。この技法(ゲーデル数化)は現在でいうところのコンパイルなどに相当する（論理式(プログラム)->機械語という意味で）。
チューリングマシンの停止問題は、この不完全性定理をコンピュータの用語に置き換えたものである。
この定理は数学、情報科学、さらには哲学などにも大きな衝撃と影響を与えた。
関連動画
関連商品
関連コミュニティ
関連項目
- 4
- 0pt
