<<

. 74
( 107 .)



>>

you read the section on generalized quanti¬ers in Chapter 14, you will recognize these
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:

<<

. 74
( 107 .)



>>