We want to show that the deductive system is complete, that is, that given a set of formulas \(\Gamma\) and a formula \(\varphi\). \(\Gamma \vdash \varphi\) if \(\Gamma \models \varphi\).
Theorem 7.1 (Completeness) Given a set of formulas \(\Gamma\) and a formula \(\varphi\), if \(\Gamma \models \varphi\), then \(\Gamma \vdash \varphi\).
We take an indirect route to the theorem. In particular, we set out to establish:
Proposition 7.1 If a set of formulas \(\Gamma\) is consistent, then \(\Gamma\) is satisfiable.
That will suffice for our purposes. For given a set of formulas \(\Gamma\) and a formula \(\varphi\), if \(\Gamma \nvdash \varphi\), then by proposition 3.6, \(\Gamma, \neg \varphi\) is consistent. Given the link between consistency and satisfiability, we would infer that \(\Gamma, \neg \varphi\) is satisfiable, whence \(\Gamma \not \models \varphi\).
We procced in two steps:
\[ \begin{array}{clllc} \Gamma \ \text{consistent} & & & & \Gamma \ \text{satisfiable}\\ \Downarrow & & & & \Uparrow \\ \exists \Sigma \ (\Gamma \subseteq \Sigma \wedge \Sigma \ \text{maxcon}) & & \Rightarrow & & \exists \Sigma \ (\Gamma \subseteq \Sigma \wedge \Sigma \ \text{satisfiable})\\ \end{array} \]
One step enables us to move from the consistency of a set \(\Gamma\) to the existence of a maximal consistent extension \(\Sigma\) of that set.
Theorem 7.2 (Lindenbaum Lemma) Each consistent set \(\Gamma\) is a subset of a maximal consistent set of formulas \(\Sigma\).
Proof. We begin with an enumeration of the formulas of propositional logic: \[ \varphi_0, \varphi_1, \cdots, \varphi_n, \cdots \] Given \(\Gamma\) be a consistent set of formulas, we build a maximal consistent superset \(\Sigma\) by the recursion: \[ \begin{array}{lll} \Sigma_0 & = & \Gamma \\ \Sigma_{n+1} & = & \begin{cases} \Sigma_n, \varphi_n & \text{if that set is consistent}\\ \Sigma_n & \text{otherwise} \end{cases} \end{array} \] We let \[ \Sigma = \bigcup_{n\in \mathbb{N}} \Sigma_n. \] We now argue that \(\Sigma\) is a maximal consistent superset of \(\Gamma\). We proceed in several steps.
Lemma 7.1 \(\Gamma \subseteq \Sigma\)
This is because \(\Gamma = \Sigma_0\) and \(\Sigma_0 \subseteq \Sigma\).
Lemma 7.2 For each natural number \(n\), \(\Gamma_n\) is consistent.
Proof. A simple induction on \(n\):
\(\Sigma_0\) is consistent on the assumption \(\Gamma\) is consistent.
If \(\Sigma_n\) is consistent, then \(\Sigma_{n+1}\) is \(\Sigma_n, \varphi_n\) if consistent, or else \(\Sigma_n\). Either way, \(\Sigma_{n+1}\) is consistent.
Lemma 7.3 For each natural number \(n\), for every \(m < n\), \(\Sigma_m \subseteq \Sigma_n\).
Proof. A simple induction on \(n\):
\(\Sigma_0\) is vacuously a superset of any predecessors in the sequence.
\(\Sigma_{n+1}\) is \(\Sigma_n, \varphi_n\) if consistent, or else \(\Sigma_n\). Either way, since by inductive hypothesis, for every \(m < n\) \(\Sigma_{m} \subseteq \Sigma_{n}\) and \(\Sigma_n \subseteq \Sigma_{n+1}\), we conclude that for every \(m < n\) \(\Sigma_{m} \subseteq \Sigma_{n+1}\).
Lemma 7.4 For every finite subset \(\Delta \subseteq \Sigma\), there is some natural number \(n\) such that \(\Delta \subseteq \Sigma_n\).
Proof. If \(\Delta\) is a finite subset of \(\Sigma\), then let \(\varphi_n\) be the member of \(\Delta\) of highest index. That is for all \(m\), if \(\varphi_m \in \Delta\), then \(m \leq n\). Notice that for each natural number \(m\), if \(\varphi_m \in \Sigma\), then \(\varphi_m \in \Sigma_{m+1}\). That is, a formula \(\varphi_m\) is accepted into \(\Sigma\) via \(\Sigma_{m+1}\) if at all. So, it follows that \(\Delta \subseteq \Sigma_{n+1}\) if \(n\) is the highest index of a formula in \(\Delta\).
Lemma 7.5 \(\Sigma\) is consistent.
Proof. It follows from the preceding lemmas that every finite subset of \(\Sigma\) is consistent. We now argue that \(\Sigma\) is consistent as well.
For a reductio, suppose \(\Sigma \vdash \bot\). That means that there is a finite derivation \((\chi_1, \dots, \chi_n)\) of \(\bot\) from \(\Sigma\). That is therefore a derivation of \(\bot\) from a finite subset of \(\Sigma\), which would require a finite subset of \(\Sigma\) to be inconsistent. That contradicts the observation that every finite subset of \(\Sigma\) is consistent.
Lemma 7.6 Given a formula \(\varphi\), if \(\Sigma, \varphi\) is consistent, then \(\varphi \in \Sigma\).
Proof. A formula \(\varphi\) will be assigned an index by the enumeration, which means \(\varphi = \varphi_n\). Now, if \(\Sigma, \varphi_n\) is consistent, then \(\Sigma_n, \varphi_n\) will be consistent as well. But that means that by construction of \(\Sigma\), \(\varphi_n \in \Sigma_{n+1} \subseteq \Sigma\).
We conclude that \(\Sigma\) is a maximal consistent superset of \(\Gamma\).
The interest of this observation is that every maximal consistent set \(\Sigma\) is satisfiable.
Theorem 7.3 (Henkin Lemma) Every maximal consistent set \(\Sigma\) is satisfiable.
Proof. Given a maximal consistent set \(\Sigma\), consider a valuation \(V\) based on an assignment \(v\) such that:
\[
\begin{array}{lll}
v(p_n) = 1 & \text{iff} & p_n \in \Sigma.
\end{array}
\]
We use an induction on the complexity of \(\varphi\) to establish:
\[
\begin{array}{lll}
V(\varphi) = 1 & \text{iff} & \varphi \in \Sigma.
\end{array}
\]
- Base Case:
\[
\begin{array}{llll}
V(p_n) = 1 & \text{iff} & v(p_n) = 1 & \\
& \text{iff} & p_n \in \Sigma. & \text{definition of} \ v
\end{array}
\]
- Inductive Step for \(\neg\):
\[
\begin{array}{llll}
V(\neg \varphi) = 1 & \text{iff} & V(\varphi) = 0 & \\
& \text{iff} & \varphi \notin \Sigma & \text{Inductive Hypothesis} \\
& \text{iff} & \neg \varphi \in \Sigma & \text{Proposition 3.7, 2} \\
\end{array}
\]
- Inductive Step for \(\to\):
\[
\begin{array}{llll}
V(\varphi \to \psi) = 1 & \text{iff} & V(\varphi) = 0 \ \text{or} \ V(\psi) =1 & \\
& \text{iff} & \varphi \notin \Sigma \ \text{or} \ \psi \in \Sigma& \text{Inductive Hypothesis} \\
& \text{iff} & \varphi \to \psi \in \Sigma & \text{Proposition 3.7, 3} \\
\end{array}
\]
We conclude that \(V\) verifies exactly those formulas in \(\Sigma\). So, it follows that \(\Sigma\) is satisfiable.