element c ∈ C. Thus, since a ∈ B and c ∈ C, we have (a, c) ∈ B × C. But then,
since B × C = A × C, we have (a, c) ∈ A × C. It follows that a ∈ A. We have
shown a ∈ B implies a ∈ A, so B ⊆ A.
The previous two paragraphs have shown A ⊆ B and B ⊆ A, so A = B. In
summary, we have shown that if A × C = B × C, then A = B. This completes
the proof.
■
Now we’ll look at another way that set operations are similar to oper-
ations on numbers. From algebra you are familiar with the distributive
property a · (b + c) = a · b + a · c. Replace the numbers a, b, c with sets A, B, C,
and replace · with × and + with ∩. We get A × (B ∩ C) = (A × B) ∩ (A × C).
This statement turns out to be true, as we now prove.
Example 8.12
Given sets A, B, and C, prove A × (B ∩ C) = (A × B) ∩ (A × C).
Proof. First we will show that A × (B ∩ C) ⊆ (A × B) ∩ (A × C).
Suppose (a, b) ∈ A × (B ∩ C).
By definition of the Cartesian product, this means a ∈ A and b ∈ B ∩ C.
By definition of intersection, it follows that b ∈ B and b ∈ C.
138
Proofs Involving Sets
Thus, since a ∈ A and b ∈ B, it follows that (a, b) ∈ A × B (by definition of ×).
Also, since a ∈ A and b ∈ C, it follows that (a, b) ∈ A × C (by definition of ×).
Now we have (a, b) ∈ A × B and (a, b) ∈ A × C, so (a, b) ∈ (A × B) ∩ (A × C).
We’ve shown that (a, b) ∈ A × (B ∩ C) implies (a, b) ∈ (A × B) ∩ (A × C) so we
have A × (B ∩ C) ⊆ (A × B) ∩ (A × C).
Next we will show that (A × B) ∩ (A × C) ⊆ A × (B ∩ C).
Suppose (a, b) ∈ (A × B) ∩ (A × C).
By definition of intersection, this means (a, b) ∈ A × B and (a, b) ∈ A × C.
By definition of the Cartesian product, (a, b) ∈ A × B means a ∈ A and b ∈ B.
By definition of the Cartesian product, (a, b) ∈ A × C means a ∈ A and b ∈ C.
We now have b ∈ B and b ∈ C, so b ∈ B ∩ C, by definition of intersection.
Thus we’ve deduced that a ∈ A and b ∈ B ∩ C, so (a, b) ∈ A × (B ∩ C).
In summary, we’ve shown that (a, b) ∈ (A×B)∩(A×C) implies (a, b) ∈ A×(B∩C)
so we have (A × B) ∩ (A × C) ⊆ A × (B ∩ C).
The previous two paragraphs show that A ×(B ∩ C) ⊆ (A × B)∩(A × C) and
(A ×B)∩(A×C) ⊆ A×(B∩C), so it follows that (A×B)∩(A×C) = A×(B∩C). ■
Occasionally you can prove two sets are equal by working out a series of
equalities leading from one set to the other. This is analogous to showing
two algebraic expressions are equal by manipulating one until you obtain
the other. We illustrate this in the following example, which gives an
alternate solution to the previous example. You are cautioned that this
approach is sometimes difficult to apply, but when it works it can shorten
a proof dramatically.
Before beginning the example, a note is in order. Notice that any
statement P is logically equivalent to P ∧ P. (Write out a truth table if you
are in doubt.) At one point in the following example we will replace the
expression x ∈ A with the logically equivalent statement (x ∈ A) ∧ (x ∈ A).
Example 8.13
Given sets A, B, and C, prove A × (B ∩ C) = (A × B) ∩ (A × C).
Proof. Just observe the following sequence of equalities.
A × (B ∩ C) = ©(x, y) : (x ∈ A) ∧ (y ∈ B ∩ C)ª
(def. of ×)
= ©(x, y) : (x ∈ A) ∧ (y ∈ B) ∧ (y ∈ C)ª
(def. of ∩)
= ©(x, y) : (x ∈ A) ∧ (x ∈ A) ∧ (y ∈ B) ∧ (y ∈ C)ª
(P = P ∧ P)
= ©(x, y) : ((x ∈ A) ∧ (y ∈ B)) ∧ ((x ∈ A) ∧ (y ∈ C))ª
(rearrange)
= ©(x, y) : (x ∈ A) ∧ (y ∈ B)ª ∩ ©(x, y) : (x ∈ A) ∧ (y ∈ C)ª (def. of ∩)
= (A × B) ∩ (A × C)
(def. of ×)
The proof is complete.
■
Examples: Perfect Numbers
139
The equation A ×(B ∩C) = (A ×B)∩(A ×C) just obtained is a fundamental
law that you may actually use fairly often as you continue with mathematics.
Some similar equations are listed below. Each of these can be proved with
this section’s techniques, and the exercises will ask that you do so.
)
A ∩ B = A ∪ B
DeMorgan’s laws for sets
A ∪ B = A ∩ B
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) ¾
Distributive laws for sets
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A × (B ∪ C) = (A × B) ∪ (A × C) ¾
Distributive laws for sets
A × (B ∩ C) = (A × B) ∩ (A × C)
It is very good practice to prove these equations. Depending on your
learning style, it is probably not necessary to commit them to memory.
But don’t forget them entirely. They may well be useful later in your
mathematical education. If so, you can look them up or re-derive them on
the spot. If you go on to study mathematics deeply, you will at some point
realize that you’ve internalized them without even being cognizant of it.
8.4 Examples: Perfect Numbers
Sometimes it takes a good bit of work and creativity to show that one set
is a subset of another or that they are equal. We illustrate this now with
examples from number theory involving what are called perfect numbers.
Even though this topic is quite old, dating back more than 2000 years, it
leads to some questions that are unanswered even today.
The problem involves adding up the positive divisors of a natural
number. To begin the discussion, consider the number 12. If we add up the
positive divisors of 12 that are less than 12, we obtain 1 + 2 + 3 + 4 + 6 = 16,
which is greater than 12. Doing the same thing for 15, we get 1 + 3 + 5 = 9
which is less than 15. For the most part, given a natural number p, the
sum of its positive divisors less than itself will either be greater than p
or less than p. But occasionally the divisors add up to exactly p. If this
happens, then p is said to be a perfect number.
Definition 8.1
A number p ∈ N is perfect if it equals the sum of its
positive divisors less than itself. Some examples follow.
• The number 6 is perfect since 6 = 1 + 2 + 3.
• The number 28 is perfect since 28 = 1 + 2 + 4 + 7 + 14.
• The number 496 is perfect since 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248.
140
Proofs Involving Sets
Though it would take a while to find it by trial-and-error, the next
perfect number after 496 is 8128. You can check that 8128 is perfect. Its
divisors are 1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 1016, 2032, 4064 and indeed
8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064.
Are there other perfect numbers? How can they be found? Do they obey any
patterns? These questions fascinated the ancient Greek mathematicians.
In what follows we will develop an idea—recorded by Euclid—that partially
answers these questions.
Although Euclid did not use sets,1 we will
nonetheless phrase his idea using the language of sets.
Since our goal is to understand what numbers
are perfect, let’s define
the following set:
P = ©p ∈ N : p
ª
is perfect .
Therefore P = ©6, 28, 496, 8128, . . . ª, but it is unclear what numbers are in
P other than the ones listed. Our goal is to gain a better understanding
of just which numbers the set P includes. To do this, we will examine
the following set A. It looks more complicated than P, but it will be very
helpful for understanding P, as we will soon see.
A = ©2n−1(2n − 1) : n ∈ N,
ª
and 2n − 1 is prime
In words, A consists of every natural number of form 2n−1(2n − 1), where
2n − 1 is prime. To get a feel for what numbers belong to A, look at the
following table. For each natural number n, it tallies the corresponding
numbers 2n−1 and 2n − 1. If 2n − 1 happens to be prime, then the product
2n−1(2n − 1) is given; otherwise that entry is labeled with an ∗.
n
2n−1
2n − 1
2n−1(2n − 1)
1
1
1
∗
2
2
3
6
3
4
7
28
4
8
15
∗
5
16
31
496
6
32
63
∗
7
64
127
8128
8
128
255
∗
9
256
511
∗
10
512
1023
∗
11
1024
2047
∗
12
2048
4095
∗
13
4096
8191
33, 550, 336
1Set theory was invented over 2000 years after Euclid died.
Examples: Perfect Numbers
141
Notice that the first four entries of A are the perfect numbers 6, 28,
496 and 8128. At this point you may want to jump to the conclusion that
A = P. But it is a shocking fact that in over 2000 years no one has ever
been able to determine whether or not A = P. But it is known that A ⊆ P,
and we will now prove it. In other words, we are going to show that every
element of A is perfect. (But by itself, that leaves open the possibility that
there may be some perfect numbers in P that are not in A.)
The main ingredient for the proof will be the formula for the sum of a
geometric series with common ratio r. You probably saw this most recently
in Calculus II. The formula is
n
rn+1
X
− 1
rk =
.
r
k=0
− 1
We will need this for the case r = 2, which is
n
X 2k = 2n+1 − 1.
(8.1)
k=0
(See the solution for Exercise 19 in Section 7.4 for a proof of this for-
mula.) Now we are ready to prove our result. Let’s draw attention to its
significance by calling it a theorem rather than a proposition.
Theorem 8.1
ª
If A = © 2n−1(2n − 1) : n ∈ N, and 2n − 1 is prime
and P =
© p ∈ N : p
ª
is perfect , then A ⊆ P.
Proof. Assume A and P are as stated. To show A ⊆ P, we must show that
p ∈ A implies p ∈ P. Thus suppose p ∈ A. By definition of A, this means
p = 2n−1(2n − 1)
(8.2)
for some n ∈ N for which 2n − 1 is prime. We want to show that p ∈ P, that
is, we want to show p is perfect. Thus, we need to show that the sum of
the positive divisors of p that are less than p add up to p. Notice that
since 2n − 1 is prime, any divisor of p = 2n−1(2n − 1) must have the form 2k
or 2k(2n − 1) for 0 ≤ k ≤ n − 1. Thus the positive divisors of p are as follows:
20,
21,
22,
. . .
2n−2,
2n−1,
20(2n − 1),
21(2n − 1),
22(2n − 1),
. . .
2n−2(2n − 1),
2n−1(2n − 1).
Notice that this list starts with 20 = 1 and ends with 2n−1(2n − 1) = p.
142
Proofs Involving Sets
If we add up all these divisors except for the last one (which equals p)
we get the following:
n−1
n−2
n−1
n−2
X 2k
X
X
X
+
2k(2n − 1) =
2k + (2n − 1)
2k
k=0
k=0
k=0
k=0
= (2n − 1) + (2n − 1)(2n−1 − 1)
(by Equation (8.1))
= [1 + (2n−1 − 1)](2n − 1)
= 2n−1(2n − 1)
=
p
(by Equation (8.2)).
This shows that the positive divisors of p that are less than p add up to p.
Therefore p is perfect, by definition of a perfect number. Thus p ∈ P, by
definition of P.
We have shown that p ∈ A implies p ∈ P, which means A ⊆ P.
■
Combined with the chart on the previous page, this theorem gives us
a new perfect number! The element p = 213−1(213 − 1) = 33, 550, 336 in A is
perfect.
Observe also that every element of A is a multiple of a power of 2, and
therefore even. But this does not necessarily mean every perfect number
is even, because we’ve only shown A ⊆ P, not A = P. For all we know there
may be odd perfect numbers in P − A that are not in A.
Are there any odd perfect numbers? No one knows.
In over 2000 years, no one has ever found an odd perfect number, nor
has anyone been able to prove that there are none. But it is known that the
set A does contain every even perfect number. This fact was first proved by
Euler, and we duplicate his reasoning in the next theorem, which proves
that A = E, where E is the set of all even perfect numbers. It is a good
example of how to prove two sets are equal.
For convenience, we are going to use a slightly different definition of a
perfect number. A number p ∈ N is perfect if its positive divisors add up
to 2p. For example, the number 6 is perfect since the sum of its divisors
is 1 + 2 + 3 + 6 = 2 · 6. This definition is simpler than the first one because
we do not have to stipulate that we are adding up the divisors that are
less than p. Instead we add in the last divisor p, and that has the effect
of adding an additional p, thereby doubling the answer.
Examples: Perfect Numbers
143
Theorem 8.2
ª
If A = © 2n−1(2n − 1) : n ∈ N, and 2n − 1 is prime and E =
© p ∈ N : p
ª
is perfect and even , then A = E.
Proof. To show that A = E, we need to show A ⊆ E and E ⊆ A.
First
we will show that A ⊆ E. Suppose p ∈ A. This means p is even,
because the definition of A shows that every element of A is a multiple of
a power of 2. Also, p is a perfect number because Theorem 8.1 states that
every element of A is also an element of P, hence perfect. Thus p is an
even perfect number, so p ∈ E. Therefore A ⊆ E.
Next we show that E ⊆ A. Suppose p ∈ E. This means p is an even
perfect number. Write the prime factorization of p as p = 2k3n1 5n2 7n2 . . .,
where some of the powers n1, n2, n3 . . . may be zero. But, as p is even, the
power k must be greater than zero. It follows p = 2k q for some positive
integer k and an odd integer q. Now, our aim is to show that p ∈ A, which
means we must show p has form p = 2n−1(2n −1). To get our current p = 2k q
closer to this form, let n = k + 1, so we now have
p = 2n−1q.
(8.3)
List the positive divisors of q as d1, d2, d3, . . . , dm. (Where d1 = 1 and dm = q.)
Then the divisors of p are:
20d1
20d2
20d3
. . .
20dm
21d1
21d2
21d3
. . .
21dm
22d1
22d2
22d3
. . .
22dm
23d1
23d2
23d3
. . .
23dm
..
.
.
.
.
..
..
..
2n−1d1
2n−1d2
2n−1d3
. . .
2n−1dm
Since p is perfect, these divisors add up to 2p. By Equation (8.3), their
sum is 2p = 2(2n−1 q) = 2n q. Adding the divisors column-by-column, we get
n−1
n−1
n−1
n−1
X 2kd
X
X
X
1 +
2k d2 +
2k d3 + ··· +
2k dm = 2n q.
k=0
k=0
k=0
k=0
Applying Equation (8.1), this becomes
(2n − 1)d1 + (2n − 1)d2 + (2n − 1)d3 + ··· + (2n − 1)dm = 2n q
(2n − 1)(d1 + d2 + d3 + ··· + dm) = 2n q
2n q
d1 + d2 + d3 + ··· + dm =
,
2n − 1
144
Proofs Involving Sets
so that
(2n − 1 + 1)q
(2n − 1)q + q
q
d1 + d2 + d3 + ··· + dm =
=
= q +
.
2n − 1
2n − 1
2n − 1
q
q
From this we see that 2n−1 is an integer. It follows that both q and 2n−1
are positive divisors of q. Since their sum equals the sum of all positive
Book of Proof Page 20
