完全性

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

数理論理学には完全性(かんぜんせい、: completeness)と呼ばれる二つの関連するが異なる概念がある。

  1. 意味論的完全性: 形式論理体系が「恒真である命題が必ず証明できる」という性質を持つこと
  2. 構文論的完全性: 形式論理体系における理論が「(その理論で用いている言語で表現可能な)どの命題についても、肯定または否定を証明できる」という性質を持つこと

ゲーデルが証明したゲーデルの完全性定理は一階述語論理が意味論的完全性の意味で完全であるとする。

同じくゲーデルが証明した有名な不完全性定理は、自然数論についてのある理論が 後者の意味では完全ではなく、 完全であるように拡張すること(超越的な操作抜きには)もできないことを示した。現在では不完全性定理はPAなど他の自然数論の公理系や自然数論以外の公理系についても証明されており、一定の性質を満たす公理系であれば広く成り立つ定理であると理解されている。

関連項目[編集]

  • 完備 (曖昧さ回避) - complete, completeness は数学の他の分野では完備とも訳される。