. 99
( 107 .)


course, make all the sentences in this list true. Submit your world.

19.20 Give formal proofs of the following theorems about identity:
‚ 1. ∀x (x = x)

2. ∀x ∀y (x = y ’ y = x)

3. ∀x ∀y ∀x [(x = y § y = z) ’ x = z]

19.21 What are the complexities of the following w¬s, where complexity is measured as in the proof
 of the Henkin Construction Lemma?
1. Cube(y)
2. y = x
3. Cube(y) ’ y = x
4. ∀y (Cube(y) ’ y = x)
5. ∃x ∀y (Cube(y) ’ y = x)
6. y = c∀y(Cube(y)’y=x)
7. ∀y (Cube(y) ’ y = c∀y(Cube(y)’y=x) )

19.22 In the inductive proof of Lemma 13, Case 1 considered only one of the truth-functional con-
 nectives, namely, ∨. Give an analogous proof that covers the case where S is of the form P § Q.

19.23 In the inductive proof of Lemma 13, Case 3 considered only one direction of the biconditional
 for ∀. Prove the other direction.

Section 19.5
546 / Completeness and Incompleteness

Section 19.6
The L¨wenheim-Skolem Theorem
One of the most striking things about the proof of completeness is the na-
the structure Mh ture of the ¬rst-order structure Mh . Whereas our original language may be
talking about physical objects, numbers, sets, what-have-you, the ¬rst-order
structure Mh that we construct by means of the Henkin construction has as
elements something quite di¬erent: equivalence classes of constant symbols.
This observation allows us to exploit the proof to establish something known
as the L¨wenheim-Skolem Theorem for fol.
Recall from our discussion of in¬nite sets in Chapter 15 that there are
di¬erent sizes of in¬nite sets. The smallest in¬nite sets are those that have
the same size as the set of natural numbers, those that can be put in one-to-
one correspondence with the natural numbers. A set is countable if it is ¬nite
or is the same size as the set of natural numbers. Digging into the details of
the proof of completeness lets us prove the following important theorem, due
originally to the logicians L¨wenheim and Skolem. They proved it before G¨del
o o
proved the Completeness Theorem, using a very di¬erent method. L¨wenheim
proved it for single sentences, Skolem proved it for countably in¬nite sets of
Theorem (L¨wenheim-Skolem Theorem) Let T be a set of sentences in a
Theorem countable language L. Then if T is satis¬ed by any ¬rst-order structure, it is
satis¬ed by a structure whose domain is countable.

Proof: (Sketch) By the Soundness Theorem, if T is satis¬able, then
it is formally consistent. The proof of completeness shows that if
T is formally consistent, it is true in a ¬rst-order structure of the
form Mh , for some truth assignment h for LH . Let™s assume that
our original language L is countable and ask how big the structure
Mh is. The answer to this is not hard to determine. There cannot
be any more elements of Mh than there are constant symbols in the
language LH . Each of these can be written down using the symbol
c, with subscripts involving symbols from L, though the subscripts
need to be able to be iterated arbitrary far. Still, if we can list the
symbols of L in a list, we can use this list to alphabetize all the
witnessing constants of LH . In this way, it is possible to show that
the domain of the structure Mh is countable.

Chapter 19
The Lowenheim-Skolem Theorem / 547

The Skolem Paradox

The L¨wenheim-Skolem Theorem can seem somewhat puzzling. Consider, for
example, our axiomatization zfc of set theory. In giving these axioms, the
intended range of structures was not terribly clear. It was, roughly speaking,
the universe, or universes, of small cumulative sets. No such universe is count- the Skolem paradox
able, since each will contain among its sets at least one in¬nite set (by the
axiom of in¬nity) as well as the powerset of this set (by the powerset axiom).
But the powerset of an in¬nite set is uncountable. Indeed, suppose c is an
in¬nite set. We can prove in zfc that the powerset of c is uncountable. How
can it be, then, that the axioms zfc are true in a countable structure, as the
L¨wenheim-Skolem Theorem implies?
The resolution to this puzzling state of a¬airs rests in the nature of the resolution of paradox
structure we constructed in the proof of the L¨wenheim-Skolem Theorem as
applied to zfc. As we noted, it is a structure Mh built out of equivalence
classes of constant symbols. It is not at all one of the intended structures we
had in mind in axiomatizing set theory. If we look at this structure, we will
¬nd that it does contain elements which purport to be powersets of in¬nite
sets. Suppose b and c are members of the domain, where b and c satisfy the
w¬ “x is the powerset of y and y is in¬nite.” The “set” b will contain various
“elements,” each of which can be seen as corresponding to a set of “elements”
of c. (Remember that the members of the domain of Mh are really equivalence
classes of constants. When we speak of the “elements” of b, we do not mean
the members of this equivalence class, but rather the members d of the domain
such that d and b satisfy the w¬ x ∈ y in Mh . This is why we are using scare
quotes around “set,” “element,” and so forth.) But most sets of “elements”
of c will not correspond to anything in b.
Another way of understanding what is going on in Mh is to think about
the de¬nition of a countable set. An in¬nite set b is countable if there is a one-
to-one function from the set of natural numbers onto b. From outside Mh , we
can see that there is such a function enumerating b, but this function does not
correspond to anything in the structure Mh . That is, there is no “function”
in Mh that enumerates b.
The lesson to be learned from the application of the L¨wenheim-Skolem
o lesson of paradox
Theorem to zfc is that the ¬rst-order language of set theory is not rich enough
to be able to capture various concepts that we implicitly assume when thinking
about the intended universe of set theory. In fact, the key concept that we
cannot adequately express is the notion of an arbitrary subset of a set, or
what comes to the same thing, the notion of the powerset of a set. When
we de¬ne powerset in the ¬rst-order language, no ¬rst-order axioms can rule

Section 19.6
548 / Completeness and Incompleteness

out structures, like Mh , in which “powerset” means something quite di¬erent
from the intended notion. While more subtle, this is not unlike the fact that
our shape axioms do not rule out structures in which Tet, Cube, Dodec, and
SameShape mean small, medium, large, and same size.

Section 19.7
The Compactness Theorem

As we mentioned before, one of the immediate consequences of the Complete-
ness Theorem is the ¬rst-order Compactness Theorem:
Theorem (Compactness Theorem for fol) Let T be a set of sentences of a
Compactness Theorem
¬rst-order language L. If every ¬nite subset of T is true in some ¬rst-order
structure, then there is a ¬rst-order structure M that makes every sentence
of T true.
This follows from Completeness for the simple reason that proofs in F are
¬nite and so can only use ¬nitely many premises. If T is not satis¬able, then
(by Completeness) there is a proof of ⊥ from sentences in T , and this proof
can only use ¬nitely many premises from T . So that subset of T can™t be
satis¬able (by Soundness).
It turns out that this theorem, like the L¨wenheim-Skolem Theorem, shows
some important expressive limitations of fol. In particular, we can show
that it is impossible to come up with axioms in the ¬rst-order language of
arithmetic that characterize the structure of the natural numbers.
Theorem (Nonstandard models of arithmetic) Let L be the language of Peano
nonstandard models
arithmetic. There is a ¬rst-order structure M such that

1. M contains all the natural numbers in its domain,

2. M also contains elements greater than all the natural numbers, but

3. M makes true exactly the same sentences of L as are true about the
natural numbers.
Proof: (Sketch) The proof of this result is fairly easy using the
Compactness Theorem. The language of Peano arithmetic, as we
de¬ned it in Chapter 16, did not contain a symbol for greater than,
but we can de¬ne x > y by the w¬ ∃z (z = 0 § x = y + z). To say that
an element n of M is greater than all the natural numbers is to say
that n satis¬es all the w¬s:

Chapter 19
The Compactness Theorem / 549

x > 0
x > 1
x > 1+1
x > (1 + 1) + 1
Let T consist of all sentences of L that are true of the natural num-
bers. Let n be a new constant symbol and let S be the set consisting
of the following sentences:
n > 0
n > 1
n > 1+1
n > (1 + 1) + 1

Let T = T ∪ S. On the intended interpretation of L, the theory
T is inconsistent. There is no natural number that is greater than
all of the numbers 0, 1, 2, . . . . But when it comes to ¬rst-order
consequence, T is perfectly consistent, as we can see by applying
the Compactness Theorem.
To apply compactness, we need to see that any ¬nite subset T 0 of
T is true in some ¬rst-order structure. Such a theory will contain
various sentences from T , all true of the natural numbers, plus a ¬nite
number of sentences of the form n > k where we use k as shorthand
(((1 + 1) + 1) + · · · + 1)
We can make all these sentences true in the natural numbers by
interpreting the constant symbol n as a name for some number m
that is bigger than the largest k for which n > k is in T 0 . Hence, the
Compactness Theorem tells us that the whole set T is true in some
¬rst-order structure M.
The axioms of T assure us that M contains a copy of the natural
numbers (and indeed the actual natural numbers, if we replace the
interpretation of k by the number k itself). But structure M has a
“number” that is greater than all of these.

We shouldn™t get too upset or puzzled by this admittedly fascinating result.
What it shows is that there is no way to uniquely characterize arithmetic™s

Section 19.7
550 / Completeness and Incompleteness

intended domain of discourse using just axioms stated in the ¬rst-order lan-
what nonstandard
models show guage of arithmetic. With ¬rst-order axioms, we can™t rule out the existence
of “natural numbers” (that is, members of the domain) that are in¬nitely far
from zero. The distinction between being ¬nitely far from zero, which holds
of all the genuine natural numbers, and being in¬nitely far from zero, which
holds of elements like n from the proof, is not one that we can make in the
¬rst-order language.
We can recast this result by considering what would happen if we added
to our language a predicate NatNum, with the intended meaning is a natu-
ral number. If we did nothing to supplement the deductive system F, then
it would be impossible to add su¬cient meaning postulates to capture the
meaning of this predicate or to prove all the consequences expressible using
the predicate. For example, if we take the set T = T ∪S from the proof above,
then intuitively the sentence ¬NatNum(n) is a consequence of T . There can,
however, be no proof of this in F.
What would happen if we added new rules to F involving the predicate
NatNum? Could we somehow strengthen F in some way that would allow us
to prove ¬NatNum(n) from T ? The answer is that if the strengthened proof
system allows only ¬nite proofs and is sound with respect to the intended
structure, then our attempt is doomed to fail. Any proof of ¬NatNum(n) would
use only ¬nitely many premises from T . This ¬nite subset is satis¬able in the
natural numbers: just assign n to a large enough number. Consequently, by the
soundness of the extended proof system, ¬NatNum(n) must not be provable
from this ¬nite subset.
While these observations are about the natural numbers, they show some-
thing very general about any language that implicitly or explicitly expresses
the concept of ¬niteness. For example, if the language of set theory is sup-
plemented with a predicate with the intended meaning is a ¬nite set, the
Compactness Theorem can be used to show that there are ¬rst-order struc-
tures in which this predicate applies to in¬nite sets, no matter what meaning
postulates we specify for the new predicate.
For a more down-to-earth example, we could consider the ¬rst-order lan-
guage for talking about family relations. If this language has a predicate mean-


. 99
( 107 .)