The Completeness Theorem — Read

Introduction

The completeness theorem is one of the most fundamental results about logic. It comes in two formulations, the equivalence of which we'll prove. In its first formulation it says something fundamental about the relationship between semantic consequence and our derivation system: if a sentence $!A$source 19 follows from some sentences $\Gamma$source 20, then there is also a derivation that establishes $\Gamma \Proves !A$source 20. Thus, the derivation system is as strong as it can possibly be without proving things that don't actually follow.

In its second formulation, it can be stated as a model existence result: every consistent set of sentences is satisfiable. Consistency is a proof-theoretic notion: it says that our derivation system is unable to produce certain derivations. But who's to say that just because there are no derivations of a certain sort from $\Gamma$source 29, it's guaranteed that there is a valuation $\pAssign{v}$source 30 with $\pSat{v}{\Gamma}$source 31? Before the completeness theorem was first proved—in fact before we had the derivation systems we now do—the great German mathematician David Hilbert held the view that consistency of mathematical theories guarantees the existence of the objects they are about. He put it as follows in a letter to Gottlob Frege:

If the arbitrarily given axioms do not contradict one another with all their consequences, then they are true and the things defined by the axioms exist. This is for me the criterion of truth and existence.

Frege vehemently disagreed. The second formulation of the completeness theorem shows that Hilbert was right in at least the sense that if the axioms are consistent, then some valuation exists that makes them all true.

These aren't the only reasons the completeness theorem—or rather, its proof—is important. It has a number of important consequences, some of which we'll discuss separately. For instance, since any derivation that shows $\Gamma \Proves !A$source 52 is finite and so can only use finitely many of the sentences in $\Gamma$source 53, it follows by the completeness theorem that if $!A$source 54 is a consequence of $\Gamma$source 54, it is already a consequence of a finite subset of $\Gamma$source 55. This is called compactness. Equivalently, if every finite subset of $\Gamma$source 57 is consistent, then $\Gamma$source 57 itself must be consistent.

Although the compactness theorem follows from the completeness theorem via the detour through derivations, it is also possible to use the the proof of the completeness theorem to establish it directly. For what the proof does is take a set of sentences with a certain property—consistency—and constructs a structure out of this set that has certain properties (in this case, that it satisfies the set). Almost the very same construction can be used to directly establish compactness, by starting from “finitely satisfiable” sets of sentences instead of consistent ones.

Outline of the Proof

The proof of the completeness theorem is a bit complex, and upon first reading it, it is easy to get lost. So let us outline the proof. The first step is a shift of perspective, that allows us to see a route to a proof. When completeness is thought of as “whenever $\Gamma \Entails !A$source 18 then $\Gamma \Proves !A$source 19,” it may be hard to even come up with an idea: for to show that $\Gamma \Proves !A$source 20 we have to find a derivation, and it does not look like the hypothesis that $\Gamma \Entails !A$source 22 helps us for this in any way. For some proof systems it is possible to directly construct a derivation, but we will take a slightly different approach. The shift in perspective required is this: completeness can also be formulated as: “if $\Gamma$source 26 is consistent, it is satisfiable.” Perhaps we can use the information in $\Gamma$source 27 together with the hypothesis that it is consistent to construct a valuation that satisfies every formula in $\Gamma$source 30. After all, we know what kind of valuation we are looking for: one that is as $\Gamma$source 32 describes it!

If $\Gamma$source 34 contains only propositional variables, it is easy to construct a model for it. All we have to do is come up with

a valuation $\pAssign{v}$source 46 such that $\pSat{v}{p}$source 46 for all $p \in \Gamma$source 46. Well, let $\pAssign{v}(p) = \True$source 47 iff $p \in \Gamma$source 47.

Now suppose $\Gamma$source 49 contains some formula $\lnot !B$source 49, with $!B$source 49 atomic. We might worry that the construction of $\pAssign{v}$source 51 interferes with the possibility of making $\lnot !B$source 52 true. But here's where the consistency of $\Gamma$source 53 comes in: if $\lnot !B \in \Gamma$source 53, then $!B \notin \Gamma$source 53, or else $\Gamma$source 54 would be inconsistent. And if $!B \notin \Gamma$source 54, then according to our construction of $\pAssign{v}$source 56, $\pSat/{v}{!B}$source 57, so $\pSat{v}{\lnot !B}$source 58. So far so good.

What if $\Gamma$source 60 contains complex, non-atomic formulas? Say it contains $!A \land !B$source 61. To make that true, we should proceed as if both $!A$source 62 and $!B$source 62 were in $\Gamma$source 62. And if $!A \lor !B \in \Gamma$source 62, then we will have to make at least one of them true, i.e., proceed as if one of them was in $\Gamma$source 64.

This suggests the following idea: we add additional formulas to $\Gamma$source 67 so as to (a) keep the resulting set consistent and (b) make sure that for every possible atomic sentence $!A$source 68, either $!A$source 69 is in the resulting set, or $\lnot !A$source 69 is, and (c) such that, whenever $!A \land !B$source 70 is in the set, so are both $!A$source 70 and $!B$source 70, if $!A \lor !B$source 71 is in the set, at least one of $!A$source 71 or $!B$source 71 is also, etc. We keep doing this (potentially forever). Call the set of all formulas so added $\Gamma^*$source 73. Then our construction above would provide us with a valuation $\pAssign{v}$source 74 for which we could prove, by induction, that it satisfies all sentences in $\Gamma^*$source 76, and hence also all sentence in $\Gamma$source 76 since $\Gamma \subseteq \Gamma^*$source 77. It turns out that guaranteeing (a) and (b) is enough. A set of sentences for which (b) holds is called complete. So our task will be to extend the consistent set $\Gamma$source 80 to a consistent and complete set $\Gamma^*$source 80.

So here's what we'll do. First we investigate the properties of complete consistent sets, in particular we prove that a complete consistent set contains $!A \land !B$source 137 iff it contains both $!A$source 138 and $!B$source 138, $!A \lor !B$source 138 iff it contains at least one of them, etc. (the proposition about complete consistent sets). We'll then take the consistent set $\Gamma$source 151 and show that it can be extended to a consistent and complete set $\Gamma^*$source 153 (Lindenbaum's Lemma). This set $\Gamma^*$source 154 is what we'll use to define our valuation $\pAssign v(\Gamma^*)$source 155. The valuation is determined by the propositional variables in $\Gamma^*$source 159 (the canonical valuation definition). We'll use the properties of complete consistent sets to show that indeed $\pSat{v(\Gamma^*)}{!A}$source 162 iff $!A \in \Gamma^*$source 162 (the Truth Lemma), and thus in particular, $\pSat{v(\Gamma^*)}{\Gamma}$source 164.

Complete Consistent Sets of sentence

In what follows, we will often tacitly use the properties of reflexivity, monotonicity, and transitivity of $\Proves$source 55 (see

the proof-theoretic notions section for sequent calculus, the proof-theoretic notions section for natural deduction, the proof-theoretic notions section for axiomatic derivation, the proof-theoretic notions section for tableaux).

Lindenbaum's Lemma

Construction of a Model

Reader correction SAR-002: Editorial projection note: the source omits an empty non-first-order alternative at this conditional boundary. This edition restores the boundary, so first-order-only material appears only in the first-order chapter; the canonical source is unchanged.

The Completeness Theorem

The Compactness Theorem

One important consequence of the completeness theorem is the compactness theorem. The compactness theorem states that if each finite subset of a set of sentences is satisfiable, the entire set is satisfiable—even if the set itself is infinite. This is far from obvious. There is nothing that seems to rule out, at first glance at least, the possibility of there being infinite sets of sentences which are contradictory, but the contradiction only arises, so to speak, from the infinite number. The compactness theorem says that such a scenario can be ruled out: there are no unsatisfiable infinite sets of sentences each finite subset of which is satisfiable. Like the completeness theorem, it has a version related to entailment: if an infinite set of sentences entails something, already a finite subset does.

A Direct Proof of the Compactness Theorem

We can prove the Compactness Theorem directly, without appealing to the Completeness Theorem, using the same ideas as in the proof of the completeness theorem. In the proof of the Completeness Theorem we started with a consistent set $\Gamma$source 18 of sentences, expanded it to a consistent and complete set $\Gamma^*$source 20 of sentences, and then showed that in the valuation $\pAssign{v(\Gamma^*)}$source 22 constructed from $\Gamma^*$source 23, all sentences of $\Gamma$source 23 are true, so $\Gamma$source 24 is satisfiable.

We can use the same method to show that a finitely satisfiable set of sentences is satisfiable. We just have to prove the corresponding versions of the results leading to the truth lemma where we replace “consistent” with “finitely satisfiable.”