as the quanti¬ers formed from some and the nouns thing and time respectively.

Section 15.1

408 / First-order Set Theory

Stated precisely, the Axiom of Extensionality claims that if sets a and b have

the same elements, then a = b.

We can express this in fol as follows:

∀a∀b[∀x(x ∈ a ” x ∈ b) ’ a = b]

In particular, the identity of a set does not depend on how it is described.

For example, suppose we have the set containing just the two numbers 7 and

11. This set can be described as {7, 11}, or as {11, 7}, it makes no di¬erence.

It can also be described as the set of prime numbers between 6 and 12, or

as the set of solutions to the equation x2 ’ 18x + 77 = 0. It might even be

the set of Max™s favorite numbers, who knows? The important point is that

the axiom of extensionality tells us that all of these descriptions pick out the

same set.

Notice that if we were developing a theory of properties rather than sets,

sets vs. properties

we would not take extensionality as an axiom. It is perfectly reasonable to have

two distinct properties that apply to exactly the same things. For example,

the property of being a prime number between 6 and 12 is a di¬erent property

from that of being a solution to the equation x2 ’ 18x + 77 = 0, and both of

these are di¬erent properties from the property of being one of Max™s favorite

numbers. It happens that these properties hold of exactly the same numbers,

but the properties themselves are still di¬erent.

The Axiom of Comprehension

The second principle of naive set theory is the so-called Unrestricted Compre-

hension Axiom. It states, roughly, that every determinate property determines

unrestricted

comprehension a set. That is, given any determinate property P , there is a set of all objects

that have this property. Thus, for example, there is a set of objects that have

the following property: being an integer greater than 6 and less than 10. By

the axiom of extensionality, this set can also be written as {7, 8, 9}.

This way of stating the Axiom of Comprehension has a certain problem,

namely it talks about properties. We don™t want to get into the business of

having to axiomatize properties as well as sets. To get around this, we use

formulas of ¬rst-order logic. Thus, for each formula P (x) of fol, we take as

a basic axiom the following:

∃a∀x[x ∈ a ” P (x)]

This says that there is a set a whose members are all and only those things

that satisfy the formula P (x). (To make sure it says this, we demand that the

variable a not occur in the w¬ P (x).)

Chapter 15

Naive set theory / 409

Notice that this is not just one axiom, but an in¬nite collection of axioms,

one for each w¬ P (x). For this reason, it is called an axiom scheme. We will axiom scheme

see later that some instances of this axiom scheme are inconsistent, so we

will have to modify the scheme. But for now we assume all of its instances as

axioms in our theory of sets.

Actually, the Axiom of Comprehension is a bit more general than our no-

tation suggests, since the w¬ P (x) can contain variables other than x, say

z1 , . . . , zn . What we really want is the universal closure of the displayed for- universal closure

mula, where all the other variables are universally quanti¬ed:

∀z1 . . . ∀zn ∃a∀x[x ∈ a ” P (x)]

Most applications of the axiom will in fact make use of these additional vari-

ables. For example, the claim that for any objects z1 and z2 , there is a pair

set {z1 , z2 } containing z1 and z2 as its only members, is an instance of this

axiom scheme:

∀z1 ∀z2 ∃a ∀x[x ∈ a ” (x = z1 ∨ x = z2 )]

In some ways, the Axiom of Comprehension, as we have stated it, is weaker

than the intuitive principle that motivated it. After all, we have already seen

that there are many determinate properties expressible in English that cannot

be expressed in any particular version of fol. These are getting left out of

our axiomatization. Still, the axiom as stated is quite strong. In fact, it is too

strong, as we will soon see.

Combining the Axioms of Extensionality and Comprehension allows us to

prove a claim about sets that clearly distinguishes them from properties.

Proposition 1. For each w¬ P (x) we can prove that there is a unique set of uniqueness theorem

objects that satisfy P (x). Using the notation introduced in Section 14.1:

∀z1 . . . ∀zn ∃!a∀x[x ∈ a ” P (x)]

This is our ¬rst chance to apply our techniques of informal proof to a claim

in set theory. Our proof might look like this:

Proof: We will prove the claim using universal generalization. Let

z1,. . . ,zn be arbitrary objects. The Axiom of Comprehension assures

us that there is at least one set of objects that satisfy P (x). So we

need only prove that there is at most one such set. Suppose a and b

are both sets that have as members exactly those things that satisfy

P (x). That is, a and b satisfy:

Section 15.1

410 / First-order Set Theory

∀x[x ∈ a ” P (x)]

∀x[x ∈ b ” P (x)]

But then it follows that a and b satisfy:

∀x[x ∈ a ” x ∈ b]

(This rather obvious step actually uses a variety of the methods of

proof we have discussed, and would be rather lengthy if we wrote it

out in complete, formal detail. You are asked to give a formal proof

in Exercise 15.5.) Applying the Axiom of Extensionality to this last

claim gives us a = b. This is what we needed to prove.

This shows that given any ¬rst-order w¬ P (x ), our axioms allow us to

deduce the existence of the set of objects that satisfy that w¬. The set of all

objects x that satisfy P (x) is often written informally as follows:

{x | P (x)}

This is read: “the set of x such that P (x).” Note that if we had used a di¬erent

variable, say “y” rather than “x,” we would have had di¬erent notation for

the very same set:

{y | P (y)}

This brace notation for sets is, like list notation, convenient but inessential.

brace notation

Neither is part of the o¬cial ¬rst-order language of set theory, since they don™t

¬t the format of ¬rst-order languages. We will only use them in informal

contexts. In any event, anything that can be said using brace notation can be

said in the o¬cial language. For example, b ∈ {x | P (x)} could be written:

∃a[∀x(x ∈ a ” P (x)) § b ∈ a]

Remember

Naive set theory has the Axiom of Extensionality and the Axiom Scheme

of Comprehension. Extensionality says that sets with the same members

are identical. Comprehension asserts that every ¬rst-order formula deter-

mines a set.

Chapter 15

Naive set theory / 411

Exercises

15.1 Are the following true or false? Prove your claims.

1. {7, 8, 9} = {7, 8, 10}

2. {7, 8, 9, 10} = {7, 8, 10, 9}

3. {7, 8, 9, 9} = {7, 8, 9}

15.2 Give a list description of the following sets.

1. The set of all prime numbers between 5 and 15.

2. { x | x is a member of your family }

3. The set of letters of the English alphabet.

4. The set of words of English with three successive double letters.

15.3 List three members of the sets de¬ned by the following properties:

1. Being a prime number larger than 15.

2. Being one of your ancestors.

3. Being a grammatical sentence of English.

4. Being a pre¬x of English.

5. Being a palindrome of English, that is, a phrase whose reverse is the very same phrase,

as with “Madam, I™m Adam”.

15.4 Are the following true or false?

1. y ∈ {x | x is a prime less than 10} if and only if y is one of 2, 3, 5 and 7.

2. {x | x is a prime less than 10} = {2, 3, 5, 7}.

3. Ronald Reagan ∈ {x | x was President of the US}.

4. “Ronald Reagan” ∈ {x | x was President of the US}.

15.5 In the Fitch ¬le Exercise 15.5, you are asked to give a formal proof of the main step in our proof

‚ of Proposition 1. You should give a complete proof, without using any of the Con rules. (You

will ¬nd the symbol ∈ on the Fitch toolbar if you scroll the predicates using the righthand

scroll button.)

15.6 Consider the following true statement:

The set whose only members are the prime numbers between 6 and 12 is the same as

the set whose only members are the solutions to the equation x2 ’ 18x + 77 = 0.

Write this statement using brace notation. Then write it out in the ¬rst-order language of

set theory, without using the brace notation. In both cases you may allow yourself natural

predicates like NatNum, Prime, and Set.

Section 15.1

412 / First-order Set Theory

Section 15.2

Singletons, the empty set, subsets

There are two special kinds of sets that sometimes cause confusion. One is

where the set is obtained using the Axiom of Comprehension, but with a

property that is satis¬ed by exactly one object. The other is when there is no

object at all satisfying the property. Let™s take these up in turn.

Suppose there is one and only one object x satisfying P (x). According to

the Axiom of Comprehension, there is a set, call it a, whose only member is

x. That is, a = {x}. Some students are tempted to think that a = x. But

in that direction lies, if not madness, at least dreadful confusion. After all,

a is a set (an abstract object) and x might have been any object at all, say

the Washington Monument. The Washington Monument is a physical object,

not a set. So we must not confuse an object x with the set {x}, called the

singleton set containing x. Even if x is a set, we must not confuse it with its

singleton set

own singleton. For example, x might have any number of elements in it, but

{x} has exactly one element: x.

The other slightly confusing case is when nothing at all satis¬es P (x).

Suppose, for example, that P (x) is the formula x = x. What are we to make

of the set

{x | x = x}?

Well, in this case the set is said to be empty, since it contains nothing. It is

easy to prove that there can be at most one such set, so it is called the empty

empty set (…)

set, and is denoted by …. Some authors use 0 to denote the empty set. It can

also be informally denoted by {}.

These special sets, singleton sets and the empty set, may seem rather

pointless, but set theory is much smoother if we accept them as full-¬‚edged

sets. If we did not, then we would always have to prove that there were at least

two objects satisfying P (x) before we could assert the existence of {x | P (x)},

and that would be a pain. The next notion is closely related to the membership

relation, but importantly di¬erent. It is the subset relation, and is de¬ned as

follows:

De¬nition Given sets a and b, we say that a is a subset of b, written a ⊆ b,

subset (⊆)

provided every member of a is also a member of b.

For example, the set of vowels, {a, e, i, o, u}, is a subset of the set of letters

of the alphabet, {a, b, c, . . . , z}, but not vice versa. Similarly, the singleton set

{Washington Monument} is a subset of the set {x | x is taller than 100 feet}.

It is very important to read the sentences “a ∈ b” and “a ⊆ b” carefully.

subset vs. membership

Chapter 15

Singletons, the empty set, subsets / 413

The ¬rst is read “a is a member of b” or “a is an element of b.” The latter is

read “a is a subset of b.” Sometimes it is tempting to read one or the other of

these as “a is included in b.” However, this is a very bad idea, since the term

“included” is ambiguous between membership and subset. (If you can™t resist

using “included,” use it only for the subset relation.)

From the point of view of fol, there are two ways to think of our de¬nition

of “subset.” One is to think of it as saying that the formula “a ⊆ b” is an

abbreviation of the following w¬:

∀x[x ∈ a ’ x ∈ b]

Another way is to think of ⊆ as an additional binary relation symbol in our

language, and to construe the de¬nition as an axiom: