述語論理の完全性定理：記号論理学の到達点

述語論理の完全性定理は、20世紀論理学の金字塔の一つです。クルト・ゲーデルが1929年に証明したこの定理は、「証明できること」と「論理的に正しいこと」が一致することを保証します。

述語論理の完全性定理

完全性定理は次のように述べられます。

Γ ⊨ φ ならば Γ ⊢ φ

論理的に正しいことは、すべて証明可能である。言い換えれば、反例がなければ証明が存在します。

逆方向（健全性）も成り立ちます：Γ ⊢ φ ならば Γ ⊨ φ。証明可能なことは論理的に正しい。

両方を合わせると、⊨ と ⊢ が一致します。

ゲーデルの証明

ゲーデルは1929年の博士論文で完全性定理を証明しました。彼の証明の核心は、証明不可能な式には反例（その式を偽にするモデル）が存在することを示す点にあります。

証明の概略は次の通りです。φ が証明不可能と仮定します。¬φ を加えても矛盾しないことを示します。矛盾しない理論からモデルを構成します。このモデルで φ は偽なので、φ は論理的に正しくありません。

ヘンキンの証明

レオン・ヘンキンは1949年に、より直接的で明快な証明を与えました。ヘンキンの方法は「証人」（witness）を加えて理論を拡張し、その極大無矛盾拡大からモデルを構成するものです。

∃x φ(x) が理論に含まれるとき、φ© を満たす新しい定項 c（証人）を追加します。これを繰り返して「証人付き」の理論を作り、その項のなす構造がモデルになります。

完全性定理の意義

完全性定理には深い意義があります。

まず、構文と意味の一致を保証します。形式的な記号操作（証明）と、意味論的な真理の概念が、述語論理では完全に一致します。

次に、コンパクト性定理の証明に使えます。Γ ⊨ φ なら有限部分集合から証明可能、よって有限部分集合から帰結、というわけです。

完全性定理の限界

完全性定理は強力ですが、限界もあります。

算術のような特定の理論については、「標準モデル」で真であることと証明可能であることは一致しません。これがゲーデルの不完全性定理です。完全性定理は「すべてのモデルで真」と「証明可能」の一致を言っているのであり、「特定のモデルで真」については別問題です。

また、二階論理（述語に対する量化を許す論理）では完全性定理は成り立ちません。述語論理の完全性は、一階論理の特別な性質なのです。

完全性と不完全性

ゲーデルは完全性定理（1929年）と不完全性定理（1931年）の両方を証明しました。一見矛盾するように見えますが、異なる主張です。

完全性定理：述語論理の推論体系は完全（論理的に正しい式はすべて証明可能）。

不完全性定理：十分強い算術を含む理論は不完全（その理論で真だが証明不可能な式がある）。

次回からは、モデル理論の話題に入っていきます。