2. Claire gave Max at most two pets at 2:00 pm.

3. Claire gave Max several pets at 2:00 pm.

4. Claire was a student before Max was.

5. The pet Max gave Claire at 2:00 pm was hungry.

6. Most pets were hungry at noon.

7. All but two pets were hungry at noon.

8. There is at least one student who made Max angry every time he (or she) gave Max a

pet.

9. Max was angry whenever a particular student gave him a pet.

10. If someone gave Max a pet, it must have been Claire.

11. No pet fed by Max between 2:00 and 2:05 belonged to Claire.

12. If Claire fed one of Max™s pets before 2:00 pm, then Max was angry at 2:00 pm.

13. Folly™s owner was a student.

14. Before 3:00, no one gave anyone a pet unless it was hungry.

15. No one should give anyone a pet unless it is hungry.

16. A pet that is not hungry always belongs to someone or other.

17. A pet that is not hungry must belong to someone or other.

18. Max was angry at 2:00 pm because Claire had fed one of his pets.

19. When Max gave Folly to Claire, Folly was hungry, but Folly was not hungry ¬ve minutes

later.

20. No student could possibly be a pet.

14.58 Here is a famous puzzle. There was a Roman who went by two names, “Cicero” and “Tully.”

Discuss the validity or invalidity of the following argument.

Bill claims Cicero was a great orator.

Cicero is Tully.

Bill claims Tully was a great orator.

Section 14.6

400 / More about Quantification

What is at stake here is nothing more or less than the principle that if (. . . a . . . ) is true, and

a = b, then (. . . b . . . ) is true. [Hint: Does the argument sound more reasonable if we replace

“claims” by “claims that”? By the way, the puzzle is usually stated with “believes” rather than

“claims.”]

The following more di¬cult exercises are not speci¬cally relevant to this section, but to the general topic

of truth of quanti¬ed sentences. They can be considered as research projects in certain types of classes.

14.59 (Persistence through expansion) As we saw in Exercise 11.5, page 292, some sentences simply

can™t be made false by adding objects of various sorts to the world. Once they are true, they

stay true. For example, the sentence There is at least one cube and one tetrahedron, if true,

cannot be made false by adding objects to the world. This exercise delves into the analysis of

this phenomenon in a bit more depth.

Let™s say that a sentence A is persistent through expansion if, whenever it is true, it remains

true no matter how many objects are added to the world. (In logic books, this is usually called

just persistence, or persistence under extensions.) Notice that this is a semantic notion. That

is, it™s de¬ned in terms of truth in worlds. But there is a corresponding syntactic notion. Call a

sentence existential if it is logically equivalent to a prenex sentence containing only existential

quanti¬ers.

—¦ Show that Cube(a) ’ ∃x FrontOf(x, a) is an existential sentence.

—¦ Is ∃x FrontOf(x, a) ’ Cube(a) an existential sentence?

—¦ Show that every existential sentence is persistent through expansion. [Hint: You will have

to prove something slightly stronger, by induction on w¬s. If you are not familiar with

induction on w¬s, just try to understand why this is the case. If you are familiar with

induction, try to give a rigorous proof.] Conclude that every sentence equivalent to an

existential sentence is persistent through expansion.

It is a theorem, due to Tarski andLo´ (a Polish logician whose name is pronounced more like

s

“wash” than like “loss”), that any sentence that is persistent through expansion is existential.

Since this is the converse of what you were asked to prove, we can conclude that a sentence

is persistent through expansion if and only if it is existential. This is a classic example of a

theorem that gives a syntactic characterization of some semantic notion. For a proof of the

theorem, see any textbook in model theory.

14.60 (Invariance under motion, part 1) The real world does not hold still, the way the world of

‚ mathematical objects does. Things move around. The truth values of some sentences change

with such motion, while the truth values of other sentences don™t. Open Ockham™s World and

Ockham™s Sentences. Verify that all the sentences are true in the given world. Make as many

of Ockham™s Sentences false as you can by just moving objects around. Don™t add or remove

any objects from the world, or change their size or shape. You should be able to make false (in a

Chapter 14

Other expressive limitations of first-order logic / 401

single world) all of the sentences containing any spatial predicates, that is, containing LeftOf,

RightOf, FrontOf, BackOf, or Between. (However, this is a quirk of this list of sentences, as we

will see in the next exercise.) Save the world as World 14.60.

14.61 (Invariance under motion, part 2) Call a sentence invariant under motion if, for every world,

the truth value of the sentence (whether true or false) does not vary as objects move around

in that world.

1. Prove that if a sentence does not contain any spatial predicates, then it is invariant

under motion.

2. Give an example of a sentence containing a spatial predicate that is nonetheless in-

variant under motion.

3. Give another such example. But this time, make sure your sentence is not ¬rst-order

equivalent to any sentence that doesn™t contain spatial predicates.

14.62 (Persistence under growth, part 1) In the real world, things not only move around, they also

‚ grow larger. (Some things also shrink, but ignore that for now.) Starting with Ockham™s World,

make the following sentences true by allowing some of the objects to grow:

1. ∀x ¬Small(x)

2. ∃x ∃y (Cube(x) § Dodec(y) § Larger(y, x))

3. ∀y (Cube(y) ’ ∀v (v = y ’ Larger(v, y)))

4. ¬∃x ∃y (¬Large(x) § ¬Large(y) § x = y)

How many of Ockham™s Sentences are false in this world? Save your world as World 14.62.

14.63 (Persistence under growth, part 2) Say that a sentence S is persistent under growth if, for

every world in which S is true, S remains true if some or all of the objects in that world get

larger. Thus, Large(a) and ¬Small(a) are persistent under growth, but Smaller(a, b) isn™t. Give

a syntactic de¬nition of as large a set of sentences as you can for which every sentence in the

set is persistent under growth. Can you prove that all of these sentences are persistent under

growth?

Section 14.6

402

Part III

Applications and

Metatheory

403

404

Chapter 15

First-order Set Theory

Over the past hundred years, set theory has become an important and useful

part of mathematics. It is used both in mathematics itself, as a sort of universal

framework for describing other mathematical theories, and also in applications

outside of mathematics, especially in computer science, linguistics, and the

other symbolic sciences. The reason set theory is so useful is that it provides

us with tools for modeling an extraordinary variety of structures.

Personally, we think of sets as being a lot like Tinkertoys or Lego blocks:

basic kits out of which we can construct models of practically anything. If modeling in set theory

you go on to study mathematics, you will no doubt take courses in which

natural numbers are modeled by sets of a particular kind, and real numbers

are modeled by sets of another kind. In the study of rational decision making,

economists use sets to model situations in which rational agents choose among

competing alternatives. Later in this chapter, we™ll do a little of this, modeling

properties, relations, and functions as sets. These models are used extensively

in philosophy, computer science, and mathematics. In Chapter 18 we will use

these same tools to make rigorous our notions of ¬rst-order consequence and

¬rst-order validity.

In this chapter, though, we will start the other way around, applying

what we have learned about ¬rst-order logic to the study of set theory. Since logic and set theory

set theory is generally presented as an axiomatized theory within a ¬rst-

order language, this gives us an opportunity to apply just about everything

we™ve learned so far. We will be expressing various set-theoretic claims in fol,

¬guring out consequences of these claims, and giving informal proofs of these

claims. The one thing we won™t be doing very much is constructing formal

proofs of set-theoretic claims. This may disappoint you. Many students are

initially intimidated by formal proofs, but come to prefer them over informal

proofs because the rules of the game are so clear-cut. For better or worse,

however, formal proofs of substantive set-theoretic claims can be hundreds or

even thousands of steps long. In cases where the formal proof is manageable,

we will ask you to formalize it in the exercises.

Set theory has a rather complicated and interesting history. Another ob-

jective of this chapter is to give you a feeling for this history. We will start out

with an untutored, or “naive” notion of set, the one that you were no doubt naive set theory

exposed to in elementary school. We begin by isolating two basic principles

that seem, at ¬rst sight, to be clearly true of this intuitive notion of set. The

405

406 / First-order Set Theory

principles are called the Axiom of Extensionality and the Axiom of Compre-

hension. We™ll state the axioms in the ¬rst-order language of set theory and

draw out some of their consequences.

We don™t have to go too far, however, before we discover that we can

prove a contradiction from these axioms. This contradiction will demonstrate

that the axioms are inconsistent. There simply can™t be a domain of discourse

satisfying our axioms; which is to say that the intuitive notion of a set is just

plain inconsistent. The inconsistency, in its simplest incarnation, is known as

Russell™s Paradox.

Russell™s Paradox has had a profound impact on modern set theory and

Russell™s Paradox

logic. It forced the founders of set theory to go back and think more critically

about the intuitive notion of a set. The aim of much early work in set theory

was to re¬ne the conception in a way that avoids inconsistency, but retains the

power of the intuitive notion. Examining this re¬ned conception of set leads

to a modi¬cation of the axioms. We end the chapter by stating the revised

axioms that make up the most widely used set theory, known as Zermelo-

Frankel set theory, or zfc. Most of the proofs given from the naive theory

carry over to zfc, but not any of the known proofs of inconsistency. zfc is

believed by almost every mathematician to be not only consistent, but true

of a natural domain of sets.

This may seem like a rather tortured route to the modern theory, but it

is very hard to understand and appreciate zfc without ¬rst being exposed

to naive set theory, understanding what is wrong with it, and seeing how the

modern theory derives from this understanding.

Section 15.1

Naive set theory

The ¬rst person to study sets extensively and to appreciate the inconsistencies

lurking in the naive conception was the nineteenth century German mathe-

matician Georg Cantor. According to the naive conception, a set is just a

collection of things, like a set of chairs, a set of dominoes, or a set of numbers.

sets and membership

The things in the collection are said to be members of the set. We write a ∈ b,

and read “a is a member (or an element) of b,” if a is one of the objects that

makes up the set b. If we can list all the members of b, say the numbers 7, 8,

and 10, then we write b = {7, 8, 10}. This is called a list description of the set.

list description

As you will recall, the ¬rst-order language of set theory has two relation

symbols, = and ∈. Beyond that, there are some options. If we want our domain

of discourse to include not just sets but other things as well, then we need

sets and non-sets

Chapter 15

Naive set theory / 407

some way to distinguish sets from other objects. One way that is sometimes

used is to have a unary predicate symbol Set (x) that holds of all and only

sets. An alternate way of accomplishing the same thing, one that results in

formulas that are easier to read, is to have two sorts of variables. One sort has

a domain that includes all and only the sets, while the other sort ranges over

sets and any other objects in the domain of discourse. This is a common way

to extend fol, and produces what is known as a many-sorted language. We™ve

in fact seen something like this before, when we translated sentences like Max many-sorted language

gave something to Claire between 2:00 and 3:00. In translating such sentences,

we often use one sort of variable for quantifying over ordinary objects (∃x)

and another to quantify over times (∃t).1

This is the approach we will take. We use variables a, b, c, . . . , with and

without subscripts, to range over sets, and variables x, y, z, . . . to range over

everything”ordinary objects as well as sets. Thus, for example, if we wanted

to say that everything is a member of some set or other, we would write

∀x∃a(x ∈ a)

To say the same thing using only one kind of variable and the predicate Set(x),

we would have to write

∀x∃y[Set(y) § x ∈ y]

Later in the chapter, we will sometimes use capital letters such as R and D

as variables ranging over certain kinds of sets, choosing the letter to help us

remember the kind of set we are interested in.

There are other symbols that get used a lot in doing set theory. For exam- other common symbols

ple, there is an individual constant … used to denote the empty set, a relation

symbol ⊆ used to express the subset relation, and function symbols © (inter-

section) and ∪ (union), among others. None of these symbols are necessary to

do set theory, though they simplify formulas a great deal. One of the things

we™ll do in this chapter is introduce abbreviations willy nilly, so we can use

these symbols without o¬cially adding them to the language. Who said you

can™t have your cake and eat it, too?

The Axiom of Extensionality

As we said, there are two principles that capture the naive conception of a

set. One is that a set is completely determined by its members. If you know

the members of a set b, then you know everything there is to know about the

identity of the set. This principle is captured by the Axiom of Extensionality. Axiom of

Extensionality

1 If