Augmentation; Completion of Completeness Proof

At this point, let us return to our overall strategy for establshing completeness. We have shown that a maximally consistent set containing witnesses is satisfiable. What remains to be shown is that a consistent set $\Phi$ can be augmented in order to produce a superset $\Phi^\star_w$ of that set that both contains witnesses and is maximally consistent. Exactly how this augmentation works depends on the size of the symbol set S upon which $\Phi$ is based: If S is countable, we take a certain route; if S is uncountable we take a different route. For the moment, let us assume that S is countable. Given this assumption, the first thing we need is a certain lemma:

Lemma 4.4   For $n \in$ N, let S_n be symbol sets such that $S_1 \subseteq S_2 \subseteq S_3 \ldots$ and let $\Phi_n$ be sets of S_n-formulas such that $\Phi_n$, based on symbol set S_n, is consistent (abbreviated Con_Sn $\Phi_n$), and $\Phi_1 \subseteq \Phi_2 \subseteq \Phi_3 \ldots$ Let $S = \bigcup_{\mbox{{\tiny$n \in$\space {\bf N}}}} S_n$ and $\Phi =\bigcup_{\mbox{{\tiny$n \in$\space {\bf N}}}} \Phi_n$. Then Con_S $\Phi$.

Proof. Suppose that the hypotheses of the lemma are true, and suppose as well -- for contradiction -- that Inc_S $\Phi$. Then for some finite subset $\Psi$ of $\Phi$ it is possible to derive a contradiction from $\Psi$. There is a k such that $\Psi \subseteq \Phi_k$ and so Inc_S $\Phi_k$. Specifically, $\Phi_k \vdash \phi$ and $\Phi_k \vdash \neg\phi$. The two derivations implied here contain only a finite number of symbols, so all the formulas in these derivations are contained in some L^S_m, where $m \ge k$. Then both of these derivations are derivations in S_m; from which it follows that Inc_Sm $\Phi_k$. Since $\Phi_k \subseteq \Phi_m$, it follows that Inc_Sm $\Phi_m$. This contradicts the hypotheses of the lemma. QED

Now we can prove that a consistent set can be extended to one that contains witnesses; here is the theorem and proof. (For the time being we shall assume that we are dealing with only a finite number of free variables.)

Theorem 4.3   Let $\Phi \subseteq L^S$ be consistent, where free$(\Phi)$ is finite and S is countable. Then there is a consistent set $\Psi$ such that $\Phi \subseteq \Psi \subseteq L^S$ and $\Psi$ contains witnesses.

Proof. We know that L^S is countable. Let

$$\exists x_1 \phi_1, \exists x_2 \phi_2, \ldots$$

be a list of all formulas in L^S that start with an existential quantifier. For each $\exists x_n \phi_n$ we define a witness formula $\psi_n$ that we add to $\Phi$; here's how we do it. Suppose that $\psi_m$ is already defined for m < n. Since free$(\Phi)$ is finite, only finitely many free variables occur in

$$\Phi \cup \{\psi_m : m < n\} \cup \{\exists x_n \phi_n\}.$$

Let y_n be a variable distinct from each of these free variables. Set

$$\psi_n = (\exists_n \phi_n \rightarrow \phi_n\frac{y_n}{x_n}).$$

Now set

$$\Psi = \Phi \cup \{\psi_1, \psi_2, \ldots\}.$$

Of course, $\Phi \subseteq \Psi$ and $\Psi$ contains witnesses.

Now let us show that $\Psi$ is consistent. In order to prepare for this demonstration, set

$$\Phi_n = \Phi \cup \{\psi : m < n\}.$$

Then $\Phi_1 \subseteq \Phi_2 \subseteq \cdots$ and $\Psi = \bigcup_{n \in \mbox{{\bf N}}} \Phi_n$. By Lemma 4.4 our proof will be completed if we can show that each $\Phi_n$ is consistent. We do so via an inductive argument on n.

Because $\Phi_1 = \Phi$, $\Phi_1$ is consistent by hypothesis; this takes care of the basis clause. Assume now that $\Phi_n$ is consistent, and assume as well, for contradiction, that $\Phi_{n+1} = \Phi_n \cup \{\psi_n\}$ is inconsistent. Then for every $\phi$ there is a set $\Delta \subseteq \Phi_{n+1}$ such that

$$\Delta \cup \{\psi_n\} \vdash \phi,$$ (4.7)

where $\phi$ here is a sentence. From this it follows that

$$\Delta \cup \{\neg \exists x_n \phi_n \vee \phi_n \frac{y_n}{x_n}\} \vdash \phi.$$ (4.8)

Now, obviously (by reiteration)

$$\Delta \cup \{\neg \exists_n \phi_n\} \vdash \neg \exists x_n \phi_n,$$ (4.9)

hence (by $\vee$ introduction)

$$\Delta \cup \{\neg \exists_n \phi_n\} \vdash \neg \exists x_n \phi_n \vee \phi_n \frac{y_n}{x_n}.$$ (4.10)

It follows from 4.8 and 4.10 that

$$\Delta \cup \{\neg \exists_n \phi_n\} \vdash \phi.$$ (4.11)

By parallel reasoning we can obtain

$$\Delta \cup \phi_n\frac{y_n}{x_n} \vdash \phi.$$ (4.12)

And this last equation, in light of the fact that y_n cannot occur free in $\Delta \cup \{\exists x_n \phi_n\} \cup \{\phi\}$, allows us to use the rule $\exists$ elimination in order to obtain

$$\Delta \cup \{\exists x_n \phi_n\} \vdash \phi.$$ (4.13)

Given the fact that any formula of the form $\psi \vee \neg\psi$ can be derived without any remaining suppositions, it follows from 4.13 and 4.11 that

$$\Delta \vdash \phi.$$ (4.14)

This implies that $\Phi_n \vdash \phi$, which in turn implies that $\Phi_n$ is inconsistent (just select contradictory sentences for $\phi$), which in turn implies that the induction hypothesis is false. QED

It is left to the reader to establish that augmentation of a consistent set to a maximally consistent set can be carried out. (The proof is easy; it parallels the one given for the propositional case in the metatheory for propositional languages.) Given this demonstration, given that we can handle the case where the set of free variables in the set $\Phi$ to be augmented is not finite, and given that we can prove that in the case were this set $\Phi$ is based on an uncountable symbol set we can still augment $\Phi$ to a consistent superset $\Phi_w$ that contains witnesses, the completeness proof is finished. The givens cited here will be proved in subsequent drafts of this text.