<<

. 73
( 107 .)



>>

1. Claire gave Max at least two pets at 2:00 pm.
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

<<

. 73
( 107 .)



>>