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

o

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.

o

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

o

proved it for single sentences, Skolem proved it for countably in¬nite sets of

sentences.

Theorem (L¨wenheim-Skolem Theorem) Let T be a set of sentences in a

o

L¨wenheim-Skolem

o

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

o

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?

o

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

o

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

o

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

for

(((1 + 1) + 1) + · · · + 1)

k

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-