Completeness

Theorem 3.2 (Completeness of Propositional Calculus)   Let $\Phi$ be a set of formulas of the propositional calculus, and let $\phi$ be one such formula. Then

$$\mbox{If } \Phi \models \phi \mbox{ then } \Phi \vdash \phi.$$

First we need to define consistency, both the syntactic variety and the semantic variety. In the syntactic variety we say simply that a set $\Phi$ is consistent, which is to say that it's not the case that from this set a contradiction can be proved (in some particular proof theoretic scheme; we have been using the Fitch-style system seen in HYPERPROOF). (A set $\Phi$ is then inconsistent provided that there is a formula $\phi$ such that $\Phi \vdash \phi$ and $\Phi \vdash \not\phi$. This is equivalent to saying that $\Phi$ is inconsistent when every formula can be derived from this set.) The semantic variety of consistency is truth-functional consistency. We say that a set $\Phi$ of formulas of the propositional calculus is truth-functionally inconsistent exactly when there is no truth-value assignment $\cal V$ such that $\cal V$ $\: \models \Phi$.

Let us first recast the completeness theorem into an equivalent form that will be easier to prove. This recasting uses two facts that are easy to prove, namely,

• For any set $\Gamma$ of formulas of the propositional calculus, and any formula $\phi$ of the propositional calculus, $\Gamma \models \phi$ if and only if $\Gamma \cup \{\neg\phi\}$ is truth-functionally inconsistent.
• For any set $\Gamma$ of formulas and any formula $\phi$, both of the propositional calculus, $\Gamma \vdash \phi$ iff $\Gamma \cup \{\neg\phi\}$ is inconsistent.

It follows from these two facts that the Completeness Theorem is equivalent to

• If $\Gamma \cup \{\neg\phi\}$ is truth-functionally inconsistent, then $\Gamma \cup \{\neg\phi\}$ is inconsistent,

which in turn is entailed by

• If $\Gamma$ is truth-functionally inconsistent, then $\Gamma$ is inconsistent (where both are sets of formulas in the propositional calculus).

Finally, taking the contrapositive of this conditional, we see that the Completeness Theorem is proved if we can establish

$$\mbox{If } \Gamma \mbox{ is consistent, then } \Gamma \mbox{ is truth-functionally consistent.}$$ (3.4)

Now, in order to prove 3.4, we will need use the following two lemmas.

Lemma 3.3   If $\Gamma$ is a consistent set, then there exists a maximally consistent superset $\Gamma^\star$ of $\Gamma$.

Lemma 3.4   All maximally consistent sets are truth-functionally consistent.

Obviously, the concept of a maximally consistent set is crucial. What is such a set? Intuitively, a maximally consistent set is one that is not only consistent, but also so large that any individual formula consistent with this set is already in the set.

In order to construct a maximally consistent set we will first need to devise a method for mechanically enumerating all the elements of $\cal L$_PC. There are a number of such methods available; here is one. First, consider the following table:

$$\begin{array}{ll\vert ll\vert ll} ( & 1 & \wedge & 2 & P_1 &... ... & & & P_5 & 399999\\ & & & & \vdots & \vdots \\ \end{array}$$

The idea here is to associate every symbol from the alphabet of the propositional calculus with the numeral to its immediate right. Given this association, every wff has a corresponding number. For example, the wff

$$(P_2 \vee P_{23})$$

corresponds to the number

$$139293\!\!\!\!\overbrace{9\cdots9}^{22 \mbox{ times}}\!\!\!19.$$

It should be obvious that every wff corresponds to a one and only one number. It should also be obvious that we now have a way of generating all the wffs in $\cal L$_PC one after another. To do so, we list the wff corresponding to the smallest number that denotes a wff (this would be P), then the wff corresponding to the next number (Q), and so on. (Recall that P₁ = P, P₂ = Q, P₃ = R.) This gives a list

$$\phi_1, \phi_2, \phi_3, \ldots$$

of all the formulas composing $\cal L$_PC.

Now that we have a method for enumerating all the formulas of the propositional calculus, we can proceed to the method for constructing a maximally consistent set given a consistent set as input: First, we fix some set $\Gamma$ consistent by hypothesis. Then we set up the following progression.

1.

$\Gamma_1 = \Gamma$

2.

$\Gamma_{i+1} = \Gamma_i \cup \{\phi_i\} \mbox{ if } \Gamma_i \cup \{\phi_i\}$ is consistent; otherwise set $\Gamma_{i+1} = \Gamma_i$.

$\Gamma^\star$, our maximally consistent set, is the union of all sets in this seequence; more precisely,

$\Gamma^\star = \{\phi \in \cal L$ $_{PC}: \phi \in \Gamma_k, k \in$ N}.

We are now ready to prove Lemma 3.3: To establish that $\Gamma^\star$, we first show by mathematical induction that every set in the sequence $\Gamma_1, \Gamma_2, \Gamma_3, \ldots$ is consistent. The basis clause is trivial, for $\Gamma_1 = \Gamma$, and $\Gamma$ is consistent by hypothesis. Now assume that $\Gamma_k$ is consistent, for all $i \le k$. Consider now the set $\Gamma_{k+1}$. There are two possibilities; either $\Gamma_{k+1}$ is $\Gamma_k \cup \phi_k$ or it is $\Gamma_k$. By definition, the former possibliity only obtains if $\Gamma_k \cup \phi_k$ is consistent, in which case $\Gamma_{k+1}$ is consistent as well. In latter case $\Gamma_k$ is consistent by the inductive hypothesis. Now suppose for contradiction that $\Gamma^\star$ is not consistent. Then some finite nonempty subset $\Gamma'$ of $\Gamma^\star$ is inconsistent. (Why?) Let $\phi_m$ be the formula in $\Gamma'$ that comes last in the enumeration of $\cal L$_PC. From this it follows that every element of $\Gamma'$ is an element of $\Gamma_{m+1}$. Now if we knew that

(+)

If a set $\Delta$ is inconsistent, then every superset of $\Delta$ is inconsistent.

we could conclude that $\Gamma_{m+1}$ is inconsistent, which would give us the desired contradiction (since we proved above that every member of this sequence is inconsistent). The proof of (+) is left as an exercise.

Now for the proof that $\Gamma^\star$ is maximally consistent. For contradiction, assume that $\Gamma^\star$ is not maximally consistent. There there is a formula $\psi_n \in \cal L$_PC such that

$$\psi_n \not\in \Gamma^\star \mbox{ and } \Gamma^\star \cup \{\psi_n\} \mbox{ is consistent}.$$

Since every superset of an inconsistent set is itself inconsistent, it follows that every subset of a consistent set is itself consistent. So, since

$$\Gamma_n \cup \{\psi_n\} \subseteq \Gamma^\star \cup \{\psi\}$$

it follows that $\Gamma_n \cup \{\psi_n\}$ is consistent. But this set is just $\Gamma_{n+1}$ in our sequence. Hence $\psi_n \in \Gamma^\star$, which gives us our contradiction. QED

Now for the proof of Lemma 3.4, the bulk of which we will leave as an exercise after conveying the core ideas in the proof. To begin, let $\cal V$$^\star$ be the truth-value assignment that assigns T to every atomic formula in $\Gamma^\star$ and F to every atomic formula of $\cal L$_PC not in $\Gamma^\star$. (Notice that $\cal V$$^\star$ assigns a truth-value to every atomic formula in $\cal L$_PC.) The lemma is established once we show

(++)

$\cal V$ $^\star \models \phi \mbox{ iff } \phi \in \Gamma^\star$

The proof of (++) now proceeds by mathematical induction on the number of connectives in formulas. The basis clause is effortless: in this case $\phi$ is atomic, and $\cal V$ $^\star \models \phi$ by definition. We now partition the remaining formulas into the following familiar forms.

1.

$\neg \psi$

2.

$\psi \wedge \delta$

3.

$\psi \vee \delta$

4.

$\psi \rightarrow \delta$

5.

$\psi \leftrightarrow \delta$

We give the sub-proof for the first of these five forms; the others are left as exercises. For this form, we rely on a fact that is left to the reader to prove, namely:

($\ast^\neg$)

For all formulas $\phi \in \cal L$ $_{PC}, \phi \in \Gamma^\star \mbox{ iff } \neg\phi \in \Gamma^\star$.^3.3

Suppose, for the ``only if" direction of (++), that $\phi = \neg \psi$, and that $\cal V$ $^\star \models \neg \psi$. Then $\cal V$ $^\star \not\models \psi$; and it follows by the inductive hypothesis that $\psi \not\in \Gamma^\star$. By ($\ast^\neg$) it follows that $\neg\psi \in \Gamma^\star$. For the ``if" direction, suppose that $\phi \in \Gamma^\star$; that is, $\neg\psi \in \Gamma^\star$. By ($\ast^\neg$) it follows that $\psi \not\in \Gamma^\star$. By the inductive hypothesis it follows that $\cal V$ $^\star \not\models \psi$, which implies by the truth-table for negation that $\cal V$ $^\star \models \neg \psi$, i.e., that $\cal V$ $^\star \models \phi$. QED