completeness theorem for propositional logic

The completeness theorem of propositional logic is the statement that a wff is tautology iff it is a theorem. In symbol, we have

$$\vDash A\mathit{\hspace{1em}}\text{iff}\mathit{\hspace{1em}}⊢A$$

for any wff $A$. The “if” part of the statement is the soundness theorem, and is proved here (http://planetmath.org/TruthValueSemanticsForPropositionalLogicIsSound). We will prove the “only if” part, which is also known as the completeness portion of the theorem. We will give a constructive proof of this. Before proving this, we state and prove some preliminary facts:

1. $A,B⊢A\to B$

2. $A,\mathrm{\neg }B⊢\mathrm{\neg }(A\to B)$

3. $\mathrm{\neg }A,B⊢A\to B$

4. $\mathrm{\neg }A,\mathrm{\neg }B⊢A\to B$

5. Let $v$ be a valuation. For any wff $A$, let $v[A]$ be defined as follows:

   Suppose $p_1,\mathrm{\dots },p_n$ are the propositional variables in $A$. Then

   $$v[p_1],\mathrm{\dots },v[p_n]⊢v[A].$$

6. if $\mathrm{\Delta },A⊢B$ and $\mathrm{\Delta },\mathrm{\neg }A⊢B$, then $⊢B$.

Proof.

Facts 1 and 3 come from the axiom schema $B\to (A\to B)$. From $⊢B\to (A\to B)$, we have $C⊢B\to (A\to B)$, so $C,B⊢A\to B$. If $C$ is $A$, we have fact 1, and if $C$ is $\mathrm{\neg }A$, we have fact 3.

Fact 2: this is proved here (http://planetmath.org/SubstitutionTheoremForPropositionalLogic).

Fact 4: By ex falso quodlibet, $⊢⟂\to B$, so $A⊢⟂\to B$, and therefore $⊢A\to (⟂\to B)$ by the deduction theorem. Now, $(A\to (⟂\to B))\to ((A\to ⟂)\to (A\to B))$ is an axiom instance, so $⊢(A\to ⟂)\to (A\to B)$, or $⊢\mathrm{\neg }A\to (A\to B)$, or $\mathrm{\neg }A⊢A\to B$, and

$$\mathrm{\neg }A,\mathrm{\neg }B⊢A\to B$$

all the more so.

Fact 5: by induction on the number $n$ of occurrences of $\to$ in $A$. If $n=0$, then $A$ is either $⟂$ or a propositional variable $p$. In the first case, $v[A]$ is $\mathrm{\neg }⟂$, and from $⟂⊢⟂$, we get $⊢⟂\to ⟂$, or $⊢\mathrm{\neg }⟂$. In the second case, $v[p]⊢v[p]$. Now, suppose there are $n+1$ occurrences of $\to$ in $A$. Let $p_1,\mathrm{\dots },p_m$ be the propositional variables in $A$. By unique readability, $A$ is $B\to C$ for some unique wff’s $B$ and $C$. Since each $B$ and $C$ has no more than $n$ occurrences of $\to$, by induction, we have

$$v[p_{i(1)}],\mathrm{\dots },v[p_{i(s)}]⊢v[B]\mathit{\hspace{1em}\hspace{1em}}\text{and}\mathit{\hspace{1em}\hspace{1em}}v[p_{j(1)}],\mathrm{\dots },v[p_{j(t)}]⊢v[C],$$

where the propositional variables in $B$ are $p_{i(1)},\mathrm{\dots },p_{i(s)}$, and in $C$ are $p_{j(1)},\mathrm{\dots },p_{j(t)}$. So

$$v[p_1],\mathrm{\dots },v[p_m]⊢v[B]\mathit{\hspace{1em}\hspace{1em}}\text{and}\mathit{\hspace{1em}\hspace{1em}}v[p_1],\mathrm{\dots },v[p_m]⊢v[C].$$

Next, we want to show that $v[B],v[C]⊢v[B\to C]$. We break this into four cases:

• if $v[B]$ is $B$ and $v[C]$ is $C$: then $v[B\to C]$ is $B\to C$, and use Fact 1

• if $v[B]$ is $B$ and $v[C]$ is $\mathrm{\neg }C$: then $v[B\to C]$ is $\mathrm{\neg }(B\to C)$, and use Fact 2

• if $v[B]$ is $\mathrm{\neg }B$ and $v[C]$ is $C$: then $v[B\to C]$ is $B\to C$, and use Fact 3

• if $v[B]$ is $\mathrm{\neg }B$ and $v[C]$ is $\mathrm{\neg }C$: then $v[B\to C]$ is $B\to C$, and use Fact 4.

In all cases, we have by applying modus ponens,

$$v[p_1],\mathrm{\dots },v[p_m]⊢v[B\to C].$$

Fact 6 is proved here (http://planetmath.org/SubstitutionTheoremForPropositionalLogic).∎

Theorem 1.

Propositional logic is complete with respect to truth-value semantics.

Proof.

Suppose $A$ is a tautology. Let $p_1,\mathrm{\dots },p_n$ be the propositional variables in $A$. Then

$$v[p_1],\mathrm{\dots },v[p_n]⊢v[A]$$

for any valuation $v$. Since $v[A]$ is $A$. We have

$$v[p_1],\mathrm{\dots },v[p_n]⊢A.$$

If $n=0$, then we are done. So suppose $n>0$. Pick a valuation $v$ such that $v(p_n)=1$, and a valuation $v^{\prime }$ such that $v^{\prime }(p_i)=v(p_i)$ and $v^{\prime }(p_n)=0$ Then

$$v[p_1],\mathrm{\dots },v[p_{n-1}],p_n⊢A\mathit{\hspace{1em}\hspace{1em}}\text{and}\mathit{\hspace{1em}\hspace{1em}}v[p_1],\mathrm{\dots },v[p_{n-1}],\mathrm{\neg }{p}_n⊢A,$$

where the first deducibility relation comes from $v$ and the second comes from $v^{\prime }$. By Fact 6 above,

$$v[p_1],\mathrm{\dots },v[p_{n-1}]⊢A.$$

So we have eliminated $v[p_n]$ from the left of $v[p_1],\mathrm{\dots },v[p_n]⊢A$. Now, repeat this process until all of the $v[p_i]$ have been eliminated, and we have $⊢A$.∎

The completeness theorem can be used to show that certain complicated wff’s are theorems. For example, one of the distributive laws

$$⊢(A\wedge B)\vee C\leftrightarrow (A\vee C)\wedge (B\vee C)$$

To see that this is indeed a theorem, by the completeness theorem, all we need to show is that it is true using the truth table:

$(A$	$\wedge$	$B)$	$\vee$	$C$	$\leftrightarrow$	$(A$	$\vee$	$C)$	$\wedge$	$(B$	$\vee$	$C)$
T	T	T	T	T	T	T	T	T	T	T	T	T
T	T	T	T	F	T	T	T	F	T	T	T	F
T	F	F	T	T	T	T	T	T	T	F	T	T
T	F	F	F	F	T	T	T	F	F	F	F	F
F	F	T	T	T	T	F	T	T	T	T	T	T
F	F	T	F	F	T	F	F	F	F	T	T	F
F	F	F	T	T	T	F	T	T	T	F	T	T
F	F	F	F	F	T	F	F	F	F	F	F	F

$Similarly,onecanshow$⊢(A∨B)∧C ↔(A∧C)∨(B∧C)