ゲーデルの完全性定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/03/26 00:09 UTC 版)
 | 出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。 |
数理論理学においてゲーデルの完全性定理（ゲーデルのかんぜんせいていり、英: Gödel's completeness theorem、独: Gödelscher Vollständigkeitssatz）とは、一階述語論理の恒真な論理式はその公理系からすべて導出可能であることを示した定理を言う[1]。1929年にクルト・ゲーデルが証明した。
概要
1928年に、D. ヒルベルトとW. アッケルマンの共著書であり、一階述語論理（狭義の述語論理）を独立した論理体系として形式化した最初の本である『記号論理学の基礎』[2]の初版が出版されたが、この初版本において一階述語論理の完全性は一つの未解決問題であった[3]。この本を読み、この問題の解決に取り掛かったクルト・ゲーデルは、学位論文として1929年の秋にその結果を発表した。これがいわゆるゲーデルの完全性定理である[4]。
一階述語論理の論理式が恒真あるいは普遍妥当であるとは、個体領域の選び方のいかんにかかわらず、その変項に代入を行っても恒にその論理式が真となることを意味する。完全性定理は、論理式が論理的に妥当ならば、その論理式の有限な演繹（形式的証明）が存在することを示した。その演繹は有限であり、人間またはコンピュータによって検証可能である。この真理値と証明可能性の関係により、数理論理学におけるモデル理論と証明論の密接な関係が確立された。
完全性定理の重要な帰結の1つとして、任意の一階の理論について、その理論の公理を使った正しい演繹を全て数え上げることで、論理的帰結を数え上げることが可能であると示された。すなわち完全性定理は論理的帰結関係 
カテゴリ - 関係記事更新
固有名詞の分類
- ゲーデルの完全性定理のページへのリンク
