完全性定理(古典的命題論理)

主張

任意の論理式$ A について$ \vDash A \implies \vdash A

証明

1. 対偶を取る

任意の$ Aについて$ \not\vdash A \implies \not \vDash A

2. $ \not \vdash Aならば$ \not\vdash \lnot\lnot A

$ \lnot\lnot A \to A

3. $ \not \vdash \lnot(\lnot A)であるならば$ \{\lnot A\}はLP無矛盾(古典的命題論理)である

論理式集合$ \{\lnot A\}の組み合わせとして存在する唯一の組$ \lnot Aについて，$ \not\vdash \lnot(\lnot A)

4. 拡大定理(古典的命題論理)より，$ \{\lnot A\} \subseteq \Lambdaとなるような極大無矛盾集合(古典的命題論理)$ \Lambdaが存在する

5. $ \Lambdaから次の方法で付値関数(古典的命題論理)$ v_Aを定義出来る．

$ v_A:\bold{F} \mapsto \bold{T}

$ v_A(A) = 1 \iff A \in \Lambda

6. $ \lnot A \in \Lambdaなので，$ v_A(\lnot A) = 1

7. $ v_A(\lnot A) = 1 \iff v_A(A) = 0

8. $ v_A(A) = 0 \iff \not\vDash A