書記が数学やるだけ#956 完全性の証明

ここまでの準備をもとに完全性の証明を行う。

問題

説明

ゲーデルの完全性定理とは、一階述語論理において意味論的に恒真である論理式は、その公理系から構文論的にすべて証明可能であることを示した定理である。1929年にクルト・ゲーデルによって証明された。

解答

Γ には c1 =c2  が属しているため、c1  と c2  は同じ同値類に属する。一方、¬(c1 =c3 ) が属しているため、c3 は異なる同値類となる。ドメイン D は、これらの同値類そのものを要素とする集合（商集合）である。

定数記号の解釈は、「その記号自身が属する同値類」として定義される。一方，述語 P の解釈 I(P) は、「Γ において P(c) が成立している定数 c の同値類」を集めた部分集合である。

変数の割り当てに基づきモデルにおける関係を Γ の中身と照合すると，「ヘンキン集合 Γ に属する記号の事実（構文論）」が、「構築されたモデル M における真偽（意味論）」へと完全に反映されていることが言える。

真理基準定理（Truth Lemma）は、構文論的に構成された極大無矛盾なヘンキン集合 Γ から、意味論的な解釈構造である項モデル（ヘンキン・ストラクチャー） M を厳密に構成した際、モデル M における任意の論理式の充足関係（真偽）が、Γ の要素関係として完全かつ無矛盾に再現されることを保証するメタ定理である。

ゲーデルの完全性定理の対偶の証明は、構文論的な無矛盾性から意味論的な反例モデルを構文論的に構成する一連のプロセスとして、以下のように形式化される。

コンパクト性定理（Compactness theorem）とは、一階述語論理の文の集合がモデルを持つこと（充足可能であること）と、その集合の任意の有限部分集合がモデルを持つことが同値であるという定理である。

本記事のもくじはこちら：