completeness theorem for propositional logic

 $\models A\quad\mbox{iff}\quad\vdash 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. 1.

$A,B\vdash A\to B$

2. 2.

$A,\neg B\vdash\neg(A\to B)$

3. 3.

$\neg A,B\vdash A\to B$

4. 4.

$\neg A,\neg B\vdash A\to B$

5. 5.

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

 $v[A]\textrm{ is }\left\{\begin{array}[]{ll}A&\textrm{if }v(A)=1,\\ \neg A&\textrm{if }v(A)=0.\end{array}\right.$

Suppose $p_{1},\ldots,p_{n}$ are the propositional variables in $A$. Then

 $v[p_{1}],\ldots,v[p_{n}]\vdash v[A].$
6. 6.

if $\Delta,A\vdash B$ and $\Delta,\neg A\vdash B$, then $\vdash B$.

Proof.

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

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

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

 $\neg A,\neg B\vdash 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 $\perp$ or a propositional variable $p$. In the first case, $v[A]$ is $\neg\perp$, and from $\perp\vdash\perp$, we get $\vdash\perp\to\perp$, or $\vdash\neg\perp$. In the second case, $v[p]\vdash v[p]$. Now, suppose there are $n+1$ occurrences of $\to$ in $A$. Let $p_{1},\ldots,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)}],\ldots,v[p_{i(s)}]\vdash v[B]\qquad\mbox{and}\qquad v[p_{j(1)}],% \ldots,v[p_{j(t)}]\vdash v[C],$

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

 $v[p_{1}],\ldots,v[p_{m}]\vdash v[B]\qquad\mbox{and}\qquad v[p_{1}],\ldots,v[p_% {m}]\vdash v[C].$

Next, we want to show that $v[B],v[C]\vdash 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 $\neg C$: then $v[B\to C]$ is $\neg(B\to C)$, and use Fact 2

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

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

 $v[p_{1}],\ldots,v[p_{m}]\vdash v[B\to C].$

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

Proof.

Suppose $A$ is a tautology. Let $p_{1},\ldots,p_{n}$ be the propositional variables in $A$. Then

 $v[p_{1}],\ldots,v[p_{n}]\vdash v[A]$

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

 $v[p_{1}],\ldots,v[p_{n}]\vdash 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}],\ldots,v[p_{n-1}],p_{n}\vdash A\qquad\mbox{and}\qquad v[p_{1}],\ldots% ,v[p_{n-1}],\neg p_{n}\vdash A,$

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

 $v[p_{1}],\ldots,v[p_{n-1}]\vdash A.$

So we have eliminated $v[p_{n}]$ from the left of $v[p_{1}],\ldots,v[p_{n}]\vdash A$. Now, repeat this process until all of the $v[p_{i}]$ have been eliminated, and we have $\vdash A$. ∎

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

 $\vdash(A\land B)\lor C\leftrightarrow(A\lor C)\land(B\lor 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$ $\land$ $B)$ $\lor$ $C$ $\leftrightarrow$ $(A$ $\lor$ $C)$ $\land$ $(B$ $\lor$ $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

${}\end{center}Similarly,onecanshow$⊢(A∨B)∧C ↔(A∧C)∨(B∧C)${{{.\inner@par\begin{flushright}\begin{tabular}[]{|ll|}\hline Title&completeness % theorem for propositional logic\\ Canonical name&CompletenessTheoremForPropositionalLogic1\\ Date of creation&2013-03-22 19:32:47\\ Last modified on&2013-03-22 19:32:47\\ Owner&CWoo (3771)\\ Last modified by&CWoo (3771)\\ Numerical id&21\\ Author&CWoo (3771)\\ Entry type&Theorem\\ Classification&msc 03B05\\ \hline}\end{tabular}}}\end{flushright}\end{document}$