7 Completeness

We want to show that the deductive system is complete, that is, that given a set of formulas $Γ$ and a formula $φ$ . $Γ ⊢ φ$ if $Γ ⊨ φ$ .

Theorem 7.1 (Completeness) Given a set of formulas $Γ$ and a formula $φ$ , if $Γ ⊨ φ$ , then $Γ ⊢ φ$ .

We take an indirect route to the theorem. In particular, we set out to establish:

Proposition 7.1 If a set of formulas $Γ$ is consistent, then $Γ$ is satisfiable.

That will suffice for our purposes. For given a set of formulas $Γ$ and a formula $φ$ , if $Γ ⊬ φ$ , then by proposition 3.6, $Γ, \neg φ$ is consistent. Given the link between consistency and satisfiability, we would infer that $Γ, \neg φ$ is satisfiable, whence $Γ ⊭ φ$ .

We procced in two steps:

$\begin{array}{clllc} Γ consistent & Γ satisfiable \\ ⇓ & ⇑ \\ \exists Σ (Γ \subseteq Σ \land Σ maxcon) & \Rightarrow & \exists Σ (Γ \subseteq Σ \land Σ satisfiable) \end{array}$

One step enables us to move from the consistency of a set $Γ$ to the existence of a maximal consistent extension $Σ$ of that set.

Theorem 7.2 (Lindenbaum Lemma) Each consistent set $Γ$ is a subset of a maximal consistent set of formulas $Σ$ .

Proof. We begin with an enumeration of the formulas of propositional logic: $φ_{0}, φ_{1}, \dots, φ_{n}, \dots$ Given $Γ$ be a consistent set of formulas, we build a maximal consistent superset $Σ$ by the recursion: $\begin{array}{lll} Σ_{0} & = & Γ \\ Σ_{n + 1} & = & {\begin{cases} Σ_{n}, φ_{n} & if that set is consistent \\ Σ_{n} & otherwise \end{cases} \end{array}$ We let $Σ = ⋃_{n \in N} Σ_{n} .$ We now argue that $Σ$ is a maximal consistent superset of $Γ$ . We proceed in several steps.

Lemma 7.1 $Γ \subseteq Σ$

This is because $Γ = Σ_{0}$ and $Σ_{0} \subseteq Σ$ .

Lemma 7.2 For each natural number $n$ , $Γ_{n}$ is consistent.

Proof. A simple induction on $n$ :

$Σ_{0}$ is consistent on the assumption $Γ$ is consistent.
If $Σ_{n}$ is consistent, then $Σ_{n + 1}$ is $Σ_{n}, φ_{n}$ if consistent, or else $Σ_{n}$ . Either way, $Σ_{n + 1}$ is consistent.

Lemma 7.3 For each natural number $n$ , for every $m < n$ , $Σ_{m} \subseteq Σ_{n}$ .

Proof. A simple induction on $n$ :

$Σ_{0}$ is vacuously a superset of any predecessors in the sequence.
$Σ_{n + 1}$ is $Σ_{n}, φ_{n}$ if consistent, or else $Σ_{n}$ . Either way, since by inductive hypothesis, for every $m < n$ $Σ_{m} \subseteq Σ_{n}$ and $Σ_{n} \subseteq Σ_{n + 1}$ , we conclude that for every $m < n$ $Σ_{m} \subseteq Σ_{n + 1}$ .

Lemma 7.4 For every finite subset $Δ \subseteq Σ$ , there is some natural number $n$ such that $Δ \subseteq Σ_{n}$ .

Proof. If $Δ$ is a finite subset of $Σ$ , then let $φ_{n}$ be the member of $Δ$ of highest index. That is for all $m$ , if $φ_{m} \in Δ$ , then $m \leq n$ . Notice that for each natural number $m$ , if $φ_{m} \in Σ$ , then $φ_{m} \in Σ_{m + 1}$ . That is, a formula $φ_{m}$ is accepted into $Σ$ via $Σ_{m + 1}$ if at all. So, it follows that $Δ \subseteq Σ_{n + 1}$ if $n$ is the highest index of a formula in $Δ$ .

Lemma 7.5 $Σ$ is consistent.

Proof. It follows from the preceding lemmas that every finite subset of $Σ$ is consistent. We now argue that $Σ$ is consistent as well.

For a reductio, suppose $Σ ⊢ ⊥$ . That means that there is a finite derivation $(χ_{1}, \dots, χ_{n})$ of $⊥$ from $Σ$ . That is therefore a derivation of $⊥$ from a finite subset of $Σ$ , which would require a finite subset of $Σ$ to be inconsistent. That contradicts the observation that every finite subset of $Σ$ is consistent.

Lemma 7.6 Given a formula $φ$ , if $Σ, φ$ is consistent, then $φ \in Σ$ .

Proof. A formula $φ$ will be assigned an index by the enumeration, which means $φ = φ_{n}$ . Now, if $Σ, φ_{n}$ is consistent, then $Σ_{n}, φ_{n}$ will be consistent as well. But that means that by construction of $Σ$ , $φ_{n} \in Σ_{n + 1} \subseteq Σ$ .

We conclude that $Σ$ is a maximal consistent superset of $Γ$ .

The interest of this observation is that every maximal consistent set $Σ$ is satisfiable.

Theorem 7.3 (Henkin Lemma) Every maximal consistent set $Σ$ is satisfiable.

Proof. Given a maximal consistent set $Σ$ , consider a valuation $V$ based on an assignment $v$ such that: $\begin{array}{lll} v (p_{n}) = 1 & iff & p_{n} \in Σ . \end{array}$ We use an induction on the complexity of $φ$ to establish:
$\begin{array}{lll} V (φ) = 1 & iff & φ \in Σ . \end{array}$
- Base Case:

$\begin{array}{llll} V (p_{n}) = 1 & iff & v (p_{n}) = 1 \\ iff & p_{n} \in Σ . & definition of v \end{array}$
- Inductive Step for $\neg$ :

$\begin{array}{llll} V (\neg φ) = 1 & iff & V (φ) = 0 \\ iff & φ \notin Σ & Inductive Hypothesis \\ iff & \neg φ \in Σ & Proposition 3.7, 2 \end{array}$
- Inductive Step for $\to$ :

$\begin{array}{llll} V (φ \to ψ) = 1 & iff & V (φ) = 0 or V (ψ) = 1 \\ iff & φ \notin Σ or ψ \in Σ & Inductive Hypothesis \\ iff & φ \to ψ \in Σ & Proposition 3.7, 3 \end{array}$
We conclude that $V$ verifies exactly those formulas in $Σ$ . So, it follows that $Σ$ is satisfiable.