and 
, the extensionality axiom yields two alternative
strategies for proving that 
:Nearly all mathematical fields apply concepts from set theory, and practically every mathematical statement can be phrased into one about sets. For these reasons, set theory is often viewed as a foundation for mathematics. In this chapter, we will begin to investigate some of the axioms of set theory that were introduced earlier. Moreover, we shall begin proving theorems about sets, and each of our proofs will be justified by the axioms. We will also show that the sets and operations discussed in Chapter 1 can be derived from these axioms.
The first six axioms, taken together, will allow us to develop the operations on sets that were discussed in the previous chapter. Furthermore, they will allow us to define additional operations on sets that were not previously covered.
Our first axiom is a very simple, but necessary, statement that proclaims that a set is uniquely determined by its elements. In other words, two sets are different if and only if one set contains an element that is not in the other set.
Extensionality Axiom. Two sets are equal if and only if they have exactly the same elements.
For sets and , the extensionality axiom yields two alternative
strategies for proving that :
and 
.
, that 
if and only if 
.We will refer to strategy (a) as the “double-subset” strategy, and
strategy (b) will be described as the “iff” strategy, where iff abbreviates the
phrase “if and only if.” One efficient way of executing strategy (b) is to
derive a succession of equivalences starting with 
and then ending
with 
. This is usually done by citing appropriate definitions and logic
laws (see Sections 1.2 and 1.3). We will illustrate the difference between
these two strategies by presenting two proofs of Theorem 2.1.1 in
Section 2.1.3.
The extensionality axiom does not imply that there exists a set. Our next five axioms do assert that certain sets exist. In addition, these axioms can be used to establish the existence of many of the sets that we typically take for granted in mathematics.
Our next axiom explicitly implies that “a set exists.”
Empty Set Axiom. There is a set with no elements.
Is there more than one set without any elements? The Extensionality
Axiom implies that there is only one such set (see Exercise 9 on page 27),
and we shall denote it by the symbol 
.
The next four axioms will allow us to build new sets from given sets.
Subset Axiom. Let 
be a formula. For every set 
there exists a
set 
that consists of all the elements 
such that 
holds.
The subset axiom states that for any set 
and for any formula 
, one
can construct a set that consists of just the elements in 
that satisfy the
property 
. In other words, the set 
exists. Observe
that 
.
Let 
and 
be two sets. The subset axiom implies that the
intersection and difference of these two sets exist, because
and thus, by the subset axiom, 
and 
are sets. On the other
hand, the subset axiom does not imply, in general, that the union 
is
a set.
Our next theorem follows from the extensionality and subset axioms. We will give two proofs of this theorem. The first proof employs the double-subset strategy, and the second proof applies the iff strategy (see page 28).
First Proof. Let 
, 
, and 
be sets. We prove that
.
(
). Let 
. Hence, 
and 
. Thus,
, 
, and 
. Because 
and 
, we have
. Since 
, we conclude that 
.
(
). Let 
. Thus, 
and 
. Because
, we have that 
and 
. We also have that
, and so we now conclude that 
. Furthermore, we know
that 
. Hence, 
.
Therefore, 
. ☐
In our first proof of Theorem 2.1.1, the annotations (
) and
(
) are added as a courtesy to the reader. The notation (
) is
used to make it clear to the reader that we are proving that the first
set1 is
a subset of the second set. The notation (
) indicates that we are proving
that the second set is a subset of the first set. We shall now reprove
Theorem 2.1.1 using the iff strategy.
Second Proof. Suppose that 
, 
, and 
are sets. Let 
be arbitrary.
Then
Therefore, 
. ☐
The argument used in Russell’s paradox will be applied in the proof of our next theorem, which states that there is no set of all sets.
Proof. Suppose, for a contradiction, that there exists a set in which every
set is a member. Let 
denote this set. Thus 
; that is, the set
contains all sets as members. By the subset axiom there exists a set 
such that
Observe from the definition of 
we have that
Because 
is a set and 
contains all sets as members, we conclude that
. Now that 
holds, the above (
) implies that 
if and
only if 
, which is clearly a contradiction. ☐
Since every set is equal to itself, we see that each set belongs in the
collection 
. Theorem 2.1.2 implies that 
is not a set.
Thus, given a formula 
, we cannot immediately conclude that the
collection 
is a set. Hence, we shall refer to any collection of the
form 
as a class. Thus, 
is a class that is not a set. If
a class is not a set, then it is a proper class, and hence, it is an “unbounded
collection” (see Exercise 34).
In the future, we will sometimes be required to prove that some classes are
actually sets (see the proof of Theorem 2.1.7). When can we prove that a
given class 
is also a set? The following theorem addresses this
question.
Theorem 2.1.3. Let 
be a formula. Suppose that there is a set
such that for all 
, if 
, then 
. Then there is a unique
set 
such that for all 
,
In other words, the class 
is, in fact, equal to the set 
.
Proof. Let 
be a set such that (
) for all 
, if 
, then 
.
By the subset axiom, let 
be the set 
. Clearly, (
)
implies that 
if and only if 
, for all 
. The set 
is unique by
the extensionality axiom. ☐
Remark 2.1.4. The regularity axiom implies that no set can be a
member of itself (see Exercise 3 on page 26). Thus, in the proof of
Theorem 2.1.2, the axioms of set theory imply that the collection 
,
defined in (2.1), is equal to 
.
Remark 2.1.5. When applying the subset axiom, we can use a formula
that is expressed in English, using appropriate symbols (e.g., 
,
). Such English formulas can actually be written as formulas in the
language of set theory.
The pairing axiom states that whenever we have two sets 
and 
, there is
a set 
whose only members are 
and 
. We can use the extensionality
axiom to show that this set 
is unique. We shall denote the set 
by
.
Pairing Axiom. For every 
and 
there is a set that consists of just
and 
.
Given any sets 
and 
, the pairing and extensionality axioms justify
the following definition.
Thus, if 
, then 
or 
. The pairing axiom implies
that for any set 
, we also have the set 
, which, of course, is equal to
the set 
by the extensionality axiom. So, given any set 
, we can
construct the set 
. Since the set 
has only one element, such a set is
referred to as a singleton.
Suppose that we have three sets 
, 
, and 
. The pairing axiom yields
the sets 
, 
, and 
. Can we conclude that
there is a set containing only 
, 
, and 
? We will be able to do this
once we understand the union axiom.
Let 
be a set. The union axiom allows us to construct a set that
consists of all the elements that belong to at least one of the sets in
.2
Union Axiom. For every set 
there is a set 
that consists of all
the elements that belong to at least one set in 
.
The union axiom states that, for any given set 
, there exists a set 
whose members are precisely the elements of members in 
. The set
given by the union axiom is denoted by 
. Thus, 
is
the set of elements 
such that 
for some 
; that is,
We shall say that the set 
is the union of 
. So for any set 
we
have that
The union axiom, together with the pairing axiom, allows us to
construct the union of any two sets 
and 
. Let 
.
Then
Similarly, we have that 
In addition, we have 
.
Suppose that we have three sets 
, 
, and 
. We can now use the
pairing and union axioms to construct a set that consists of only 
, 
, and
. We have the sets 
and 
by the pairing axiom. By the union
axiom we have the set
which consists of the three elements 
, 
, and 
. Similarly, one
can assemble the set 
consisting of the four elements
, and so on.
We saw that the subset axiom allows us to construct the intersection of two sets. Our next theorem will allow us to take the intersection of all the sets that belong to a given nonempty set.
Proof. Let 
be a nonempty set. So let 
. For each 
, if 
belongs to every member of 
, then clearly 
. Since 
is a
set, Theorem 2.1.3 implies that there is a unique set 
satisfying
(2.2). ☐
Definition 2.1.8. Let 
be a nonempty set. We denote the unique set 
given in the above Theorem 2.1.7 by 
, which is said to be the
intersection of 
.
Thus, if 
is a nonempty set, then 
if and only if
.
We see that 
and 
.
Furthermore, if 
, then 
.
Why does Definition 2.1.8 require that 
? Observe that the
statement “
belongs to every member of 
” is vacuously true. To see
this, suppose that this statement is false. Then 
does not belong to some
member of 
, but the set 
has no elements! Therefore, the statement is
true for all sets 
.
Now, suppose 
is a set. Thus,
Because the statement “
belongs to every member of 
” is true
for every 
, we conclude that 
must contain every set, and
this contradicts Theorem 2.1.2. Therefore, the notation 
is
undefined.
The next example clearly states what it means for an element to be in, and not in, a union and intersection.
Example 5. Suppose that 
is set. Then the following statements are
true:
means that 
for some 
.
means that 
for every 
.
means that 
for every 
.
means that 
for some 
.We now demonstrate how one works with our generalized notions of union and intersection in the following theorem and proof.
Proof. Let 
. To prove that 
, let 
.
Thus, 
for some 
. Since 
, we have that 
.
So 
for some 
. Hence, 
. Now, suppose that
is nonempty. Because 
, we see that 
is also nonempty.
Let 
. Thus, 
for every 
. Since 
,
we conclude that 
for every 
as well. Therefore,
. ☐
Recall that 
means that 
is a subset of 
; that is, every element
in 
is also an element in 
. Given any set 
, the power set
axiom ensures that one can form a set that consists of every subset of
.
Power Set Axiom. For every set 
there is a set 
that consists of
all the sets that are subsets of 
.
When 
is a set, the power set axiom states that there is a set 
such
that if 
, then 
. In addition, this axiom implies that if
, then 
.
be a set. The power set of 
, denoted by
, is the set whose elements are all of the subsets of 
; that is,
.
Thus, as noted above, 
if and only if 
. Recall that
and 
(see page 2). Therefore, 
and 
for every set 
. The power set of a set 
has more elements than 
. For
example,
.
.
.
.The power set operation distributes over the intersection of two sets (for a generalization, see Exercise 14 on page 40).
Proof. Let 
and 
be sets. We shall prove that 
.
(
). Let 
. Hence, 
. Thus, 
and
(see Exercise 4). So 
and 
. Therefore,
.
(
). Let 
. Thus, 
and 
.
Hence, 
and 
. Therefore, 
(see Exercise 4), and
we now conclude that 
. ☐
Theorem 2.1.11 motivates the following simple question: Can one prove
the equality 
for any two sets 
and 
?
The answer is no. Let 
and 
. Clearly, the set
is subset of 
, and thus, 
. Because 
is not a subset of 
and is also not a subset of 
, we see that
. So 
and 
. Therefore,
.
Prove the following theorems, where 
, 
, 
, and 
are sets:
4. Theorem. 
and 
if and only if 
.
such that 
.
.
if and only if 
.
, then 
or
.
be a set. Then 
.
be a set. Then 
.
be a set and let 
. Then 
.
be a set and let 
. Then 
.
and 
be sets. If 
for some 
,
then we have that 
.
and 
be sets. Suppose 
for every
. Then 
.
be a set. Then 
.
32. Theorem. Let 
. Then 
.
34. Theorem. Let 
be a formula. Then 
is a proper
class if and only if for every set 
there is an 
such that 
and 
.
and 
to
be the set 
. Then for sets 
, 
, 
we
have
.
.Exercise Notes: Exercises 8–9 are referred to as the distributive laws for sets. Exercises 10–11 are called the associative laws for sets.
Sets can be combined in a number of ways to construct another set. We will now see how the first six axioms of Zermelo–Fraenkel set theory can be used to prove a number of theorems concerning several important methods, not identified in the previous section, for constructing a new set from given sets.
Lemma 2.2.1. Let 
and 
be sets. Then there is a unique set 
such
that for all 
,
We shall let 
denote the set 
.
Proof. Let 
and 
be sets. If 
for some 
, then
and so 
. Since 
is a set, Theorem 2.1.3 implies
that there exists a unique set 
satisfying (2.3). ☐
The “double-subset” proof strategy will be used to prove our next theorem.
Before reading this proof, one should review items (1)–(4) of Example 5 on
page 34 and note that 
iff 
for every
.
Proof. We prove that 
and leave (2) as an
exercise.
. Let 
. We prove that 
as
follows:3
Therefore, 
.
. Let 
. We prove that 
as
follows:
Therefore, 
. The proof of (1) is complete. ☐
Lemma 2.2.3. For all sets 
and 
, there exist unique sets 
and 
such that for all 
:
We let 
denote the set 
and 
denote
the set 
.
Proof. Let 
and 
be sets. If 
for a 
, then
. Thus, 
. As 
is a set,
Theorem 2.1.3 asserts that there exists a unique set 
satisfying (2.4). In a
similar manner, one can show that there is a unique set 
satisfying (2.5)
(see Exercise 5). ☐
Proof. We prove (1) using the “iff” strategy and leave (2) as an exercise.
Let 
be given. We prove that 
iff 
as follows:
The above proof implicitly applied the quantifier distribution law (QDL) 1.3.6(5). We demonstrate this in the following more “symbolic” proof:
We now prove a lemma that will justify some of the exercises of this section.
Proof. Let 
be any set. If 
for some 
, then
by Exercise 32 on page 37. As 
is a set,
there exists a unique set 
satisfying (2.6) by Theorem 2.1.3. ☐
Prove the following theorems:
be a set and 
. Then
.
and 
be sets. Then
.
and 
be sets. Then
.
5. Theorem. Let 
and 
be sets. Then there exists a unique
set 
such that for all 
we have that 
if and only if
for some 
.
and 
be sets. Then there is a unique set
such that for all 
, we have that 
if and only if
for some 
and some 
.
for
any sets 
and 
.
and 
be sets. Then there is a unique set
such that for all 
, we have that 
if and only if
for some 
and some 
.
when
and 
are nonempty.
for any sets
and 
.
12. Theorem. If 
and 
are nonempty, then
.
14. Theorem. Let 
be a nonempty set. Then
.
be a set. Then 
.
be a set. If there is an 
such that
for all 
, then 
.
, 
, and 
are sets. Then
.
and 
, the 
is the unique
set whose only members are 
and 
.
. Then
.
. Then
be a nonempty set. There is a unique set 
such
that for all 
,
. Then
.
. Then
.
.
.
.
. Then 
, and if 
is nonempty, then 
.
and 
be sets. Then
.
, then 
and 
. 
and 
, then 
. 
, then 
. 
.
.
.
.
.
.
.
.
and
.
.
, then 
.
and 
, then 
.
and 
, then 
.
.
and 
be sets. If 
for all 
,
then we have that 
. 
be a set. Then 
. 
is not a set. 
is a set and 
is
nonempty, then
,
.
and 
are sets, then
for 
,
.
is a set, then there exists a unique set 
such that for
all 
is denoted by 
.
. Then 
for any
set 
. 
and 
be sets. Then
. 
and 
be sets. Then
.