3Completeness

In this chapter, we’re going to meet some important results about the powers and limitations of first-order logic. Our starting point is the completeness theorem, which shows that whenever a first-order sentence is entailed by some premises then it is derivable from these premises in the first-order calculus. We’ll see that this positive result is tightly connected to some negative results: the compactness theorem and the Löwenheim-Skolem theorems. These theorems concern the size of models, by which we mean the size of their domain. To fully appreciate their implications, I’ll begin with some background about the sizes of sets, which will be needed in later chapters anyway.

3.1Cardinalities

\(\{\) Athens \(\}\) is a set with one member: the city Athens. We say that \(\{\) Athens \(\}\) has size 1. \(\{\) Athens, Berlin \(\}\) has size 2. \(\{\) Athens, Berlin, Cairo \(\}\) has size 3. And so on. It seems straightforward. But now consider the set \(\mathbb {N} = \{ 0, 1, 2, 3, \ldots \}\) of natural numbers. What is its size?

The official set-theoretic word for the size of a set is cardinality. So \(\{\) Athens, Berlin, Cairo \(\}\) has cardinality 3. Finite sets have finite cardinalities, which are natural numbers. But infinite sets also have a cardinality. These aren’t natural numbers, but numbers of a more general sort, called cardinals. The infinite cardinals are also known as the alephs, because they are conventionally written using the Hebrew letter ‘\(\aleph \)’ (“aleph”). For example, the cardinality of \(\mathbb {N}\) is called ‘\(\aleph _0\)’. This is the smallest infinite cardinal. The next larger one is \(\aleph _1\), followed by \(\aleph _2\), and so on.

How do we determine the cardinality of an infinite set? The crucial idea goes back to Galileo and Hume, but was only fully developed by Georg Cantor in the 19th century. Following Galileo and Hume, Cantor stipulates that two sets have the same cardinality iff there is a one-to-one correspondence between their members.

To make this precise, we define the notion of a one-to-one correspondence, or bijection.

Intuitively, a bijection pairs up each element of \(A\) with exactly one element of \(B\), and vice versa, so that every element of either set gets a unique partner. As a shorthand, we say that sets \(A\) and \(B\) are equinumerous if there is a bijection from \(A\) to \(B\). (In this case, there is always also a bijection from \(B\) to \(A\).)

The Galileo-Hume-Cantor principle now says that two sets have the same cardinality iff they are equinumerous. Obviously, no finite set of numbers is equinumerous with \(\mathbb {N}\). So \(\mathbb {N}\) has an infinite cardinality. We define ‘\(\aleph _0\)’ to name this cardinality. Using the Galileo-Hume-Cantor principle, we can determine, for any other set, whether it also has cardinality \(\aleph _0\).

Consider, for example, the set of odd numbers \(1, 3, 5, 7, \ldots \). The following function \(f\) is a bijection from \(\mathbb {N}\) to the set of odd numbers: \[ f(n) = 2n + 1. \] The function maps 0 to 1, 1 to 3, 2 to 5, and so on. Every natural number is mapped to a unique odd number, and no odd number is left unmapped. So the set of odd numbers also has cardinality \(\aleph _0\).

Galileo found this paradoxical: how can there be as many odd numbers as natural numbers, given that the odd numbers are a proper subset of the natural numbers? Never mind, said Cantor: the resulting theory of cardinalities is consistent and mathematically fruitful, even if it may initially seem strange.

Sets that are equinumerous with \(\mathbb {N}\) are also called countably infinite or denumerable. A set is countable if it is either finite or countably infinite. The word ‘countable’ alludes to the fact that a bijection between \(\mathbb {N}\) and another set effectively assigns a “counter” to each member of the set. For example, the above bijection between \(\mathbb {N}\) and the odd numbers assigns the counter 0 to 1, 1 to 3, 2 to 5, and so on.

Are there any uncountable sets? One might suspect that the set of pairs of natural numbers is uncountable. But not so. Cantor’s zig-zag method shows that there is a bijection between \(\mathbb {N}\) and the set of pairs of natural numbers. We begin by arranging all pairs of natural numbers in a two-dimensional grid.

We then define a path through this grid that visits each cell exactly once. The orange arrows indicate that path. It effectively enumerates all pairs \(\langle x, y \rangle \), starting with \(\langle 0,0 \rangle \), followed by \(\langle 0,1 \rangle \), \(\langle 1,0 \rangle \), \(\langle 2,0 \rangle \), \(\langle 1,1 \rangle \), \(\langle 0,2 \rangle \), and so on. The enumeration amounts to a lists of all the pairs. We get a bijection to \(\mathbb {N}\) by assigning to each pair its position in the list, starting with position 0. So \(\langle 0,0 \rangle \) is mapped to 0, \(\langle 0,1 \rangle \) to 1, \(\langle 1,0 \rangle \) to 2, and so forth.

(We can find a formula for this bijection. As we follow the arrow, the pairs before any given pair \(\langle x,y \rangle \) comprise all the pairs on the left-to-top diagonals before \(\langle x,y \rangle \), which have 1, 2, 3, etc. pairs, plus the \(y\) pairs on the diagonal containing \(\langle x,y \rangle \) itself. The total number of pairs preceding \(\langle x,y \rangle \) is therefore \((1 + 2 + \ldots + (x+y)) + y\). In exercise 1.3, you showed that \(1+2+ \ldots + (x+y) = (x + y)(x + y + 1)/2\). So the position of any pair \(\langle x,y \rangle \) in the enumeration is \((x+y)(x+y+1)/2 + y\).)

But it’s true that not all sets are countable. Cantor established this with another powerful technique: diagonalization.

We can again picture this technique with a two-dimensional grid.

Each row represents a set of natural numbers. Each column stands for a number. A checkmark indicates that the number is in the set, a cross that it is not. (So \(0\) is in \(S_0\), \(1\) is not in \(S_0\), 2 is not in \(S_{0}\), and so on.) Cantor’s method now looks at the shaded diagonal. It defines the new set \(D\) by inverting the diagonal, swapping crosses and checkmarks. In the picture, the inverted diagonal would begin with ✗✓✗✗✓…, meaning that \(D\) does not contain \(0\), does contain 1, does not contain 2 and 3, does contain 4, and so on. The so-defined set \(D\) is called the antidiagonal of the grid. It can’t be anywhere in the list \(S_0, S_1, S_2, \ldots \). So there can be no list of all sets of natural numbers.

Theorem 3.1 can be strengthened:

Cantor’s theorem reveals a hierarchy of infinities. Starting with \(\mathbb {N}\), we can produce larger and larger infinities by taking power sets: \(\mathcal {P}(\mathbb {N})\) is larger than \(\mathbb {N}\), \(\mathcal {P}(\mathcal {P}(\mathbb {N}))\) is even larger, \(\mathcal {P}(\mathcal {P}(\mathcal {P}(\mathbb {N})))\) is larger than that, and so on, without end. There are infinitely many infinite cardinals.

3.2Planning the completeness proof

In section 1.4, we showed that all valid sentences in propositional logic are derivable from the axiom schemata A1–A3 by Modus Ponens. This particular result wasn’t easy to foresee, but it wasn’t a surprise that there is some mechanical way of checking if a sentence of propositional logic is valid. Models of propositional logic are essentially finitary. A model is a truth-value assignment to the sentence letters. Since each sentence of propositional logic is composed of finitely many sentence letters, and there are only finitely many ways of assigning truth-values to these sentence letters, it is to be expected that there is a finitary algorithm for deciding whether all of these assignments make the sentence true.

In first-order logic, the situation is very different. A first-order model consists of an arbitrary set \(D\) together with an interpretation of the non-logical vocabulary, where every subset of \(D\) is a possible interpretation of any monadic predicate. Even if \(D\) itself is countable, this means that there are usually uncountably many models with that domain. And \(D\) doesn’t have to be countable. It can have any cardinality whatsoever. The space of first-order models is enormous. The number of first-order models is vastly greater than \(\aleph _0\). There is, in fact, no aleph big enough to measure the number of first-order models. It is therefore astonishing that there is a finitary, mechanical method – a proof system – by which one can find every sentence that is true across the realm of all first-order models. Astonishing, but true – as Kurt Gödel showed in 1929.

Gödel’s completeness theorem (not to be confused with his incompleteness theorems that we’ll discuss in later chapters) is noteworthy for other reasons as well. For example, it supports the hypothesis that all intuitively valid mathematical arguments can be formalized as deductions in the first-order calculus. Let’s grant, for the sake of the argument, that every mathematical statement can be expressed in a first-order language. Now suppose some mathematical argument can’t be replicated in the first-order calculus. By the completeness theorem, it follows that there is a model in which the premises are true but the conclusion false. This strongly suggests that the argument wasn’t valid. We’ll meet further applications of the completeness theorem later. First we need to prove it.

Our proof will follow Henkin’s 1949 method, which we used in chapter 1 to prove the completeness of propositional logic. Let’s recall the key steps.

We want to show that whenever a sentence \(A\) is entailed by a set of sentences \(\Gamma \) (meaning that every model that makes all members of \(\Gamma \) true also makes \(A\) true), then there is a deduction of \(A\) from \(\Gamma \). For short: if \(\Gamma \vDash A\) then \(\Gamma \vdash A\). The proof is by contraposition. We assume \(\Gamma \not \vdash A\) and derive \(\Gamma \not \vDash A\), as follows.

1.

Assume \(\Gamma \not \vdash A\).

2.

Infer that \(\Gamma \cup \{ \neg A \}\) is consistent.

3.

Show that \(\Gamma \cup \{ \neg A \}\) can be extended to a maximal consistent set \(\Gamma ^{+}\).

4.

Construct a model \(\mathfrak {M}\) based on \(\Gamma ^{+}\) in which all members of \(\Gamma ^{+}\) are true.

5.

Infer that \(\Gamma \not \vDash A\).

As in chapter 1, we call a set of sentences consistent if no contradiction can be derived from it. That is, \(\Gamma \) is consistent iff there is no sentence \(A\) such that \(\Gamma \vdash A\) and \(\Gamma \vdash \neg A\). Equivalently (as you showed in exercise 1.8; the proof carries over from propositional logic), \(\Gamma \) is consistent iff \(\Gamma \not \vdash \bot \).

Steps 2 and 5 are easy. The following lemma establishes step 2, and is proved just as its propositional counterpart, lemma 1.2.

It remains to fill in steps 3 and 4: we need to show that every consistent set of sentences is satisfiable.

Here is the plan. Let \(\Gamma \) be a consistent set of sentences in some first-order language \(\mathfrak {L}\) (with identity and function symbols). We’ll show how one can construct a model \(\mathfrak {M}\) in which all members of \(\Gamma \) are true. As in chapter 1, we first extend \(\Gamma \) to a maximal consistent set \(\Gamma ^{+}\) that will guide the construction of the model. For example, if \(\Gamma \) contains \(Fa \lor Gb\), it’s not obvious if our model should satisfy \(Fa\) or \(Gb\) or both. \(\Gamma ^{+}\) will directly contain \(Fa\) or \(Gb\) or both, so it will answer this question.

Suppose we have \(Fa\) in \(\Gamma ^{+}\). Our model \(\mathfrak {M}\) must then contain an object \(⟦ a⟧^{\mathfrak {M}}\) denoted by \(a\) that falls in the extension \(⟦ F ⟧^{\mathfrak {M}}\) of \(F\). The nature of the object \(⟦ a⟧^{\mathfrak {M}}\) is irrelevant. It proves useful to choose the individual constant \(a\) as the object denoted by \(a\). Then we can say that the extension of \(F\) comprises all individual constants \(c\) for which \(Fc \in \Gamma ^{+}\). (It might seem odd to have a model whose domain consists of individual constants, and in which each constant denotes itself. But nothing in the definition of a first-order model prevents us from doing this.)

Unfortunately, there are some complications. Suppose \(\Gamma \) contains \(\exists x Fx\) (which is short for \(\neg \forall x \neg Fx\)). We want all sentences in \(\Gamma \) to be true in our model \(\mathfrak {M}\). So there must be some object in \(⟦ F ⟧^{\mathfrak {M}}\). But if \(⟦ F ⟧^{\mathfrak {M}}\) is defined as the set of individual constants \(c\) for which \(Fc \in \Gamma ^{+}\), there might be no such object, as there might be no constant \(c\) for which \(Fc \in \Gamma ^{+}\). We need to ensure that this doesn’t happen. That is, we need to ensure that for each existential sentence \(\exists x Fx\) in \(\Gamma ^{+}\), there is a “witnessing” sentence \(Fc\) in \(\Gamma ^{+}\). But what if \(\Gamma \) already contains \(\neg Fc\) for every individual constant \(c\)? Then we can’t add the required witness without making \(\Gamma \) inconsistent.

To get around this problem, we’ll construct \(\Gamma ^{+}\) in an extend language \(\mathfrak {L}^{+}\) that adds new individual constants to \(\mathfrak {L}\). We can use these constants to ensure that every existential sentence in \(\Gamma \) has a witness.

Another complication arises from the presence of the identity symbol. If we let each individual constant denote itself, any identity statement involving different individual constants will be false. After all, no constant is identical to any other constant. But \(a=b\) is consistent, and might be in \(\Gamma \) and therefore in \(\Gamma ^{+}\). So we’ll actually let each constant denote a set of terms: the constant \(a\) will denote the set of closed terms \(t\) for which \(a=t\) is in \(\Gamma ^{+}\).

Let’s fill in the details.

3.3The completeness proof

We’ll show that every consistent set of first-order sentences is satisfiable. As we’ve seen above (and as we’ll spell out again below), from this it is only a small step to the completeness theorem.

So let \(\Gamma \) be a consistent set of sentences in a first-order language \(\mathfrak {L}\). Let \(\mathfrak {L}^{+}\) be an extension of \(\mathfrak {L}\) with (countably) infinitely many new individual constants. We’ll extend \(\Gamma \) to a maximal consistent set in \(\mathfrak {L}^{+}\). First, though, we need to confirm that \(\Gamma \) itself is still consistent in the extended language \(\mathfrak {L}^{+}\). Consistency is language-relative because the language determines which instances of the axioms are available. As we switch from \(\mathfrak {L}\) to \(\mathfrak {L}^{+}\), new axioms become available. We need to confirm that these new axioms don’t allow deriving a contradiction from \(\Gamma \).

Next, we show that \(\Gamma \) can be extended to a maximal consistent set \(\Gamma ^{+}\) in which every existential sentence \(\exists x A\) has a witness \(A(x/c)\). Such sets are called Henkin sets.

In the presence of the other conditions, (iii) is equivalent to the requirement that if \(\Gamma \) contains \(\neg \forall x \neg A\) then it contains \(A(x/c)\) for some \(c\).

Next, we show how to read off a model from a Henkin set. The model’s domain will consist of sets of closed terms, so that we can stipulate that each constant \(c\) denotes the set of all terms \(t\) for which \(c=t\) is in the Henkin set. Let’s have a closer look at these sets.

An equivalence relation partitions the domain over which it is defined into distinct cells so that within each cell, all objects stand in the relation to one another. These cells are called equivalence classes. If \(R\) is an equivalence relation and \(x\) an object in the domain, we write ‘\([x]_{R}\)’ for the equivalence class of \(R\) that contains \(x\). That is, \([x]_{R} = \{ y \in D \,:\, x R y \}\). If the relation \(R\) is clear from the context, we may simply write ‘\([x]\)’.

When we’re talking about a Henkin set \(\Gamma \), the relevant equivalence relation is the one defined in lemma 3.4. In what follows, ‘\([t]\)’ therefore denotes the set of all terms \(s\) for which \(t=s \in \Gamma \).

The model \(\mathfrak {M}\) that we’ll construct from a Henkin set \(\Gamma \) will have as its domain the set of all equivalence classes \([t]\), where \(t\) is a closed term in the language of \(\Gamma \). By exercise 3.7, \([t]\) always contains an individual constant. So we can also say that \(D\) is the set of all \([c]\) where \(c\) is an individual constant in the language of \(\Gamma \).

We’ll stipulate that the interpretation function \(I\) of \(\mathfrak {M}\) assigns \([c]\) to each constant \(c\). So we’ll have \(⟦ c ⟧^{\mathfrak {M}} = [c]\). We’ll extend this to function terms, so that \(⟦ f(c) ⟧^{\mathfrak {M}} = [f(c)]\). But we can’t directly stipulate this, because interpretation functions don’t assign denotations to complex terms. We have to interpret \(f\) as denoting a function on \(D\). By definition 2.9, The denotation of \(f(c)\) is the denotation of \(f\) applied to the denotation of \(c\). Since the denotation of \(c\) is \([c]\), we want the denotation of \(f\) to be a function that returns \([f(c)]\) for input \([c]\). So we’ll stipulate that for any one-place function symbol \(f\) and constant \(c\), \(I(f)\) is the function that maps \([c]\) to \([f(c)]\). Similarly for many-place function symbols.

This kind of stipulation can go wrong. Suppose \([c]\) contains two constants \(c\) and \(d\), and \([f(c)] \neq [f(d)]\). Our stipulation would entail that \(I(f)\) returns \([f(c)]\) for input \([c]\) and \([f(d)]\) for input \([d]\). But if \(c\) and \(d\) are both in \([c]\) then \([c] = [d]\). And a function can’t return two different values for the same input. We must show that this problem can never arise.

A similar issue arises for the interpretation of predicates. To ensure that \(Ft\) is in \(\Gamma \) iff \(\mathfrak {M} \Vdash Ft\), we’ll stipulate that \(I(F)\) is the set of all \([t]\) for which \(Ft \in \Gamma \). This set isn’t well-defined if there are cases where \([t]\) contains two terms \(t\) and \(s\) for which \(Ft \in \Gamma \) but \(Fs \notin \Gamma \).

The following lemma shows that neither problem can arise.

Lemma 3.5 ensures that the following definition is legitimate.

Now remember what we’re trying to achieve. We want to show that every consistent set of sentences is satisfiable. We’ve shown in lemma 3.3 that every such set can be extended to a Henkin set. Definition 3.4 tells us how to construct a model from this Henkin set. It remains to show that all members of the Henkin set (and therefore all members of the original set) are true in this model.

We’ll need the following two facts.

With that, we have all the ingredients for the completeness proof.

Technically, the model that figures in this proof is not a model for the original language \(\mathfrak {L}\) of \(\Gamma \) and \(A\), because it also interprets the added individual constants. If this bothers you, we can define an \(\mathfrak {L}\)-model that falsifies \(\Gamma \vDash A\) by restricting the interpretation function of the Henkin model to \(\mathfrak {L}\)-constants, without changing the domain. This is called the reduct of the Henkin model to \(\mathfrak {L}\).

3.4Unintended models

We’ve now shown that the first-order calculus is both sound (theorem 2.4) and complete (theorem 3.3): \(\Gamma \vDash A\) iff \(\Gamma \vdash A\). As Gödel pointed out, this has a curious consequence:

Why is this curious? Well, for one, it is easy to come up with cases where a conclusion is entailed by infinitely many premises, but not by any finite subset of those premises. For example, consider the premises ‘I like the number 0’, ‘I like the number 1’, ‘I like the number 2’, and so on, for all natural numbers. Together, these premises entail ‘I like all natural numbers’. But no finite subset of the premises does. This doesn’t contradict the compactness theorem because the inference isn’t logically valid: it depends on the interpretation of ‘0’, ‘1’, ‘2’, …, and ‘natural number’. Still, it’s curious that first-order logic doesn’t allow any such inference to be valid. More directly, compactness implies that there is no way to fully pin down the interpretation of ‘0’, ‘1’, ‘2’, etc. in a first-order language. Let’s think through this more carefully.

Many branches of mathematics can be seen as studying certain mathematical structures. A mathematical structure consists of a set of objects together with some operations and relations on these objects. For example, arithmetic studies operations and relations on the natural numbers. A formalized, first-order theory of arithmetic will have nonlogical symbols for, say, addition (‘\(+\)’), multiplication (‘\(\times \)’), and the less-than relation (‘\(<\)’). We might add an individual constant ‘\(n\)’ for each number \(n\), but for the sake of economy we can instead have a single constant ‘0’ for 0 and another symbol ‘\(s\)’ for the successor function that maps each number \(n\) to its successor \(n+1\). Instead of ‘1’, we can then write ‘\(s(0)\)’; ‘2’ is ‘\(s(s(0))\)’, and so on.

In logic, we abstract away from the meaning of the nonlogical symbols. In arithmetic, we don’t. In arithmetic, ‘\(1+2=3\)’ (that is, ‘\(s(0) + s(s(0)) = s(s(s(0)))\)’) is a definite claim about the natural numbers. We say that it has an intended interpretation, or an intended model.

The intended model of arithmetic, also known as the standard model of arithmetic, or \(\mathfrak {N}\), has as its domain the set of natural numbers \(\mathbb {N}\); it interprets ‘0’ as denoting 0, ‘+’ as denoting the addition function +, ‘\(\times \)’ as denoting the multiplication function \(\times \), ‘\(s\)’ as denoting the successor function \(s\), and ‘\(<\)’ as denoting the less-than relation \(<\). We can represent this as a list: \(\langle \mathbb {N}, 0, +, \times , s, < \rangle \). The list represents the “structure” of the natural numbers. It identifies a set \(\mathbb {N}\) and some operations and relations on that set that are picked out by the nonlogical symbols of the language. (0 counts as a zero-ary operation.)

Of course, the language of arithmetic also has unintended models. For example, we can let the domain be \(\{\) Athens, Berlin \(\}\) and use an interpretation function that maps ‘0’ to Athens, ‘+’ and ‘\(\times \)’ to the function that maps any pair of cities to Athens, ‘\(s\)’ to the function that maps each city to itself, and ‘<’ to the empty relation. In this model, ‘\(s(0) + s(s(0)) = s(s(s(0)))\)’ is true, but so is ‘\(s(0) = 0\)’.

We might hope that such unintended models can always be ruled out by laying down sufficiently many postulates in the formal language of arithmetic. For example, if our theory of arithmetic contains ‘\(s(0) \ne 0\)’ then the above model (with Athens and Berlin) is no longer a model of the theory. So we can rule out some unintended models. The compactness theorem dashes any hope of ruling out all unintended models. Let \(\mathrm {Th}(\mathfrak {N})\) be the set of all sentences true in the standard model \(\mathfrak {N}\). This is called the theory of \(\mathfrak {N}\). It contains all postulates we could possibly lay down, assuming that they should all be true in the standard model. By compactness, there is a model of \(\mathrm {Th}(\mathfrak {N})\) whose domain includes junk elements that clearly aren’t natural numbers.

Compactness thus reveals a deep expressive limitation of first-order logic: the structure of the natural numbers can’t be captured in a first-order language.

Here is a simpler example of this kind of limitation. For each \(n>0\), it is easy to find a first-order sentence \(S_n\) that is true in all and only the models with exactly \(n\) elements. For example, \(\exists x \exists y (x \ne y \land \forall z (z=x \lor z=y))\) is true in all and only models with exactly two elements. (Compare exercise 2.16.) In that sense, we can capture the intended size of a domain, as long as that size is a fixed finite number. But there is no first-order sentence that is true in all and only the models with infinitely many elements.

To see why, let \(S_\infty \) be such a sentence. Its negation \(\neg S_\infty \) would be true in all and only the finite models. Now consider the set consisting of \(\neg S_\infty \) together with \(\neg S_1, \neg S_2, \neg S_3, \ldots \). All finite subsets of this set are satisfiable. By compactness, the whole set is satisfiable. But there is no model whose domain not infinite, and yet also has no finite size.

The following theorems show that the situation is even worse. In section 3.1, we saw that there are many levels of infinity: many infinite cardinalities. None of them can be captured in first-order logic, insofar as there is no sentence (nor even a set of sentences) that would force a model to have a particular infinite cardinality, or even to fall in any non-trivial range of infinite cardinalities.

The downward theorem was proved by Thoralf Skolem in 1920, building on an earlier proof sketch by Leopold Löwenheim. The (ill-named) upward theorem, due to Alfred Tarski, requires compactness and could only be proved after 1929. It entails, among other things, that \(\mathrm {Th}(\mathfrak {N})\) has non-standard models of every infinite cardinality.