ゲーデルの完全性定理
ゲーデルの完全性定理は、一階述語計算の演繹系が、全ての論理的に妥当な論理式の証明に追加の推論規則を必要としないという意味で「完全」であるとしている。完全性の逆は健全性であり、演繹系において論理的に妥当な論理式のみが証明可能だということを意味する。これらから、論理式が論理的に妥当であることと、それが形式的演繹の帰結であることは同値である。
ゲーデルの完全性定理をより一般化した版もある。すなわち、任意の一階の理論 T とその理論での言語における任意の命題 S について、T における S の形式的演繹が存在することと、S が T のあらゆるモデルで成り立つことは同値である。この一般化された定理は暗黙のうちに使われており、例えば、命題を群論の公理系で証明可能であることを示すとき、任意の群についてその命題が成り立つことを示すことで証明とする。
異なるモデルでも真となることを扱う数理論理学の一分野をモデル理論と呼ぶ。証明論という一分野では形式体系の証明そのものの構造を研究する。完全性定理は意味論と統語論の間を繋ぐことでこれら2つの分野の基本的な繋がりを確立している。
ゲーデルのオリジナルの証明(en)は、問題を論理式の特殊ケースを表すある統語論的な形式に還元し、以後はその形式を場当たり的な方法で扱った。
最近の論理学の文献では、 ヘンキンの証明の方がよく紹介されている。ヘンキンの証明では、任意の無矛盾な一階理論に適用できるような項モデル(en)を直接構築する。他の証明方法も存在する。