30. Suppose a, b, p ∈ Z and p is prime. Prove that if p | ab then p | a or p | b.
(Suggestion: Use the proposition on page 126.)
31. If n ∈ Z, then gcd(n, n + 1) = 1.
32. If n ∈ Z, then gcd(n, n + 2) ∈ ©1,2ª.
33. If n ∈ Z, then gcd(2n + 1,4n2 + 1) = 1.
34. If gcd(a, c) = gcd(b, c) = 1, then gcd(ab, c) = 1.
(Suggestion: Use the proposition on page 126.)
35. Suppose a, b ∈ N. Then a = gcd(a, b) if and only if a | b.
36. Suppose a, b ∈ N. Then a = lcm(a, b) if and only if b | a.
CHAPTER
8
Proofs Involving Sets
tudents in their first advanced mathematics classes are often surprised
S by the extensive role that sets play and by the fact that most of the
proofs they encounter are proofs about sets. Perhaps you’ve already seen
such proofs in your linear algebra course, where a vector space was
defined to be a set of objects (called vectors) that obey certain properties.
Your text proved many things about vector spaces, such as the fact that
the intersection of two vector spaces is also a vector space, and the proofs
used ideas from set theory. As you go deeper into mathematics, you will
encounter more and more ideas, theorems and proofs that involve sets.
The purpose of this chapter is to give you a foundation that will prepare
you for this new outlook.
We will discuss how to show that an object is an element of a set, how
to prove one set is a subset of another and how to prove two sets are
equal. As you read this chapter, you may need to occasionally refer back
to Chapter 1 to refresh your memory. For your convenience, the main
definitions from Chapter 1 are summarized below. If A and B are sets,
then:
A × B = ©(x, y) : x ∈ A, y ∈ Bª,
A ∪ B = ©x : (x ∈ A) ∨ (x ∈ B)ª,
A ∩ B = ©x : (x ∈ A) ∧ (x ∈ B)ª,
A − B = ©x : (x ∈ A) ∧ (x ∉ B)ª,
A
= U − A.
Recall that A ⊆ B means that every element of A is also an element of B.
8.1 How to Prove a ∈ A
We will begin with a review of set-builder notation, and then review how
to show that a given object a is an element of some set A.
132
Proofs Involving Sets
Generally, a set A will be expressed in set-builder notation A = ©x : P(x)ª,
where P(x) is some statement (or open sentence) about x. The set A is
understood to have as elements all those things x for which P(x) is true.
For example,
©x : x
ª
is an odd integer = © . . . , −5, −3, −1, 1, 3, 5, . . . ª.
A common variation of this notation is to express a set as A = ©x ∈ S : P(x)ª.
Here it is understood that A consists of all elements x of the (predetermined)
set S for which P(x) is true. Keep in mind that, depending on context, x
could be any kind of object (integer, ordered pair, set, function, etc.). There
is also nothing special about the particular variable x; any reasonable
symbol x, y, k, etc., would do. Some examples follow.
©n ∈ Z : n
ª
is odd
= © . . . , −5, −3, −1, 1, 3, 5, . . . ª
©x ∈ N : 6| xª = ©6,12,18,24,30,...ª
©(a, b) ∈ Z × Z : b = a + 5ª = ©...,(−2,3),(−1,4),(0,5),(1,6),...ª
© X ∈ P(Z) : |X| = 1ª = ©...,© − 1ª,©0ª,©1ª,©2ª,©3ª,©4ª,...ª
Now it should be clear how to prove that an object a belongs to a set
©x : P(x)ª
©
. Since x : P(x)ª consists of all things x for which P(x) is true, to
show that a ∈ ©x : P(x)ª we just need to show that P(a) is true. Likewise, to
show a ∈ ©x ∈ S : P(x)ª, we need to confirm that a ∈ S and that P(a) is true.
These ideas are summarized below. However, you should not memorize
these methods, you should understand them. With contemplation and
practice, using them becomes natural and intuitive.
How to show a ∈ ©x : P(x)ª
How to show a ∈ ©x ∈ S : P(x)ª
Show that P(a) is true.
1. Verify that a ∈ S.
2. Show that P(a) is true.
Example 8.1
Let’s investigate elements of A = ©x : x ∈ N and 7 | xª. This set
has form A = ©x : P(x)ª where P(x) is the open sentence (x ∈ N) ∧ (7 | x). Thus
21 ∈ A because P(21) is true. Similarly, 7,14,28,35, etc., are all elements of
A. But 8 ∉ A (for example) because P(8) is false. Likewise −14 ∉ A because
P(−14) is false.
Example 8.2
Consider the set A = ©X ∈ P(N) : |X | = 3ª. We know that
©4,13,45ª ∈ A
©
¯©
©
because 4, 13, 45ª ∈ P(N) and ¯ 4, 13, 45ª¯¯ = 3. Also 1, 2, 3ª ∈ A,
©10,854,3ª ∈ A
©
¯©
, etc. However 1, 2, 3, 4ª ∉ A because ¯ 1, 2, 3, 4ª¯¯ 6= 3. Further,
© − 1,2,3ª ∉ A
©
because
− 1, 2, 3ª ∉ P(N).
How to Prove A ⊆ B
133
Example 8.3
Consider the set B = ©(x, y) ∈ Z × Z : x ≡ y (mod 5)ª. Notice
(8, 23) ∈ B because (8,23) ∈ Z × Z and 8 ≡ 23 (mod 5). Likewise, (100,75) ∈ B,
(102, 77) ∈ B, etc., but (6,10) ∉ B.
Now suppose n ∈ Z and consider the ordered pair (4n + 3, 9n − 2). Does
this ordered pair belong to B?
To answer this, we first observe that
(4n+3,9n−2) ∈ Z×Z. Next, we observe that (4n+3)−(9n−2) = −5n+5 = 5(1−n),
so 5 | ¡(4n+3)−(9n−2)¢, which means (4n+3) ≡ (9n−2) (mod 5). Therefore we
have established that (4n + 3, 9n − 2) meets the requirements for belonging
to B, so (4n + 3, 9n − 2) ∈ B for every n ∈ Z.
Example 8.4
This illustrates another common way of defining a set.
Consider the set C = ©3x3 + 2 : x ∈ Zª. Elements of this set consist of all the
values 3x3 + 2 where x is an integer. Thus −22 ∈ C because −22 = 3(−2)3 + 2.
1
You can confirm −1 ∈ C and 5 ∈ C, etc. Also 0 ∉ C and 2 ∉ C, etc.
8.2 How to Prove A ⊆ B
In this course (and more importantly, beyond it) you will encounter many
circumstances where it is necessary to prove that one set is a subset of an-
other. This section explains how to do this. The methods we discuss should
improve your skills in both writing your own proofs and in comprehending
the proofs that you read.
Recall (Definition 1.3) that if A and B are sets, then A ⊆ B means that
every element of A is also an element of B. In other words, it means if
a ∈ A , then a ∈ B . Therefore to prove that A ⊆ B, we just need to prove that
the conditional statement
“If a ∈ A , then a ∈ B ”
is true. This can be proved directly, by assuming a ∈ A and deducing a ∈ B.
The contrapositive approach is another option: Assume a ∉ B and deduce
a ∉ A. Each of these two approaches is outlined below.
How to Prove A ⊆ B
How to Prove A ⊆ B
(Direct approach)
(Contrapositive approach)
Proof. Suppose a ∈ A.
Proof. Suppose a ∉ B.
..
.
.
..
Therefore a ∈ B.
Therefore a ∉ A.
Thus a ∈ A implies a ∈ B,
Thus a ∉ B implies a ∉ A,
so it follows that A ⊆ B.
■
so it follows that A ⊆ B.
■
134
Proofs Involving Sets
In practice, the direct approach usually results in the most straight-
forward and easy proof, though occasionally the contrapositive is the
most expedient. (You can even prove A ⊆ B by contradiction: Assume
(a ∈ A) ∧ (a ∉ B), and deduce a contradiction.) The remainder of this section
consists of examples with occasional commentary. Unless stated otherwise,
we will use the direct approach in all proofs; pay special attention to how
the above outline for the direct approach is used.
Example 8.5
©
Prove that x ∈ Z : 18 | xª ⊆ ©x ∈ Z : 6 | xª.
Proof. Suppose a ∈ ©x ∈ Z : 18| xª.
This means that a ∈ Z and 18 | a.
By definition of divisibility, there is an integer c for which a = 18c.
Consequently a = 6(3c), and from this we deduce that 6 | a.
Therefore a is one of the integers that 6 divides, so a ∈ ©x ∈ Z : 6 | xª.
We’ve shown a ∈ ©x ∈ Z : 18 | xª implies a ∈ ©n ∈ Z : 6 | xª, so it follows that
©x ∈ Z : 18| xª ⊆ ©x ∈ Z : 6| xª.
■
Example 8.6
©
Prove that x ∈ Z : 2 | xª ∩ ©x ∈ Z : 9 | xª ⊆ ©x ∈ Z : 6 | xª.
Proof. Suppose a ∈ ©x ∈ Z : 2| xª ∩ ©x ∈ Z : 9| xª.
By definition of intersection, this means a ∈ ©x ∈ Z : 2 | xª and a ∈ ©x ∈ Z : 9 | xª.
Since a ∈ ©x ∈ Z : 2 | xª we know 2 | a, so a = 2c for some c ∈ Z. Thus a is even.
Since a ∈ ©x ∈ Z : 9 | xª we know 9 | a, so a = 9d for some d ∈ Z.
As a is even, a = 9d implies d is even. (Otherwise a = 9d would be odd.)
Then d = 2e for some integer e, and we have a = 9d = 9(2e) = 6(3e).
From a = 6(3e), we conclude 6 | a, and this means a ∈ ©x ∈ Z : 6 | xª.
We have shown that a ∈ ©x ∈ Z : 2 | xª ∩ ©x ∈ Z : 9 | xª implies a ∈ ©x ∈ Z : 6 | xª,
©
so it follows that x ∈ Z : 2 | xª ∩ ©x ∈ Z : 9 | xª ⊆ ©x ∈ Z : 6 | xª.
■
Example 8.7
©
Show (x, y) ∈ Z×Z : x ≡ y (mod 6)ª ⊆ ©(x, y) ∈ Z×Z : x ≡ y (mod 3)ª.
Proof. Suppose (a, b) ∈ ©(x, y) ∈ Z × Z : x ≡ y (mod 6)ª.
This means (a, b) ∈ Z × Z and a ≡ b (mod 6).
Consequently 6 |(a − b), so a − b = 6c for some integer c.
It follows that a − b = 3(2c), and this means 3 |(a − b), so a ≡ b (mod 3).
Thus (a, b) ∈ ©(x, y) ∈ Z × Z : x ≡ y (mod 3)ª.
We’ve now seen that (a, b) ∈ ©(x, y) ∈ Z × Z : x ≡ y (mod 6)ª implies (a, b) ∈
©(x, y) ∈ Z × Z : x ≡ y (
©
mod 3)ª, so it follows that (x, y) ∈ Z × Z : x ≡ y (mod 6)ª ⊆
©(x, y) ∈ Z × Z : x ≡ y (mod 3)ª.
■
How to Prove A ⊆ B
135
Some statements involving subsets are transparent enough that we
often accept (and use) them without proof. For example, if A and B are any
sets, then it’s very easy to confirm A ∩ B ⊆ A. (Reason: Suppose x ∈ A ∩ B.
Then x ∈ A and x ∈ B by definition of intersection, so in particular x ∈ A.
Thus x ∈ A ∩ B implies x ∈ A, so A ∩ B ⊆ A.) Other statements of this nature
include A ⊆ A ∪ B and A − B ⊆ A, as well as conditional statements such as
¡(A ⊆ B) ∧ (B ⊆ C)¢ ⇒ (A ⊆ C) and (X ⊆ A) ⇒ (X ⊆ A ∪ B). Our point of view in
this text is that we do not need to prove such obvious statements unless we
are explicitly asked to do so in an exercise. (Still, you should do some quick
mental proofs to convince yourself that the above statements are true. If
you don’t see that A ∩ B ⊆ A is true but that A ⊆ A ∩ B is not necessarily
true, then you need to spend more time on this topic.)
The next example will show that if A and B are sets, then P(A)∪P(B) ⊆
P(A ∪ B). Before beginning our proof, let’s look at an example to see if
this statement really makes sense. Suppose A = ©1, 2ª and B = ©2, 3ª. Then
P(A)∪P(B) = ©;,©1ª,©2ª,©1,2ªª∪©;,©2ª,©3ª,©2,3ªª
= ©;, ©1ª, ©2ª, ©3ª, ©1, 2ª, ©2, 3ªª.
Also P(A∪B) = P(©1, 2, 3ª) = ©;, ©1ª, ©2ª, ©3ª, ©1, 2ª, ©2, 3ª, ©1, 3ª, ©1, 2, 3ªª. Thus,
even though P(A)∪P(B) 6= P(A ∪B), it is true that P(A)∪P(B) ⊆ P(A ∪B)
for this particular A and B. Now let’s prove P(A) ∪ P(B) ⊆ P(A ∪ B) no
matter what sets A and B are.
Example 8.8
Prove that if A and B are sets, then P(A)∪P(B) ⊆ P(A∪B).
Proof. Suppose X ∈ P(A) ∪ P(B).
By definition of union, this means X ∈ P(A) or X ∈ P(B).
Therefore X ⊆ A or X ⊆ B (by definition of power sets). We consider cases.
Case 1. Suppose X ⊆ A. Then X ⊆ A ∪ B, and this means X ∈ P(A ∪ B).
Case 2. Suppose X ⊆ B. Then X ⊆ A ∪ B, and this means X ∈ P(A ∪ B).
(We do not need to consider the case where X ⊆ A and X ⊆ B because that
is taken care of by either of cases 1 or 2.) The above cases show that
X ∈ P(A ∪ B).
Thus we’ve shown that X ∈ P(A) ∪ P(B) implies X ∈ P(A ∪ B), and this
completes the proof that P(A) ∪ P(B) ⊆ P(A ∪ B).
■
In our next example, we prove a conditional statement. Direct proof is
used, and in the process we use our new technique for showing A ⊆ B.
136
Proofs Involving Sets
Example 8.9
Suppose A and B are sets. If P(A) ⊆ P(B), then A ⊆ B.
Proof. We use direct proof. Assume P(A) ⊆ P(B).
Based on this assumption, we must now show that A ⊆ B.
To show A ⊆ B, suppose that a ∈ A.
©
©
Then the one-element set aª is a subset of A, so aª ∈ P(A).
©
But then, since P(A) ⊆ P(B), it follows that aª ∈ P(B).
©
This means that aª ⊆ B, hence a ∈ B.
We’ve shown that a ∈ A implies a ∈ B, so therefore A ⊆ B.
■
8.3 How to Prove A = B
In proofs it is often necessary to show that two sets are equal. There is a
standard way of doing this. Suppose we want to show A = B. If we show
A ⊆ B, then every element of A is also in B, but there is still a possibility
that B could have some elements that are not in A, so we can’t conclude
A = B. But if in addition we also show B ⊆ A, then B can’t contain anything
that is not in A, so A = B. This is the standard procedure for proving A = B:
Prove both A ⊆ B and B ⊆ A.
How to Prove A = B
Proof.
[Prove that A ⊆ B.]
[Prove that B ⊆ A.]
Therefore, since A ⊆ B and B ⊆ A,
it follows that A = B.
■
Example 8.10
©
Prove that n ∈ Z : 35 | nª = ©n ∈ Z : 5 | nª ∩ ©n ∈ Z : 7 | nª.
Proof.
©
First we show
n ∈ Z : 35|
nª ⊆ ©n ∈ Z : 5| nª ∩ ©n ∈ Z : 7| nª. Suppose
a ∈ ©n ∈ Z : 35| nª. This means 35| a, so a = 35c for some c ∈ Z. Thus a = 5(7c)
and a = 7(5c). From a = 5(7c) it follows that 5 | a, so a ∈ ©n ∈ Z : 5 | nª. From
a = 7(5c) it follows that 7| a, which means a ∈ ©n ∈ Z : 7| nª. As a belongs
©
©
to both n ∈ Z : 5 | nª and n ∈ Z : 7 | nª, we get a ∈ ©n ∈ Z : 5 | nª ∩ ©n ∈ Z : 7 | nª.
©
Thus we’ve shown that n ∈ Z : 35 | nª ⊆ ©n ∈ Z : 5 | nª ∩ ©n ∈ Z : 7 | nª.
©
Next we show n ∈ Z : 5 | nª ∩ ©n ∈ Z : 7 | nª ⊆ ©n ∈ Z : 35 | nª. Suppose that
a ∈ ©n ∈ Z : 5| nª ∩ ©n ∈ Z : 7| nª. By definition of intersection, this means that
a ∈ ©n ∈ Z : 5| nª and a ∈ ©n ∈ Z : 7| nª. Therefore it follows that 5| a and 7| a.
By definition of divisibility, there are integers c and d with a = 5c and a = 7d.
Then a has both 5 and 7 as prime factors, so the prime factorization of a
How to Prove A = B
137
must include factors of 5 and 7. Hence 5·7 = 35 divides a, so a ∈ ©n ∈ Z : 35 | nª.
©
We’ve now shown that n ∈ Z : 5 | nª ∩ ©n ∈ Z : 7 | nª ⊆ ©n ∈ Z : 35 | nª.
©
At this point we’ve shown that n ∈ Z : 35 | nª ⊆ ©n ∈ Z : 5 | nª ∩ ©n ∈ Z : 7 | nª
©
©
and n ∈ Z : 5 | nª∩©n ∈ Z : 7 | nª ⊆ ©n ∈ Z : 35 | nª, so we’ve proved n ∈ Z : 35 | nª =
©n ∈ Z : 5| nª ∩ ©n ∈ Z : 7| nª.
■
You know from algebra that if c 6= 0 and ac = bc, then a = b. The next
example shows that an analogous statement holds for sets A, B and C. The
example asks us to prove a conditional statement. We will prove it with
direct proof. In carrying out the process of direct proof, we will have to
use the new techniques from this section.
Example 8.11
Suppose A, B, and C are sets, and C 6= ;. Prove that if
A × C = B × C, then A = B.
Proof. Suppose A × C = B × C. We must now show A = B.
First we will show A ⊆ B. Suppose a ∈ A. Since C 6= ;, there exists
an element c ∈ C. Thus, since a ∈ A and c ∈ C, we have (a, c) ∈ A × C, by
definition of the Cartesian product. But then, since A × C = B × C, it follows
that (a, c) ∈ B × C. Again by definition of the Cartesian product, it follows
that a ∈ B. We have shown a ∈ A implies a ∈ B, so A ⊆ B.
Next we show B ⊆ A. We use the same argument as above, with the
roles of A and B reversed. Suppose a ∈ B. Since C 6= ;, there exists an
Book of Proof Page 19
