Lesson 16

Finally, we shall prove the completeness theorem.

Theorem. If \(\Delta\) is consistent, then it has a model.

Proof. We are given a set \(\Delta\) of expressions over a vocabulary \(\Sigma\). We know that \(\Delta\) is consistent. Based on this information alone, we must find a model for \(\Delta\). The task seems formidable: We must somehow build a semantic structure from the syntactic information we currently possess. The solution is simple and ingenious: Our model will be a syntactic one, based on the elements of our language. In particular, our universe will be the set of all terms over \(\Sigma\). And the details of the model (the values of the relations and functions) will be defined as mandated by the expressions in \(\Delta\).

There are serious difficulties in implementing this plan. First, the universe of all terms may not be rich enough to provide a model: Consider \(\Delta = \{\exists x\ P(x)\} \cup \{\neg P(t) : t \text{is a term over} \Sigma\}\). Although this is a consistent set of expressions, it is easy to see that there is no way to satisfy it by a model whose universe contains just the terms of \(\Sigma\). Another difficulty is that the expressions in \(\Delta\) may be too few and inconclusive to drive our definition of the model. For a certain term \(t\), they may provide no clue on whether \(P(t)\) or not.

To avoid these difficulties, we employ a maneuver due to Leon Henkin, explained below. First, we add to \(\Sigma\) a countable infinity of constants, \(c_{1}, c_{2}, …\) Call the resulting vocabulary \(\Sigma'\). We have to prove that our hypothesis remains valid:

Lemma. \(\Delta\) remains consistent when considered as a set of expressions over \(\Sigma'\).

Proof. Suppose that there is a proof \(S = (\phi_{1}, …, \phi_{n})\) of some contradiction from \(\Delta\) using expressions over \(\Sigma'\). We can assume that there is an infinity of variables not appearing in \(\Delta\), call them \(x_{1}, x_{2}, …\) To see why these variables must exist, first recall that our vocabulary of variables is infinite. Even if they all appear in \(\Delta\), we can redefine \(\Delta\) so that it uses only odd-numbered variables from our set, and so an infinity of variables remains unused.

From the proof \(S\) of the contradiction we construct a new proof \(S'\), in which every occurrence of constant \(c_{i}\) is replaced by variable \(x_{i}\). This new proof proves a contradiction in the original vocabulary of \(\Delta\), which is absurd because \(\Delta\) was assumed consistent.◼

Having introduced the constants \(c_{i}\), we add to \(\Delta\) new expressions (enough to make it “conclusive”), as follows. Consider an enumeration of all expressions over \(\Sigma'\): \(\phi_{1}, \phi_{2}, …\) We shall define a sequence of successive enhancements of \(\Delta\) by new expressions, \(\Delta_{i}\), for \(i = 0, 1, …\) Define \(\Delta_{0} = \Delta\), and suppose that \(\Delta_{1}, …, \Delta_{i-1}\) have already been defined. \(\Delta_{i}\) depends on \(\Delta_{i-1}\) and \(\phi_{i}\). There are four cases:

1. \(\Delta_{i-1}\cup \{\phi_{i}\}\) is consistent, and \(\phi_{i}\) is not of the form \(\exists x \ \psi\). Then \(\Delta_{i} = \Delta_{i-1}\cup \{\phi_{i}\}\).
2. \(\Delta_{i-1}\cup \{\phi_{i}\}\) is consistent, and \(\phi_{i} = \exists x \ \psi\). Let \(c\) be a constant not appearing in any one of the expressions \(\phi_{1}, …, \phi_{i-1}\) (since we have an infinite supply of constants, such a constant exists). Then we let \(\Delta_{i} = \Delta_{i-1}\cup \{\exists x \ \psi, \psi[x \gets c]\}\).
3. \(\Delta_{i-1}\cup \{\phi_{i}\}\) is inconsistent, and \(\phi_{i}\) is not of the form \(\forall x \ \psi\). Then \(\Delta_{i} = \Delta_{i-1}\cup \{\neg \phi_{i}\}\).
4. \(\Delta_{i-1}\cup \{\phi_{i}\}\) is inconsistent, and \(\phi_{i} = \forall x \ \psi\). Let \(c\) be a constant not appearing in any one of the expressions \(\phi_{1}, …, \phi_{i-1}\) (since we have an infinite supply of constants, such a constant exists). Then we let \(\Delta_{i} = \Delta_{i-1}\cup \{\neg \forall x \ \psi, \neg \psi[x \gets c]\}\).

Lemma. For all \(i \geq 0\), \(\Delta_{i}\) is consistent.

Proof. Induction on \(i\). For the basis, \(\Delta_{0} = \Delta\) is definitely consistent. Suppose then that \(\Delta_{i-1}\) is consistent.

If \(\Delta_{i}\) was obtained by Case 1, then it is clearly consistent. If Case 3 prevails, then we know that \(\Delta_{i-1}\cup \{\phi_{i}\}\) is inconsistent, and since \(\Delta_{i-1}\) is consistent, so is \(\Delta_{i} = \Delta_{i-1}\cup \{\neg \phi_{i}\}\).

Finally, suppose that Case 4 prevails, and \(\Delta_{i}\) is inconsistent (the same argument holds for Case 2). Arguing by contradiction, \(\Delta_{i-1}\cup \{\neg \psi[x \gets c]\} \vdash \forall x \ \psi\); but we know that also \(\Delta_{i-1}\vdash \neg \forall x \ \psi\), and so \(\Delta_{i-1}\cup \{\neg \psi[x \gets c]\}\) is inconsistent. Arguing by contradiction, \(\Delta_{i-1}\vdash \psi[x \gets c]\).

However, we know that \(c\) does not appear in any expression in \(\Delta_{i-1}\), and thus we can replace \(c\) by a new variable \(y\) throughout this latter proof. Thus, \(\Delta_{i-1}\vdash \psi[x \gets y]\). By justified generalization, \(\Delta_{i-1}\vdash \forall y \ \psi[x \gets y]\). Changing names of the variables and take an alphabetic variant of the latter expression, we obtain \(\Delta_{i-1}\vdash \forall x \ \psi\) (we've left an exercise that this replacement is correct). But we know that \(\Delta_{i-1}\cup \{\forall x \ \psi\}\) is inconsistent, and thus \(\Delta_{i-1}\) is inconsistent, a contradiction.◼

Define thus \(\Delta'\) to be the union of all \(\Delta_{i}\)'s. That is, \(\Delta'\) contains all expressions that appear in some \(\Delta_{i}\), \(i \geq 0\). \(\Delta'\) contains the original \(\Delta\), and has some remarkable properties: First, for any expression \(\phi\) over \(\Sigma'\), either \(\phi\) or \(\neg \phi\) is in \(\Delta'\): We say \(\Delta'\) is complete. Second, for any expression \(\exists x \ \phi\) in \(\Delta'\), there is in \(\Delta'\) an expression of the form \(\phi[x \gets c]\): We say \(\Delta'\) is closed. Finally, it is easy to see that \(\Delta'\) is consistent: Any proof of a contradiction would involve finitely many expressions, and thus only expressions in \(\Delta_{i}\), for some \(i\). But we know that \(\Delta_{i}\) is consistent, and thus no contradictions can be proved from it.

We are now in a position to apply our original idea of “semantics by syntax.” Consider the set \(T\) of all terms over \(\Sigma'\). Define an equivalence relation on this set, as follows: \(t \equiv t'\) if and only if \(t = t' \in \Delta'\). The equivalence class of term \(t \in T\) is denoted \([t]\). Let \(U\) be the set of equivalence classes of \(T\) under \(\equiv\). \(U\) is the universe of our model \(M\).

We next define the values of the variables, functions, and predicates under \(M\). For every variable \(x\), let \(x^{M}=[x]\). If \(f\) is a \(k\)-ary function symbol in \(\Sigma'\) and \(t_{1}, …, t_{k}\) are terms, then \(f^{M}([t_{1}], …, [t_{k}]) = [f(t_{1}, …, t_{k})]\). If \(R\) is a \(k\)-ary relation symbol in \(\Sigma'\) and \(t_{1}, …, t_{k}\) are terms, then \(R^{M}([t_{1}], …, [t_{k}])\) if and only if \(R(t_{1}, …, t_{k}) \in \Delta'\). This completes the definition of \(M\).

It takes some argument to verify that this model “makes sense,” that the definitions of \(f^{M}\) and \(R^{M}\) are independent of the particular representatives for the class \([t_{i}]\). Suppose that \(t_{1}, …, t_{k}, t_{1}', …, t_{k}'\) are terms such that \(t_{i} \equiv t_{i}'\) for all \(i\). Then we claim that \(f(t_{1}, …, t_{k}) \equiv f(t_{1}', …, t_{k}')\), and thus \([f(t_{1}, …, t_{k})]\) is indeed independent of the choice of the representatives \(t_{i}\).

The reason is that \(t_{i} \equiv t_{i}'\) for all \(i\) means \(t_{i} = t_{i}' \in \Delta'\) for all \(i\), and hence \(\Delta' \vdash f(t_{1}, …, t_{k}) = f(t_{1}', …, t_{k}')\), with the help of axiom AX2b. Hence the latter expression is in \(\Delta'\), and \(f(t_{1}, …, t_{k}) \equiv f(t_{1}', …, t_{k}')\).

Also, the same way we establish, by induction on the structure of \(t\), that \(t^{M} = [t]\). As for the definition of \(R^{M}\): If \(t_{i} \equiv t_{i}'\) for all \(i\), then \(M \models R(t_{1}, …, t_{k})\) if and only if \(M \models R(t_{1}', …, t_{k}')\), through axiom AX2c. The following result now finishes the proof of the completeness theorem:

Lemma. \(M \models \Delta'\).

Proof. We shall show, by induction on the structure of \(\phi\), that \(M \models \phi\) if and only if \(\phi \in \Delta'\). For the basis, suppose that \(\phi\) is atomic, \(\phi = R(t_{1}, …, t_{k})\). By the definition of \(R^{M}\), we know that \(R^{M}(t_{1}^{M}, …, t_{k}^{M})\) if and only if \(\phi \in \Delta'\).

Suppose then that \(\phi = \neg \psi\). \(M \models \phi\) if and only if \(M \not\models \psi\). By induction, \(M \not\models \psi\) if and only if \(\psi \not\in \Delta'\), which, by the completeness of \(\Delta'\), happens if and only if \(\phi \in \Delta'\).

If \(\phi = \psi_{1} \vee \psi_{2}\), then \(M \models \phi\) if and only if \(M \models \psi_{i}\) for at least one \(i\), which, by induction, happens if and only if at least one \(\psi_{i}\) is in \(\Delta'\). By consistency and completeness, this happens if and only if \(\phi \in \Delta'\). Similarly for the case \(\phi = \psi_{1} \wedge \psi_{2}\).

Suppose then that \(\phi = \forall x \ \psi\). We claim that \(\phi \in \Delta'\) if and only if \(\psi[x \gets t] \in \Delta'\) for all terms \(t\) (this would complete the proof).

Suppose that \(\phi \in \Delta'\). Then, for each term \(t\), \(\Delta' \vdash \psi[x \gets t]\) (by invoking the axiom \(\forall x \ \psi \Rightarrow \psi[x \gets t]\) and modus ponens). Since \(\Delta'\) is complete, \(\psi[x \gets t] \in \Delta'\).

Conversely, suppose that \(\phi \not\in \Delta'\). Then \(\neg \forall x \ \psi\) was introduced to \(\Delta'\) during its construction, and \(\neg \psi[x \gets c]\) was introduced along with it. Hence, \(\psi[x \gets c] \not\in \Delta'\). Since \(c\) is a constant, it is free for \(x\) in \(\psi\), so we may take \(\psi_{c}=\psi\). The proof is complete.◼◼