Chapter 1

Sets and Relations

1.2.1 Explain why 2 ∈ {1, 2, 3}.

Solution: 2 ∈ {1, 2, 3} by definition: 2 is an element of {1, 2, 3}.

1.2.2 Is {1, 2} ∈ {{1, 2, 3}, {1, 3}, 1, 2}? Justify your answer.
Solution: {1, 2} ∈ / {{1, 2, 3}, {1, 3}, 1, 2} since it does not appear as a member of the
given set.

1.2.3 Try to devise a set which is a member of itself.

Solution: The set of all sets.

1.2.4 Give an example of sets A, B, and C such that A ∈ B, B ∈ C, and A ∈/ C.

Solution: A = {1}. B = {1, {1}}. C = {1, {1, {1}}}. Then A ∈ B, B ∈ C, but A ∈
/ C.

1.2.5 Describe in prose each of the following sets.

Solution:

(a) {x ∈ Z | x is divisible by 2 and x is divisible by 3}

Solution: All integer multiples of 6.
(b) {x | x ∈ A and x ∈ B}
Solution: All elements common to sets A and B.
(c) {x | x ∈ A or x ∈ B}
Solution: All elements from set A and from set B.
(d) {x ∈ Z+ | x ∈ {x ∈ Z | for some integer y, x = 2y} and x ∈ {x ∈ Z |
for some integer y, x = 3y}}
Solution: All positive integer multiples of 6.
(e) {x2 | x is a prime}
Solution: The squares of all prime numbers.
(f) {a/b ∈ Q | a + b = 1 and a, b ∈ Q}
Solution: All ratios of rational numbers whose numerator and denominator sum
to 1; i.e. all rational numbers.

1
 (g) {(x, y) ∈ R2 | x2 + y 2 = 1}
Solution: All points on the unit circle.
(h) {(x, y) ∈ R2 | y = 2x and y = 3x}
Solution: The single point (0,0).
1.2.6 Prove that if a, b, c, and d are any objects, not necessarily distinct from one another,
then {{a}, {a, b}} = {{c}, {c, d}} iff both a = c and b = d.
Solution: (⇒) Let {{a}, {a, b}} = {{c}, {c, d}}. Then {{a}, {a, b}} ⊆ {{c}, {c, d}}
and so in particular {a} ∈ {{c}, {c, d}}. Suppose c = d. Then {{c}, {c, d}} =
{{c}, {c, c}} = {{c}, {c}} = {{c}} and therefore {a} ∈ {{c}} ⇒ {a} = {c} ⇒ {a} ⊆
{c} ⇒ a ∈ {c} ⇒ a = c. Then since {{a}, {a, b}} ⊆ {{c}, {c, d}} = {{c}} = {{a}} we
also have that {a, b} ∈ {{a}} ⇒ {a, b} = {a} ⇒ {a, b} ⊆ {a} ⇒ b ∈ {a} ⇒ a = b.
Now suppose c 6= d. Since {a} ∈ {{c}, {c, d}} ⇒ {a} = {c} ⇒ a = c. By
{{a}, {a, b}} ⊆ {{c}, {c, d}} we also have that {a, b} = {c, b} ∈ {{c}, {c, d}} and
so {c, b} = {c, d} ⇒ b = d.
(⇐) Let a = c and b = d. Then {{a}, {a, b}} = {{c}, {c, d}}. 

1.3.1 Prove each of the following, using any properties of numbers that may be needed.
(a) {x ∈ Z | for an integer y, x = 6y} = {x ∈ Z | for integers u and v, x =
2u and x = 3v}.
Solution: Let a ∈ {x ∈ Z | for an integer y, x = 6y}. Then a = 6b for an integer
b. Then a = 2 · 3b and a = 3 · 2b. Since b is an integer, 3b and 2b are also integers.
Therefore a ∈ {x ∈ Z | for integers u and v, x = 2u and x = 3v} and so {x ∈ Z |
for an integer y, x = 6y} ⊆ {x ∈ Z | for integers u and v, x = 2u and x = 3v}.
Now let a ∈ {x ∈ Z | for integers u and v, x = 2u and x = 3v}. Then there
is an m and n such that a = 2m and a = 3n. Then m − n = a6 and so
a = 6(m − n). Since m and n are integers, m − n is also an integer and so a ∈
{x ∈ Z | for an integer y, x = 6y}. Therefore {x ∈ Z | for integers u and v, x =
2u and x = 3v} ⊆ {x ∈ Z | for an integer y, x = 6y}.
Thus {x ∈ Z | for an integer y, x = 6y} = {x ∈ Z | for integers u and v, x =
2u and x = 3v}. 
(b) {x ∈ R | for a real number y, x = y 2 } = {x ∈ R | x ≥ 0}
Solution: Let a ∈ {x ∈ R | for a real number y, x = y 2 }. Then a = b2 for
some b ∈ R. If b = 0 then a = 0. Otherwise, a > 0 since the square of a
nonzero real number is positive. Thus a ∈ {x ∈ R | x ≥ 0} and therefore
{x ∈ R | for a real number y, x = y 2 } ⊆ {x ∈ R | x ≥ 0}.
Now let a ∈ {x ∈ R | x ≥ 0}. √ Then a ≥ 0. Then we may find a b ∈ R such
that a = b2 : simply pick b = a ∈ R. (The square root of any nonnegative real
number is again a real number.) Then a ∈ {x ∈ R | for a real number y, x = y 2 }
and therefore {x ∈ R | x ≥ 0} ⊆ {x ∈ R | for a real number y, x = y 2 }.
Thus {x ∈ R | for a real number y, x = y 2 } = {x ∈ R | x ≥ 0}. 

2
 (c) {x ∈ Z | for an integer y, x = 6y} ⊆ {x ∈ Z | for an integer y, x = 2y}.
Solution: Let a ∈ {x ∈ Z | for an integer y, x = 6y}. Then a = 6b for some
integer b. Then a = 2 · 3b. Since b is an integer, 3b is also an integer. Therefore
a ∈ {x ∈ Z | for an integer y, x = 2y}. Thus {x ∈ Z | for an integer y, x =
6y} ⊆ {x ∈ Z | for an integer y, x = 2y}. 

1.3.2 Prove each of the following for sets A, B, and C.

(a) If A ⊆ B and B ⊆ C, then A ⊆ C.

Solution: Suppose A ⊆ B and B ⊆ C. Then for any a ∈ A we have that a ∈ B
and since a ∈ B we have that a ∈ C. Thus a ∈ C whenever a ∈ A and therefore
A ⊆ C.
(b) If A ⊆ B and B ⊂ C, then A ⊂ C.
Solution: Suppose A ⊆ B and B ⊂ C. Take the case when A = B. Since B ⊂ C
we have that A ⊂ C. Now take the case when A ⊂ B. For any a ∈ A we have
that a ∈ B. Since B ⊂ C we have that a ∈ C. Then A ⊆ C. Since B ⊂ C,
we know that there is some element c ∈ C such that c ∈
/ B and since A ⊂ B we
know that c ∈
/ A and so A 6= C. Therefore A ⊂ C.
(c) If A ⊂ B and B ⊆ C, then A ⊂ C.
Solution: Suppose A ⊂ B and B ⊆ C. Take the case when B = C. Since A ⊂ B
we have that A ⊂ C. Now take the case when B ⊂ C. For any a ∈ A we have
that a ∈ B. Since B ⊂ C we have that a ∈ C. Then A ⊆ C. Since B ⊂ C, we
also know that there is some element c ∈ C such that c ∈
/ B and since A ⊂ B we
know that c ∈
/ A and so A 6= C. Therefore A ⊂ C.
(d) If A ⊂ B and B ⊂ C, then A ⊂ C.
Solution: Suppose A ⊂ B and B ⊂ C. For any a ∈ A we have that a ∈ B. Since
B ⊂ C we have that a ∈ C. Then A ⊂ C. Since B ⊂ C, we know that there is
some element c ∈ C such that c ∈
/ B and since A ⊂ B we know that c ∈
/ A and
so A 6= C. Therefore A ⊂ C.

1.3.3 Give an example of sets A, B, C, D, and E which satisfy the following conditions si-
multaneously: A ⊂ B, B ∈ C, C ⊂ D, and D ⊂ E.
Solution: Let A = ∅, B = {∅}, C = {{∅}}, D = {∅, {∅}}, and E = {∅, {∅}, {{∅}}}.

1.3.4 Which of the following are true for all sets A, B, and C?

(a) If A ∈
/ B and B ∈/ C, then A ∈
/ C.
Solution: False: Let A = ∅, B = {0} and C = {∅}.
(b) If A 6= B and B 6= C, then A 6= C.
Solution: False: Let A = R, B = Z and C = R.
(c) If A ∈ B and B 6⊆ C, then A ∈
/ C.
Solution: False: Let A = ∅, B = {∅, 0} and C = {∅, 1}.

3
 (d) If A ⊂ B and B ⊆ C, then C 6⊆ A.
Solution: True: Suppose A ⊂ B and B ⊆ C. Since A ⊂ B, there is some b ∈ B
such that b ∈
/ A. Since B ⊆ C we have that this b ∈ C and thus there is a c ∈ C
such that c ∈
/ A. Therefore C 6⊆ A.
(e) If A ⊂ B and B ⊂ C, then A ⊂ C.
Solution: True: Suppose A ⊂ B and B ⊂ C. Then for any a ∈ A we have that
a ∈ B. Since a ∈ B we have that a ∈ C. Therefore A ⊆ C. Since B ⊂ C we
have that there is some c ∈ C such that c ∈
/ B. Since A ⊂ B we have that c ∈
/ A.
Therefore A 6= C and so A ⊂ C.

1.3.5 Show that for every set A, A ⊆ ∅ iff A = ∅.

Solution: (⇒) Suppose A ⊆ ∅. Then for any a ∈ A we have that a ∈ ∅. But since the
empty set has no members, no such a can exist. Therefore A has no members and so
A = ∅. (⇐) Suppose A = ∅. Then A has no members and so, certainly, for all a ∈ A
we have that a ∈ B, for any set B. Therefore A ⊆ B. Letting B = ∅, we conclude
that A ⊆ ∅. 

1.3.6 Let A1 , A2 , . . . , An be n sets. Show that

A1 ⊆ A2 ⊆ · · · ⊆ An ⊆ A1 iff A1 = A2 = · · · = An .

Solution: (⇐) Suppose sets A1 = A2 = · · · = An . Then clearly Ai ⊆ Ai+1 for all

1 ≤ i ≤ n − 1 and An ⊆ A1 . Therefore A1 ⊆ A2 ⊆ · · · ⊆ An ⊆ A1 .
(⇒) Suppose A1 ⊆ A2 ⊆ · · · ⊆ An ⊆ A1 . Then for any a ∈ A1 we have that a ∈ A2 ,
a ∈ A3 , . . . , a ∈ An and so A1 ⊆ An . But since An ⊆ A1 we must have that A1 = An .
Therefore A1 ⊆ A2 ⊆ · · · ⊆ An−1 ⊆ A1 . Repeating this argument n − 2 times for
j = n − 1, n − 2, . . . , 2 we find that for any a ∈ A1 we have that a ∈ Aj and therefore
A1 ⊆ Aj . But we also have that Aj ⊆ A1 and so A1 = Aj . Finally, we conclude that
A1 = A2 = · · · = An . 

1.3.7 Give several examples of a set X such that each element of X is a subset of X.
Solution: X1 = ∅. X2 = {∅}. X3 =?

1.3.8 List the members of P(A) if A = {{1, 2}, {3}, 1}.

Solution: P(A) = {A, {{1, 2}, {3}}, {{1, 2}, 1}, {{3}, 1}, {{1, 2}}, {{3}}, {1}, ∅}

1.3.9 For each positive integer n, give an example of a set An of n elements such that for
each pair of elements of An , one member is an element of the other.
Solution: Let A0 = ∅ and A1 = {A0 }. For n ≥ 2, let An = {A0 , A1 , . . . , An−1 }.

1.4.1 Prove that for all sets A and B, ∅ ⊆ A ∩ B ⊆ A ∪ B.

Solution: Let A and B be any sets. Since the empty set has no members, it’s clear

4
 that for all x ∈ ∅ we have that x ∈ C for any set C. Since A ∩ B is a set, we have that
∅ ⊆ A ∩ B. Now take any x ∈ A ∩ B. Then x ∈ A and x ∈ B and so, clearly, x ∈ A
or x ∈ B. Therefore x ∈ A ∪ B and so A ∩ B ⊆ A ∪ B. Thus ∅ ⊆ A ∩ B ⊆ A ∪ B.

1.4.2 Let Z be the universal set, and let

A = {x ∈ Z | for some positive integer y, x = 2y},

B = {x ∈ Z | for some positive integer y, x = 2y − 1},
C = {x ∈ Z | x < 10}.

Describe A, A ∪ B, A − C, and C − (A ∪ B), either in prose or by a defining property.

Solution:

• A = {x ∈ Z | x < 1} ∪ B
• A ∪ B = {x ∈ Z | x < 1}
• A − C = {2, 3, 6, 8}
• C − (A ∪ B) = {x ∈ Z | x < 1}

1.4.3 Consider the following subsets of Z+ , the set of positive integers:

A = {x ∈ Z+ | for some integer y, x = 2y},

B = {x ∈ Z+ | for some integer y, x = 2y + 1},
C = {x ∈ Z+ | for some integer y, x = 3y}.

(a) Describe A ∩ C, B ∪ C, and B − C.

Solution:
• A ∩ C = {x ∈ Z+ | for some integer y, x = 6y}. This is the set of all positive
multiples of both 2 and 3 (i.e. all positive multiples of 6).
• B ∪ C = B ∪ {x ∈ Z+ | for some integer y, x = 6y}. This is the set of
all positive odd integers along with all even positive multiples of 3 (i.e. all
positive multiples of 6).
• B − C = {x ∈ Z+ | for some integer y, x = 3y + 1 or x = 3y + 2}. This is
the set of all positive integers which are not divisible by 3.
(b) Verify that A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Solution: In this example:
• A ∩ (B ∪ C) = A ∩ C
• A ∩ B = ∅ ⇒ (A ∩ B) ∪ (A ∩ C) = A ∩ C
A general proof:
Assume x ∈ A ∩ (B ∪ C). Then by definition of set intersection, x ∈ A and
x ∈ B ∪ C. By the definition of set union, x ∈ B or x ∈ C. If x ∈ B then
we have that x ∈ A ∩ B since x ∈ A. Otherwise, if x ∈ C then we have that

5
 x ∈ A ∩ C since x ∈ A. In both cases we know that x ∈ (A ∩ B) ∪ (A ∩ C) since
both A ∩ B ⊆ (A ∩ B) ∪ (A ∩ C) and A ∩ C ⊆ (A ∩ B) ∪ (A ∩ C). Therefore
A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C). Now assume x ∈ (A ∩ B) ∪ (A ∩ C). By the
definition of set union, x ∈ A∩B or x ∈ A∩C. If x ∈ A∩B then by the definition
of set intersection, we have that x ∈ A and x ∈ B. Since B ⊆ B ∪ C we know that
x ∈ B ∪ C. Thus x ∈ A ∩ (B ∪ C). Otherwise if x ∈ A ∩ C then by the definition
of set intersection, we have that x ∈ A and x ∈ C. Since C ⊆ B ∪ C we know that
x ∈ B ∪ C. Thus x ∈ A ∩ (B ∪ C). Therefore (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C).
Therefore (A ∩ B) ∪ (A ∩ C) = A ∩ (B ∪ C). 
1.4.4 If A is any set, what are each of the following sets? A ∩ ∅, A ∪ ∅, A − ∅, A − A, ∅ − A.
Solution:
• A ∩ ∅ = {x | x ∈ A and x ∈ ∅} = ∅.
• A ∪ ∅ = {x | x ∈ A or x ∈ ∅} = A.
• A − ∅ = {x | x ∈ A and x ∈
/ ∅} = A.
• A − A = {x | x ∈ A and x ∈
/ A} = ∅.
• ∅ − A = {x | x ∈ ∅ and x ∈
/ A} = ∅.
1.4.5 Determine ∅ ∩ {∅}, {∅} ∩ {∅}, {∅, {∅}} − ∅, {∅, {∅}} − {∅}, {∅, {∅}} − {{∅}}
Solution:
• ∅ ∩ {∅} = {x | x ∈ ∅ and x ∈ {∅}} = ∅.
• {∅} ∩ {∅} = {x | x ∈ {∅} and x ∈ {∅}} = {x | x ∈ {∅}} = {∅}.
• {∅, {∅}} − ∅ = {x | x ∈ {∅, {∅}} and x ∈
/ ∅} = {∅, {∅}}.
• {∅, {∅}} − {∅} = {x | x ∈ {∅, {∅}} and x ∈
/ {∅}} = {{∅}}.
• {∅, {∅}} − {{∅}} = {x | x ∈ {∅, {∅}} and x ∈
/ {{∅}}} = {∅}.
1.4.6 Suppose A and B are subsets of U . Show that in each of (a), (b), and (c) below, if any
one of the relations stated holds, then each of the others holds.
(a) A ⊆ B, A ⊇ B, A ∪ B = B, A ∩ B = A.
(b) A ∩ B = ∅, A ⊆ B, B ⊆ A.
(c) A ∪ B = U, A ⊆ B, B ⊆ A.
Solution:

(a) i. Assume A ⊆ B.
• Take x ∈
/ B. Assume x ∈ A. Since A ⊆ B we have that x ∈ B. Then by
contradiction we must have that x ∈
/ A. Therefore B ⊆ A or A ⊇ B.
• Take x ∈ A ∪ B. Then x ∈ A or x ∈ B. Assume x ∈ A. Then since
A ⊆ B we have that x ∈ B. Therefore A ∪ B ⊆ B. But since B ⊆ A ∪ B
we have that A ∪ B = B.

6
 • Take x ∈ A. Because A ⊆ B we have that x ∈ B. Since x ∈ A and x ∈ B
we have that x ∈ A ∩ B and therefore A ⊆ A ∩ B. But since A ∩ B ⊆ A,
we have A ∩ B = A.
ii. Assume A ⊇ B.
• Take x ∈ A. Assume x ∈ / B. Then because A ⊇ B we have that x ∈ / A.
Then by contradiction we must have that x ∈ B. Therefore A ⊆ B.
• Take x ∈ A ∪ B. Then by the definition of set union, x ∈ A or x ∈ B.
Assume x ∈ / B. Then because A ⊇ B we have that x ∈ / A. But then
since x ∈
/ A and x ∈ / B we have that x ∈/ A ∪ B. By contradiction we
must have that x ∈ B and thus A ∪ B ⊆ B. But since B ⊆ A ∪ B we
have A ∪ B = B.
• Take x ∈ A. Assume x ∈ / B. Then because A ⊇ B we have that x ∈ / A.
By contradiction, x ∈ B. Thus A ⊆ A ∩ B. But since A ∩ B ⊆ A we have
A ∩ B = A.
iii. Assume A ∪ B = B.
• Take x ∈ A. Then x ∈ A ∪ B = B and therefore A ⊆ B.
• Take x ∈/ B. Then x ∈/ A ∪ B and so x ∈
/ A. Therefore A ⊇ B.
• Take x ∈ A. Then x ∈ A∪B = B. Since x ∈ A and x ∈ B then x ∈ A∩B
and so A ⊆ A ∩ B. But since A ∩ B ⊆ A we have A ∩ B = A.
iv. Assume A ∩ B = A.
• Take x ∈ A. Then x ∈ A ∩ B and so x ∈ B. Therefore A ⊆ B.
• Take x ∈/ B. Then x ∈/ A ∩ B and so x ∈
/ A. Therefore A ⊇ B.
• Take x ∈ A ∪ B. Then x ∈ A or x ∈ B. Assume x ∈ / B. Then
x∈ / A ∩ B = A and so x ∈ / A ∪ B. By contradiction, we must have the
x ∈ B. Then A ∪ B ⊆ B. But since B ⊆ A ∪ B we have that A ∪ B = B.
(b) i. Assume A ∩ B = ∅.
• Take x ∈ A. Since A ∩ B = ∅, x ∈
/ B. Then A ⊆ B.
• Take x ∈ B. Since A ∩ B = ∅, x ∈
/ A. Then B ⊆ A.
ii. Assume A ⊆ B.
• Take x ∈ A. Then since A ⊆ B we have x ∈/ B. Now take x ∈ B. Assume
x ∈ A. But then since A ⊆ B we have x ∈/ B. By contradiction we must
have that x ∈
/ A. Thus x ∈ A ⇒ x ∈ / B and x ∈ B ⇒ x ∈ / A and so
A ∩ B = ∅.
• Take x ∈ B. Assume x ∈ A. Then since A ⊆ B we have that x ∈ / B.
Then by contradiction, we must have x ∈
/ A and so B ⊆ A.
iii. Assume B ⊆ A.
• Take x ∈ B. Then since B ⊆ A we have x ∈ / A. Now take x ∈ A and
assume x ∈ B. But since B ⊆ A we have x ∈ / A. Then by contradiction,
we must have that x ∈/ B. Thus x ∈ A ⇒ x ∈ / B and x ∈ B ⇒ x ∈ / A
and so A ∩ B = ∅.

7
 • Take x ∈ A. Assume x ∈ B. Then since B ⊆ A we have x ∈ / A. Then by
contradiction we must have that x ∈
/ B. Therefore A ⊆ B.
(c) i. Assume A ∪ B = U .
• Take x ∈/ A. Assume x ∈/ B. Then since x ∈
/ A and x ∈
/ B, we have that
x∈/ A ∪ B = U . But since A ⊆ U this is a contradiction. So we must
have that x ∈ B. Therefore A ⊆ B.
• Take x ∈/ B. Assume x ∈/ A. Then since x ∈
/ A and x ∈
/ B, we have that
x∈/ A ∪ B = U . But since B ⊆ U this is a contradiction. So we must
have that x ∈ A. Therefore B ⊆ A.
ii. Assume A ⊆ B.
• Take x ∈ U . Then either x ∈ A or x ∈ / A. Assume that x ∈ A. Then
x ∈ A ∪ B. Now assume that x ∈ / A. Then since A ⊆ B we have that
x ∈ B. Then x ∈ A ∪ B. Therefore U ⊆ A ∪ B. But since A ∪ B ⊆ U we
must have that A ∪ B = U .
• Take x ∈/ B. AssumeB ⊆ A
iii. Assume B ⊆ A.
• Take x ∈ U . Then x ∈ B or x ∈/ B. If x ∈ B then x ∈ A ∪ B. If x ∈
/B
then since B ⊆ A we have that x ∈ A and so x ∈ A ∪ B. Therefore
U ⊆ A ∪ B. But since A ∪ B ⊆ U we must have that A ∪ B = U .
• Take x ∈/ A and assume x ∈/ B. Then since B ⊆ A we have that x ∈ A.
Then by contradiction we must have that x ∈ B and so A ⊆ B.

1.4.7 Prove that for all sets A, B, and C,

(A ∩ B) ∪ C = A ∩ (B ∪ C) iff C ⊆ A.

Solution: (⇒) Assume (A ∩ B) ∪ C = A ∩ (B ∪ C). Let x ∈ C. Then x ∈ (A ∩ B) ∪ C.

Since (A ∩ B) ∪ C = A ∩ (B ∪ C) we have that x ∈ A ∩ (B ∪ C) and thus x ∈ A.
Therefore C ⊆ A.
(⇐) Assume C ⊆ A. Let x ∈ (A∩B)∪C. Then x ∈ A∩B or x ∈ C. Assume x ∈ A∩B.
Then x ∈ A and x ∈ B. Since x ∈ B then x ∈ B ∪ C. Since x ∈ A and x ∈ B ∪ C we
have that x ∈ A ∩ (B ∪ C). Now assume x ∈ C. Then x ∈ B ∪ C. Since C ⊆ A we also
have that x ∈ A. Thus x ∈ A ∩ (B ∪ C). Therefore (A ∩ B) ∪ C ⊆ A ∩ (B ∪ C). Now let
x ∈ A ∩ (B ∪ C). Then x ∈ A and x ∈ B ∪ C. Then x ∈ B or x ∈ C. Assume x ∈ B.
Then since x ∈ A and x ∈ B we have that x ∈ A ∩ B. Therefore x ∈ (A ∩ B) ∪ C.
Now assume x ∈ C. Then x ∈ (A ∩ B) ∪ C. Therefore A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ C and
so we can conclude that (A ∩ B) ∪ C = A ∩ (B ∪ C). 

1.4.8 Prove that for all sets A, B, and C,

(A − B) − C = (A − C) − (B − C).

8
 Solution: Let x ∈ (A − B) − C. Then x ∈ A − B and x ∈ / C. Since x ∈ A − B we
have that x ∈ A and x ∈/ B. Then since x ∈ A and x ∈/ C we have that x ∈ A − C.
Since x ∈
/ B we have that x ∈
/ B − C. Then since x ∈ A − C and x ∈/ B − C we have
that x ∈ (A − C) − (B − C). Now let x ∈ (A − C) − (B − C). Then x ∈ A − C and
x∈/ B − C. Then since x ∈ A − C we have that x ∈ A and x ∈/ C. Since x ∈/ B−C
we have that either x ∈
/ B or x ∈ C. But x ∈ C is a contradiction because x ∈
/ C.
Therefore x ∈
/ B. Then since x ∈ A and x ∈ / B we have that x ∈ A − B and since
x∈/ C we have that x ∈ (A − B) − C. Therefore (A − C) − (B − C) ⊆ (A − B) − C
and thus (A − B) − C = (A − C) − (B − C). 
1.4.9 (a) Draw the Venn diagram of the symmetric difference, A + B, of sets A and B.
Solution: ... TO DO ...
(b) Using a Venn diagram, show that the symmetric difference is a commutative and
associative operation.
Solution: ... TO DO ...
(c) Show that for every set A, A + A = ∅ and A + ∅ = A
Solution: Let A be a set. Let x ∈ A + A = (A − A) ∪ (A − A). Then x ∈ A − A =
{x | x ∈ A and x ∈
/ A} = ∅. Therefore A + A ⊆ ∅. Then since ∅ ⊆ A + A we have
that A + A = ∅. 
Let x ∈ A + ∅ = (A − ∅) ∪ (∅ − A). Then x ∈ A − ∅ or x ∈ ∅ − A. Assume
x ∈ ∅ − A. Then x ∈ ∅. But this is a contradiction and so we have that x ∈ A − ∅.
Then x ∈ A. Therefore A + ∅ ⊆ A. Now let x ∈ A. Since x ∈ / ∅ we have that
x ∈ A − ∅. Then x ∈ (A − ∅) ∪ (∅ − A) = A + ∅. Thus A ⊆ A + ∅ and therefore
A + ∅ = A. 
1.4.10 The Venn diagram for subsets A, B, and C of U , in general, divides the rectangle
representing U into eight nonoverlapping regions. Label each region with a combination
of A, B, and C which represents exactly that region.
Solution: ... TO DO ...
1.4.11 With the aid of a Venn diagram investigate the validity of each of the following infer-
ences:
(a) If A, B, and C are subsets of U such that A ∩ B ⊆ C and A ∪ C ⊆ B, then
A ∩ C = ∅.
Solution: ... TO DO ...
(b) If A, B, and C are subsets of U such that A ⊆ B ∪ C and B ⊆ A ∪ C, then B = ∅.
Solution: ... TO DO ...

1.5.1 Prove that parts 3’, 4’, and 5’ of Theorem 5.1 are identities
Solution:

9
 3’. Assume x ∈ A ∩ (B ∪ C). Then x ∈ A and x ∈ B ∪ C. If x ∈ B then since
x ∈ A we have x ∈ A ∩ B and so x ∈ (A ∩ B) ∪ (A ∩ C). Otherwise if x ∈ C
then since x ∈ A we have x ∈ A ∩ C and so x ∈ (A ∩ B) ∪ (A ∩ C). Therefore
A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C). Now assume x ∈ (A ∩ B) ∪ (A ∩ C). Then
x ∈ A ∩ B or x ∈ A ∩ C. If x ∈ A ∩ B then x ∈ A and x ∈ B. Since x ∈ B we
have x ∈ B ∪ C. Since we also have x ∈ A then x ∈ A ∩ (B ∪ C). Otherwise if
x ∈ A ∩ C then x ∈ A and x ∈ C. Since x ∈ C we have x ∈ B ∪ C. Since we also
have x ∈ A then x ∈ A ∩ (B ∪ C). Therefore (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C).
Hence A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

4’. Assume x ∈ A ∩ U . Then x ∈ A and x ∈ U . Therefore A ∩ U ⊆ A. Now assume

x ∈ A. Then since A ⊆ U we have x ∈ U and so x ∈ A ∩ U . Therefore A ⊆ A ∩ U .
Hence A ∩ U = A.

5’. Assume x ∈ A ∩ A. Then x ∈ A and x ∈ A. Since x ∈ A we have x ∈ / A. Since

/ A we have x ∈ ∅. Therefore A ∩ A ⊆ ∅. Since ∅ ⊆ X for any set
x ∈ A and x ∈
X we have ∅ ⊆ A ∩ A. Hence A ∩ A = ∅.

1.5.2 Prove the unprimed parts of Theorem 5.2 using the membership relations. Try to prove
the same results using only Theorem 5.1. In at least one such proof write out the dual
of each step to demonstrate that a proof of the dual results.
Solution:

6. using membership: Assume that A ∪ B = A for all A. Then, in particular, for

A = ∅ we have A ∪ B = ∅ ∪ B = ∅. Take x ∈ B. Then x ∈ ∅ ∪ B = ∅ and so
B ⊆ ∅. Now take x ∈ ∅. By ex falso quodlibet, we have x ∈ B. Therefore ∅ ⊆ B.
Thus B = ∅.
using Thm 5.1: Assume that A ∪ B = A for all A. Then, in particular, ∅ ∪ B = ∅.
Then

B =B∪∅ (5.1.4)
=∅∪B (5.1.2)
= ∅. (Consequence of assumption)

Therefore B = ∅.
dual proof: Assume that A ∩ B = A for all A. Then, in particular, U ∩ B = U .
Then

B =B∩U (5.1.4’)
=U ∩B (5.1.2’)
= U. (Consequence of assumption)

Therefore B = U .

10
7. using membership: Assume A ∪ B = U and A ∩ B = ∅. Take x ∈ B. Assume
x ∈ A. Then x ∈ A ∩ B = ∅. By contradiction, x ∈ / A and so x ∈ {y ∈ U | y ∈
/
A} = U − A = A. Therefore B ⊆ A. Now take x ∈ A. Then x ∈ / A. Assume
x∈/ B. Then x ∈/ A ∪ B = U . By contradiction, x ∈ B and so A ⊆ B. Therefore
B = A.
using Thm 5.1: Assume A ∪ B = U and A ∩ B = ∅. Then we have
B =B∩U (5.1.4’)
= B ∩ (A ∪ A) (5.1.5)
= (B ∩ A) ∪ (B ∩ A) (5.1.3’)
= (A ∩ B) ∪ (B ∩ A) (5.1.2’)
= (A ∩ B) ∪ (A ∩ B) (5.1.2’)
= ∅ ∪ (A ∩ B) (Assumption)
= (A ∩ A) ∪ (A ∩ B) (5.1.5’)
= (A ∩ A) ∪ (A ∩ B) (5.1.2’)
= A ∩ (A ∪ B) (5.1.3’)
=A∩U (Assumption)
= A. (5.1.4’)
(self-dual)
8. using membership: Take x ∈ A. Then x ∈ U − A = {y ∈ U | y ∈
/ A} = {y ∈ U |
y ∈ A} = A. Therefore A ⊆ A. Now take x ∈ A. Then x ∈
/ A and so x ∈ A.
Then A ⊆ A and so A = A.
using Thm 5.1:

A=A∩U (5.1.4’)
= A ∩ (A ∪ A) (5.1.5)
= (A ∩ A) ∪ (A ∩ A) (5.1.3’)
= (A ∩ A) ∪ (A ∩ A) (5.1.2’)
= (A ∩ A) ∪ ∅ (5.1.5’)
= ∅ ∪ (A ∩ A) (5.1.2)
= (A ∩ A) ∪ (A ∩ A) (5.1.5’)
= (A ∩ A) ∪ (A ∩ A) (5.1.2’)
= A ∩ (A ∪ A) (5.1.3’)
=A∩U (5.1.5)
= A. (5.1.4’)

11
 (self-dual)
9. using membership: Take x ∈ ∅. Then x ∈ U − ∅ = {y ∈ U | y ∈
/ ∅} = {y ∈ U } =
U . Therefore ∅ ⊆ U . Now take x ∈ U . Then x ∈/ ∅ and so x ∈ ∅. Therefore
U ⊆ ∅. Thus ∅ = U .
using Thm 5.1:

∅=∅∪∅ (5.1.4)
=∅∪∅ (5.1.2)
= U. (5.1.5)

10. using membership: Take x ∈ A ∪ A. Then x ∈ A or x ∈ A. Obviously, x ∈ A and

so A ∪ A ⊆ A. Take x ∈ A. Then x ∈ A ∪ A and so A ⊆ A ∪ A. Thus A ∪ A = A.
using Thm 5.1:

A ∪ A = (A ∪ A) ∩ U (5.1.4’)
= (A ∩ A) ∩ (A ∪ A) (5.1.5)
= A ∪ (A ∩ A) (5.1.3)
=A∪∅ (5.1.5’)
= A. (5.1.4)

11. using membership: Take x ∈ A ∪ U . Then x ∈ A or x ∈ U . Assume x ∈ / U.

Then x ∈/ A since A ⊆ U . By contradiction, we must have x ∈ U . Therefore
A ∪ U ⊆ U . Now take x ∈ U . Then x ∈ U ∪ A = A ∪ U and therefore U ⊆ A ∪ U .
Thus A ∪ U = U .
using Thm 5.1:

A ∪ U = (A ∪ U ) ∩ U (5.1.4’)
= U ∩ (A ∪ U ) (5.1.2’)
= (A ∪ A) ∩ (A ∪ U ) (5.1.5)
= A ∪ (A ∩ U ) (5.1.3)
=A∪A (5.1.4’)
= U. (5.1.5)

12. using membership: Take x ∈ A ∪ (A ∩ B). Then x ∈ A or x ∈ A ∩ B. In the first

case, x ∈ A. In the second case, x ∈ A and x ∈ B. In both cases x ∈ A and so
A ∪ (A ∩ B) ⊆ A. Now take x ∈ A. Then x ∈ A ∪ (A ∩ B) and so A ⊆ A ∪ (A ∩ B).
Thus A ∪ (A ∩ B) = A.
using Thm 5.1: A = A ∪ ∅ = A ∪ ((A ∩ B) ∩ (A ∩ B)) = A ∪ ((A ∩ B) ∩ (A ∪ B)) =
(A∪(A∩B))∩(A∪(A∪B)) = (A∪(A∩B))∩((A∪A)∪B) = (A∪(A∩B))∩(U ∪B) =
(A ∪ (A ∩ B)) ∩ (B ∪ U ) = (A ∪ (A ∩ B)) ∩ U = A ∪ (A ∩ B).

12
 13. using membership: Take x ∈ A ∪ B. Then x ∈ / A ∪ B. Then x ∈/ A and x ∈/ B
and so x ∈ A and x ∈ B and therefore x ∈ A∩B. Thus A ∪ B ⊆ A∩B. Now take
x ∈ A ∩ B. Then x ∈ A and x ∈ B and so x ∈/ A and x ∈
/ B. Therefore x ∈
/ A∪B
and so x ∈ A ∪ B. Then we have A ∩ B ⊆ A ∪ B. Thus A ∪ B = A ∩ B.
using Thm 5.1:

A ∪ (A ∩ B) = (A ∩ U ) ∪ (A ∩ B) (5.1.4’)
= (A ∩ (B ∪ B)) ∪ (A ∩ B) (5.1.5)
= ((A ∩ B) ∪ (A ∩ B)) ∪ (A ∩ B) (5.1.3’)
= (A ∩ B) ∪ ((A ∩ B) ∪ (A ∩ B)) (5.1.1)
= (A ∩ B) ∪ ((A ∩ B) ∪ (A ∩ B)) (5.1.2)
= ((A ∩ B) ∪ (A ∩ B)) ∪ (A ∩ B) (5.1.1)
= (((A ∩ B) ∪ (A ∩ B)) ∩ U ) ∪ (A ∩ B) (5.1.4’)
= (((A ∩ B) ∪ (A ∩ B)) ∩ ((A ∩ B) ∪ (A ∩ B))) ∪ (A ∩ B) (5.1.5)
= ((A ∩ B) ∪ ((A ∩ B) ∩ (A ∩ B))) ∪ (A ∩ B) (5.1.3)
= ((A ∩ B) ∪ ∅) ∪ (A ∩ B) (5.1.5’)
= (A ∩ B) ∪ (A ∩ B) (5.1.4)
= A ∩ (B ∪ B) (5.1.3’)
=A∩U (5.1.5)
= A. (5.1.4’)

1.5.3 Using only the identities in Theorems 5.1 and 5.2, show that each of the following
equations is an identity.

(a) (A ∩ B ∩ X) ∪ (A ∩ B ∩ C ∩ X ∩ Y ) ∪ (A ∩ X ∩ A) = A ∩ B ∩ X.
Solution:

(A ∩ B ∩ X) ∪ (A ∩ B ∩ C ∩ X ∩ Y ) ∪ (A ∩ X ∩ A)
= [(A ∩ B ∩ X) ∪ (A ∩ B ∩ C ∩ X ∩ Y )] ∪ (A ∩ X ∩ A)
= [(A ∩ B ∩ X) ∪ (A ∩ B ∩ X ∩ C ∩ Y )] ∪ (A ∩ X ∩ A)
= [(A ∩ B ∩ X) ∪ ((A ∩ B ∩ X) ∩ (C ∩ Y ))] ∪ (A ∩ X ∩ A)
= (A ∩ B ∩ X) ∪ (A ∩ X ∩ A)
= (A ∩ B ∩ X) ∪ (A ∩ A ∩ X)
= (A ∩ B ∩ X) ∪ (∅ ∩ X)
= (A ∩ B ∩ X) ∪ (X ∩ ∅)
= (A ∩ B ∩ X) ∪ ∅
= A ∩ B ∩ X.

13
(b) (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ B ∪ C = U .
Solution:

(A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ B ∪ C
= (B ∩ C ∩ A) ∪ (B ∩ C ∩ A) ∪ B ∪ C
= [(B ∩ C) ∩ A] ∪ [(B ∩ C) ∩ A] ∪ B ∪ C
= [(B ∩ C) ∩ (A ∪ A)] ∪ B ∪ C
= [(B ∩ C) ∩ U ] ∪ B ∪ C
= (B ∩ C) ∪ B ∪ C
= (B ∩ C) ∪ (B ∩ C)
= U.

(c) (A ∩ B ∩ C ∩ X) ∪ (A ∩ C) ∪ (B ∩ C) ∪ (C ∩ X) = C.
Solution:

(A ∩ B ∩ C ∩ X) ∪ (A ∩ C) ∪ (B ∩ C) ∪ (C ∩ X)
= (C ∩ A ∩ B ∩ X) ∪ (C ∩ A) ∪ (C ∩ B) ∪ (C ∩ X)
= (C ∩ A ∩ B ∩ X) ∪ (C ∩ (A ∪ B)) ∪ (C ∩ X)
= (C ∩ A ∩ B ∩ X) ∪ (C ∩ [(A ∪ B) ∪ X])
= (C ∩ A ∩ B ∩ X) ∪ (C ∩ (A ∪ B ∪ X))
= (C ∩ A ∩ B ∩ X) ∪ (C ∩ (A ∩ B ∪ X))
= (C ∩ (A ∩ B ∩ X)) ∪ (C ∩ (A ∩ B ∪ X))
= C ∩ [(A ∩ B ∩ X) ∪ (A ∩ B ∪ X)]
=C ∩U
= C.

14
(d) [(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ X ∩ Y )] ∩ [(A ∩ B ∩ C) ∪ (A ∩ X ∩ Y ) ∪ (A ∩ B ∩ Y )] =
(A ∩ B) ∪ (A ∩ B ∩ X ∩ Y ).
Solution: In the words of George Costanza: “Let’s get nuts!”

[(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ X ∩ Y )] ∩ [(A ∩ B ∩ C) ∪ (A ∩ X ∩ Y ) ∪ (A ∩ B ∩ Y )]
= [(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ X ∩ Y )] ∩ [(A ∩ B ∩ C) ∪ (A ∩ X ∩ Y ) ∩ (A ∩ B ∩ Y )]
(5.2.13)
= [(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ X ∩ Y )] ∩ [(A ∩ B ∩ C) ∩ (A ∩ X ∩ Y ) ∩ (A ∩ B ∩ Y )]
(5.2.13)
= [(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ X ∩ Y )] ∩ [(A ∪ B ∪ C) ∩ (A ∪ X ∪ Y ) ∩ (A ∪ B ∪ Y )]
(5.2.13’)
= [(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ X ∩ Y )] ∩ [(A ∪ B ∪ C) ∩ (A ∪ X ∪ Y ) ∩ (A ∪ B ∪ Y )]
(5.2.8)
= [(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ X ∩ Y )] ∩ [(A ∪ B ∪ C) ∩ (A ∪ B ∪ Y ) ∩ (A ∪ X ∪ Y )]
(5.1.2’)
= [(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ X ∩ Y )] ∩ [(A ∪ B ∪ Y ) ∩ (A ∪ B ∪ C) ∩ (A ∪ X ∪ Y )]
(5.1.2’)
= [(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ X ∩ Y )] ∩ [(A ∪ B ∪ Y ) ∩ (A ∪ X ∪ Y ) ∩ (A ∪ B ∪ C)]
(5.1.2’)
= [[[(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ X ∩ Y )] ∩ (A ∪ B ∪ Y )] ∩ (A ∪ X ∪ Y )] ∩ (A ∪ B ∪ C)
(5.1.1’)

I will now break the derivation into three parts, taking care of each of the nested
intersections, and taking some reasonable shortcuts along the way. In most places,
I’ve gone above and beyond to make sure that every step appeals to theorem 5.1
or 5.2.

15
[(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ X ∩ Y )] ∩ (A ∪ B ∪ Y )
= (A ∪ B ∪ Y ) ∩ [(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ X ∩ Y )]
= [(A ∪ B ∪ Y ) ∩ (A ∩ B)] ∪ [(A ∪ B ∪ Y ) ∩ (A ∩ C)] ∪ [(A ∪ B ∪ Y ) ∩ (A ∩ X ∩ Y )]
= [((A ∪ B ∪ Y ) ∩ A) ∩ B] ∪ [((A ∪ B ∪ Y ) ∩ A) ∩ C)] ∪ [(A ∪ B ∪ Y ) ∩ (A ∩ X ∩ Y )]
= [(A ∩ (A ∪ B ∪ Y )) ∩ B] ∪ [(A ∩ (A ∪ B ∪ Y )) ∩ C)] ∪ [(A ∪ B ∪ Y ) ∩ (A ∩ X ∩ Y )]
= [(A ∩ (A ∪ (B ∪ Y ))) ∩ B] ∪ [(A ∩ (A ∪ (B ∪ Y ))) ∩ C)] ∪ [(A ∪ B ∪ Y ) ∩ (A ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [(A ∪ B ∪ Y ) ∩ (A ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [((A ∪ B ∪ Y ) ∩ A) ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [(A ∩ (A ∪ B ∪ Y )) ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [((A ∩ A) ∪ (A ∩ B) ∪ (A ∩ Y )) ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [((A ∩ A) ∪ (A ∩ B) ∪ (A ∩ Y )) ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [(∅ ∪ (A ∩ B) ∪ (A ∩ Y )) ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [((A ∩ B) ∪ (A ∩ Y ) ∪ ∅) ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [((A ∩ B) ∪ (A ∩ Y )) ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [((A ∩ B) ∪ A) ∩ ((A ∩ B) ∪ Y )) ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [(A ∪ (A ∩ B)) ∩ (Y ∪ (A ∩ B)) ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [(A ∩ (Y ∪ (A ∩ B)) ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [(A ∩ (Y ∪ A) ∩ (Y ∪ B)) ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [(A ∩ (A ∪ Y ) ∩ (Y ∪ B)) ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [(A ∩ (Y ∪ B)) ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [A ∩ ((Y ∪ B) ∩ X) ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [A ∩ (X ∩ (Y ∪ B)) ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [A ∩ X ∩ ((Y ∪ B) ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [A ∩ X ∩ (Y ∩ (Y ∪ B))]
= (A ∩ B) ∪ (A ∩ C) ∪ [A ∩ X ∩ ((Y ∩ Y ) ∪ (Y ∩ B))]
= (A ∩ B) ∪ (A ∩ C) ∪ [A ∩ X ∩ (∅ ∪ (Y ∩ B))]
= (A ∩ B) ∪ (A ∩ C) ∪ [A ∩ X ∩ ((Y ∩ B) ∪ ∅)]
= (A ∩ B) ∪ (A ∩ C) ∪ [A ∩ X ∩ (Y ∩ B)]
= (A ∩ B) ∪ (A ∩ C) ∪ [A ∩ X ∩ (B ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [A ∩ (X ∩ B) ∩ Y ]
= (A ∩ B) ∪ (A ∩ C) ∪ [A ∩ (B ∩ X) ∩ Y ]
= (A ∩ B) ∪ (A ∩ C) ∪ (A ∩ B ∩ X ∩ Y ).

16
[(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ B ∩ X ∩ Y )] ∩ (A ∪ X ∪ Y )
= (A ∪ X ∪ Y ) ∩ [(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ B ∩ X ∩ Y )]
= [(A ∪ X ∪ Y ) ∩ (A ∩ B)] ∪ [(A ∪ X ∪ Y ) ∩ (A ∩ C)] ∪ [(A ∪ X ∪ Y ) ∩ (A ∩ B ∩ X ∩ Y )]
= [((A ∪ X ∪ Y ) ∩ A) ∩ B] ∪ [((A ∪ X ∪ Y ) ∩ A) ∩ C)] ∪ [(A ∪ X ∪ Y ) ∩ (A ∩ B ∩ X ∩ Y )]
= [(A ∩ (A ∪ X ∪ Y )) ∩ B] ∪ [(A ∩ (A ∪ X ∪ Y )) ∩ C)] ∪ [(A ∪ X ∪ Y ) ∩ (A ∩ B ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [(A ∪ X ∪ Y ) ∩ (A ∩ B ∩ X ∩ Y )]
= (A ∩ B) ∪ (A ∩ C) ∪ [(A ∪ X ∪ Y ) ∩ (Y ∩ A ∩ B ∩ X)]
= (A ∩ B) ∪ (A ∩ C) ∪ [((A ∪ X ∪ Y ) ∩ Y ) ∩ A ∩ B ∩ X]
= (A ∩ B) ∪ (A ∩ C) ∪ [(Y ∩ (A ∪ X ∪ Y )) ∩ A ∩ B ∩ X]
= (A ∩ B) ∪ (A ∩ C) ∪ [(Y ∩ (Y ∪ A ∪ X)) ∩ A ∩ B ∩ X]
= (A ∩ B) ∪ (A ∩ C) ∪ (Y ∩ A ∩ B ∩ X)
= (A ∩ B) ∪ (A ∩ C) ∪ (A ∩ B ∩ X ∩ Y ).

17
 [(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ B ∩ X ∩ Y )] ∩ (A ∪ B ∪ C)
= [(A ∩ B) ∩ (A ∪ B ∪ C)] ∪ [(A ∩ C) ∩ (A ∪ B ∪ C)] ∪ [(A ∩ B ∩ X ∩ Y ) ∩ (A ∪ B ∪ C)]
= [A ∩ (B ∩ (A ∪ B ∪ C))] ∪ [(A ∩ C) ∩ (A ∪ B ∪ C)] ∪ [(A ∩ B ∩ X ∩ Y ) ∩ (A ∪ B ∪ C)]
= [A ∩ (B ∩ (B ∪ A ∪ C))] ∪ [(A ∩ C) ∩ (A ∪ B ∪ C)] ∪ [(A ∩ B ∩ X ∩ Y ) ∩ (A ∪ B ∪ C)]
= (A ∩ B) ∪ [(A ∩ C) ∩ (A ∪ B ∪ C)] ∪ [(A ∩ B ∩ X ∩ Y ) ∩ (A ∪ B ∪ C)]
= (A ∩ B) ∪ [(A ∩ C) ∩ (A ∪ C ∪ B)] ∪ [(A ∩ B ∩ X ∩ Y ) ∩ (A ∪ B ∪ C)]
= (A ∩ B) ∪ [(A ∩ C) ∩ (A ∩ C ∪ B)] ∪ [(A ∩ B ∩ X ∩ Y ) ∩ (A ∪ B ∪ C)]
= (A ∩ B) ∪ [((A ∩ C) ∩ (A ∩ C)) ∪ ((A ∩ C) ∩ B)] ∪ [(A ∩ B ∩ X ∩ Y ) ∩ (A ∪ B ∪ C)]
= (A ∩ B) ∪ [∅ ∪ ((A ∩ C) ∩ B)] ∪ [(A ∩ B ∩ X ∩ Y ) ∩ (A ∪ B ∪ C)]
= (A ∩ B) ∪ [((A ∩ C) ∩ B) ∪ ∅] ∪ [(A ∩ B ∩ X ∩ Y ) ∩ (A ∪ B ∪ C)]
= (A ∩ B) ∪ ((A ∩ C) ∩ B) ∪ [(A ∩ B ∩ X ∩ Y ) ∩ (A ∪ B ∪ C)]
= (A ∩ B) ∪ (A ∩ (C ∩ B)) ∪ [(A ∩ B ∩ X ∩ Y ) ∩ (A ∪ B ∪ C)]
= (A ∩ B) ∪ (A ∩ (B ∩ C)) ∪ [(A ∩ B ∩ X ∩ Y ) ∩ (A ∪ B ∪ C)]
= (A ∩ B) ∪ ((A ∩ B) ∩ C) ∪ [(A ∩ B ∩ X ∩ Y ) ∩ (A ∪ B ∪ C)]
= (A ∩ B) ∪ [(A ∩ B ∩ X ∩ Y ) ∩ (A ∪ B ∪ C)]
= (A ∩ B) ∪ [((A ∩ B ∩ X ∩ Y ) ∩ A) ∪ ((A ∩ B ∩ X ∩ Y ) ∩ B) ∪ ((A ∩ B ∩ X ∩ Y ) ∩ C)]
= (A ∩ B) ∪ [(A ∩ (A ∩ B ∩ X ∩ Y )) ∪ (B ∩ (A ∩ B ∩ X ∩ Y )) ∪ (C ∩ (A ∩ B ∩ X ∩ Y ))]
= (A ∩ B) ∪ [((A ∩ A) ∩ B ∩ X ∩ Y ) ∪ (B ∩ (A ∩ B ∩ X ∩ Y )) ∪ (C ∩ (A ∩ B ∩ X ∩ Y ))]
= (A ∩ B) ∪ [(A ∩ B ∩ X ∩ Y ) ∪ (B ∩ (A ∩ B ∩ X ∩ Y )) ∪ (C ∩ (A ∩ B ∩ X ∩ Y ))]
= (A ∩ B) ∪ [(A ∩ B ∩ X ∩ Y ) ∪ (B ∩ (B ∩ A ∩ X ∩ Y )) ∪ (C ∩ (A ∩ B ∩ X ∩ Y ))]
= (A ∩ B) ∪ [(A ∩ B ∩ X ∩ Y ) ∪ ((B ∩ B) ∩ A ∩ X ∩ Y ) ∪ (C ∩ (A ∩ B ∩ X ∩ Y ))]
= (A ∩ B) ∪ [(A ∩ B ∩ X ∩ Y ) ∪ (∅ ∩ A ∩ X ∩ Y ) ∪ (C ∩ (A ∩ B ∩ X ∩ Y ))]
= (A ∩ B) ∪ [(A ∩ B ∩ X ∩ Y ) ∪ (A ∩ X ∩ Y ∩ ∅) ∪ (C ∩ (A ∩ B ∩ X ∩ Y ))]
= (A ∩ B) ∪ [(A ∩ B ∩ X ∩ Y ) ∪ ∅ ∪ (C ∩ (A ∩ B ∩ X ∩ Y ))]
= (A ∩ B) ∪ [(A ∩ B ∩ X ∩ Y ) ∪ (C ∩ (A ∩ B ∩ X ∩ Y )) ∪ ∅]
= (A ∩ B) ∪ [(A ∩ B ∩ X ∩ Y ) ∪ (C ∩ (A ∩ B ∩ X ∩ Y ))]
= (A ∩ B) ∪ [(A ∩ B ∩ X ∩ Y ) ∪ ((A ∩ B ∩ X ∩ Y ) ∩ C)]
= (A ∩ B) ∪ (A ∩ B ∩ X ∩ Y ).

1.5.4 Rework Exercise 4.9(b), using solely the algebra of sets developed in this section.
Solution: Exercise 4.9(b) states: Using a Venn diagram, show that the symmetric
difference is a commutative and associative operation. In the language of the algebra
of sets, this translates to: For all sets A, B and C show that A + B = B + A and that
A + (B + C) = (A + B) + C.

18
• Theorem: A + B = B + A.
Proof:

A + B = (A − B) ∪ (B − A) (Definition of symmetric difference)

= (B − A) ∪ (A − B) (5.1.2)
= B + A. (Definition of symmetric difference)

• Theorem: A + (B + C) = (A + B) + C.
In order to prove the theorem, the following few lemmas will be useful:
Lemma 1: (A − B) − C = A − (B ∪ C).
Proof:

(A − B) − C = (A ∩ B) − C (Definition of relative complement)

= (A ∩ B) ∩ C (Definition of relative complement)
= A ∩ (B ∩ C) (5.1.1’)
= A ∩ (B ∪ C) (5.1.13)
= A − (B ∪ C) (Definition of relative complement)

Lemma 2: (A − C) ∪ (B − C) = (A ∪ B) − C.
Proof:

(A − C) ∪ (B − C) = (A ∩ C) ∪ (B ∩ C) (Definition of relative complement)

= (C ∩ A) ∪ (C ∩ B) (5.1.2’)
= C ∩ (A ∪ B) (5.1.3’)
= (A ∪ B) ∩ C (5.1.2’)
= (A ∪ B) − C (Definition of relative complement)

Lemma 3: (A ∪ B) ∩ (A ∪ B) = (A ∩ B) ∪ (A ∩ B).
Proof:

(A ∪ B) ∩ (A ∪ B) = [(A ∪ B) ∩ A] ∪ [(A ∪ B) ∩ B] (5.1.3’)

= [A ∩ (A ∪ B)] ∪ [B ∩ (A ∪ B)] (5.1.2’)
= [(A ∩ A) ∪ (A ∩ B)] ∪ [(B ∩ A) ∪ (B ∩ B)] (5.1.3’)
= [(A ∩ A) ∪ (A ∩ B)] ∪ [(A ∩ B) ∪ (B ∩ B)] (5.1.2’)
= [(A ∩ B) ∪ (A ∩ A)] ∪ [(A ∩ B) ∪ (B ∩ B)] (5.1.2)
= [(A ∩ B) ∪ (B ∩ B)] ∪ [(A ∩ B) ∪ (A ∩ A)] (5.1.2)
= [(A ∩ B) ∪ ∅] ∪ [(A ∩ B) ∪ ∅] (5.1.5’)
= (A ∩ B) ∪ (A ∩ B) (5.1.4)

19
Proof of theorem:

A + (B + C) = A + [(B − C) ∪ (C − B)] (Definition of symmetric difference)

= (A − [(B − C) ∪ (C − B)]) ∪ ([(B − C) ∪ (C − B)] − A)
(Definition of symmetric difference)
= ([A − (B − C)] − [C − B]) ∪ ([(B − C) ∪ (C − B)] − A)
(Lemma 1)
= ([A − (B − C)] − [C − B]) ∪ ([(B − C) − A] ∪ [(C − B) − A])
(Lemma 2)
= ([A − (B ∩ C)] − [C ∩ B]) ∪ ([(B ∩ C) − A] ∪ [(C ∩ B) − A])
(Definition of relative complement)
= ([A − (B ∩ C)] − [C ∩ B]) ∪ ([(B ∩ C) ∩ A] ∪ [(C ∩ B) ∩ A])
(Definition of relative complement)
= ([A − (B ∩ C)] − [C ∩ B]) ∪ ([A ∩ (B ∩ C)] ∪ [A ∩ (C ∩ B)])
(5.1.2’)
= ([A − (B ∩ C)] − [C ∩ B]) ∪ ([A ∩ (B ∩ C)] ∪ [A ∩ (B ∩ C)])
(5.1.2’)
= ([A − (B ∩ C)] − [C ∩ B]) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C)
(5.1.1’)
= (A − [(B ∩ C) ∪ (C ∩ B)]) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C)
(Lemma 1)
= (A ∩ [(B ∩ C) ∪ (C ∩ B)]) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C)
(Definition of relative complement)
= (A ∩ [(B ∩ C) ∩ (C ∩ B)]) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C)
(5.2.13)
= (A ∩ [(B ∪ C) ∩ (C ∪ B)]) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C)
(5.2.13’)
= (A ∩ [(B ∪ C) ∩ (C ∪ B)]) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) (5.2.8)
= (A ∩ [(B ∪ C) ∩ (B ∪ C)]) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) (5.1.2)
= (A ∩ [(B ∩ C) ∪ (B ∩ C)]) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C)
(Lemma 3)
= [(A ∩ (B ∩ C)) ∪ (A ∩ (B ∩ C))] ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C)
(5.1.3’)

20
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) (5.1.1’)
= (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) (5.1.1)
= (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) (5.1.2)
= (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C)
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] (5.1.1)
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ [(C ∩ A ∩ B) ∪ (C ∩ A ∩ B)] (5.1.2’)
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ [C ∩ [(A ∩ B) ∪ (A ∩ B)]] (5.1.3’)
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ [C ∩ [(A ∪ B) ∩ (A ∪ B)]] (Lemma 3)
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ [[C ∩ (A ∪ B)] ∩ (A ∪ B)] (5.1.1’)
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ [[C ∩ (A ∪ B)] ∩ (A ∪ B)] (5.1.2’)
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ [[C ∩ (A ∪ B)] ∩ (A ∪ B)] (5.2.8)
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ [[C ∩ (A ∪ B)] ∩ (A ∩ B)] (5.2.13’)
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ [[C ∩ (A ∪ B)] − (A ∩ B)]
(Definition of relative complement)
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ [[C ∩ (A ∪ B)] − (A ∩ B)] (5.2.8)
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ [[C ∩ (A ∩ B)] − (A ∩ B)] (5.2.13’)
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ [[C − (A ∩ B)] − (A ∩ B)]
(Definition of relative complement)
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ [[C − (A ∩ B)] − (B ∩ A)] (5.1.2’)
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ [[C − (A − B)] − (B − A)]
(Definition of relative complement)
= [(A ∩ B ∩ C) ∪ (A ∩ B ∩ C)] ∪ [C − [(A − B) ∪ (B − A)]] (Lemma 1)
= [((A ∩ B) ∩ C) ∪ ((A ∩ B) ∩ C)] ∪ [C − [(A − B) ∪ (B − A)]] (5.1.1’)
= [((A ∩ B) − C) ∪ ((A ∩ B) − C)] ∪ [C − [(A − B) ∪ (B − A)]]
(Definition of relative complement)
= [((A ∩ B) − C) ∪ ((B ∩ A) − C)] ∪ [C − [(A − B) ∪ (B − A)]] (5.1.2’)
= [((A − B) − C) ∪ ((B − A) − C)] ∪ [C − [(A − B) ∪ (B − A)]]
(Definition of relative complement)
= [[(A − B) ∪ (B − A)] − C] ∪ [C − [(A − B) ∪ (B − A)]] (Lemma 2)
= [(A + B) − C] ∪ [C − (A + B)] (Definition of symmetric difference)
= (A + B) + C (Definition of symmetric difference)

21
1.5.5 Let A1 , A2 , . . . , An be sets, and define Sk to be A1 ∪ A2 ∪ · · · ∪ Ak for k = 1, 2, . . . , n.
Show that
A = {A1 , A2 − S1 , A3 − S2 , . . . , An − Sn }
is a disjoint collection of sets and that

Sn = {A1 ∪ (A2 − S1 ) ∪ · · · ∪ (An − Sn−1 )}.

When is A a partition of Sn ?
Solution: First we will extend the definition of Sk to include the case of
k = 0: Define S0 = ∅. Then we may write A1 = A1 − S0 .
Now take any two distinct elements B1 = Ai − Si−1 and B2 = Aj − Sj−1 of A where,
without loss of generality, 1 ≤ i < j ≤ n. Then Sj−1 = A1 ∪ · · · ∪ Ai ∪ · · · ∪ Aj−1 and
so we have

B2 = Aj − Sj−1 = Aj ∩ (A1 ∪ · · · ∪ Ai ∪ · · · ∪ Aj−1 ) = Aj ∩ A1 ∩ · · · ∩ Ai ∩ · · · ∩ Aj−1 .

Therefore B1 ∩ B2 = (Ai − Si−1 ) ∩ (Aj − Sj−1 ) = (Ai ∩ Si−1 ) ∩ (Aj ∩ A1 ∩ · · · ∩ Ai ∩

· · · ∩ Aj−1 ) = Ai ∩ Ai ∩ (Si−1 ∩ A1 ∩ · · · ∩ Ai−1 ∩ Ai+1 ∩ · · · ∩ Aj−1 ) = ∅ ∩ (Si−1 ∩ A1 ∩
· · · ∩ Ai−1 ∩ Ai+1 ∩ · · · ∩ Aj−1 ) = ∅ and thus A is a disjoint collection of sets.

To prove Sn = {A1 ∪ (A2 − S1 ) ∪ · · · ∪ (An − Sn−1 )}, first we show that

A1 ∪ (A2 − S1 ) = A1 ∪ (A2 ∩ S1 )
= A1 ∪ (A2 ∩ A1 )
= (A1 ∪ A2 ) ∩ (A1 ∩ A1 )
= (A1 ∪ A2 ) ∩ ∅
= A1 ∪ A2 .

Now suppose A1 ∪ (A2 − S1 ) ∪ · · · ∪ (Ak − Sk−1 ) = A1 ∪ A2 ∪ · · · ∪ Ak for some k > 2.

Then

A1 ∪ (A2 − S1 ) ∪ · · · ∪ (Ak − Sk−1 ) ∪ (Ak+1 − Sk )

= A1 ∪ A2 ∪ · · · ∪ Ak ∪ (Ak+1 − Sk )
= A1 ∪ A2 ∪ · · · ∪ Ak ∪ (Ak+1 ∩ Sk )
= A1 ∪ A2 ∪ · · · ∪ Ak ∪ (Ak+1 ∩ A1 ∪ A2 ∪ · · · ∪ Ak )
= (A1 ∪ A2 ∪ · · · ∪ Ak ∪ Ak+1 ) ∩ (A1 ∪ A2 ∪ · · · ∪ Ak ∪ A1 ∪ A2 ∪ · · · ∪ Ak )
= (A1 ∪ A2 ∪ · · · ∪ Ak ∪ Ak+1 ) ∩ U
= A1 ∪ A2 ∪ · · · ∪ Ak ∪ Ak+1 .

Therefore for any given n, Sn = {A1 ∪ (A2 − S1 ) ∪ · · · ∪ (An − Sn−1 )}.

22
 A is a partition of Sn as long as all of Ai for 1 ≤ i ≤ n are nonempty. (This is all we need
since we already have that A is a disjoint collection of sets.) We have that Ai is empty
whenever Ai ⊆ Aj for some j < i since Ai − Si−1 = Ai ∩ (A1 ∩ · · · ∩ Aj ∩ · · · ∩ Ai−1 ) =
Ai ∩ Aj ∩ · · · = ∅ ∩ · · · = ∅.
1.5.6 Prove that for arbitrary sets A1 , A2 , . . . , An (n ≥ 2),
A1 ∪ A2 ∪ · · · ∪ An = (A1 − A2 )∪(A2 − A3 ) ∪ · · · ∪ (An−1 − An )
∪ (An − A1 ) ∪ (A1 ∩ A2 ∩ · · · ∩ An ).

Solution: Take x ∈ A1 ∪ A2 ∪ · · · ∪ An . Then x ∈ Ai for some 1 ≤ i ≤ n. If x ∈ / Ai+1

then we have x ∈ (Ai − Ai+1 ) (if i = n substitute 1 for i + 1 - i.e. arithmetic on the set
indices is modulo n). Otherwise, if x ∈ / Ai+2 , then x ∈ (Ai+1 − Ai+2 ). If not, continue
in this manner, checking whether x ∈ Ai+3 , Ai+4 , etc. If for all 1 ≤ j ≤ n we have
x ∈ Aj but x ∈ / (Aj − Aj+1 ) then we must have x ∈ A1 ∩ A2 ∩ · · · ∩ An . In any case,
x ∈ (A1 − A2 ) ∪ (A2 − A3 ) ∪ · · · ∪ (An−1 − An ) ∪ (An − A1 ) ∪ (A1 ∩ A2 ∩ · · · ∩ An ) and so
A1 ∪A2 ∪· · ·∪An ⊆ (A1 −A2 )∪(A2 −A3 )∪· · ·∪(An−1 −An )∪(An −A1 )∪(A1 ∩A2 ∩· · ·∩An ).
Now take x ∈ (A1 −A2 )∪(A2 −A3 )∪· · ·∪(An−1 −An )∪(An −A1 )∪(A1 ∩A2 ∩· · ·∩An ).
Then x ∈ Ai − Ai+1 for some 1 ≤ i ≤ n (again substituting 1 for i + 1 when i = n) or
x ∈ A1 ∩A2 ∩· · ·∩An . If x ∈ A1 ∩A2 ∩· · ·∩An then clearly x ∈ A1 ∪A2 ∪· · ·∪An . Now
if x ∈ Ai − Ai+1 for some i then clearly x ∈ Ai and so x ∈ A1 ∪ A2 ∪ · · · ∪ An . Therefore
(A1 −A2 )∪(A2 −A3 )∪· · ·∪(An−1 −An )∪(An −A1 )∪(A1 ∩A2 ∩· · ·∩An ) ⊆ A1 ∪A2 ∪· · ·∪An
and thus A1 ∪ A2 ∪ · · · ∪ An = (A1 − A2 ) ∪ (A2 − A3 ) ∪ · · · ∪ (An−1 − An ) ∪ (An − A1 ) ∪
(A1 ∩ A2 ∩ · · · ∩ An ).
1.5.7 Referring to Example 5.2, prove the following.
(a) For all sets A and B, A = B iff A + B = ∅.
Solution: Let A = B. Then A + B = (A − B) ∪ (B − A) = (A − A) ∪ (B − B) =
∅ ∪ ∅ = ∅. Now let A + B = ∅. Then (A − B) ∪ (B − A) = ∅. Thus A − B = ∅
and so A = B.
(b) An equation in X with righthand member ∅ can be reduced to one of the form
(A ∩ X) ∪ (B ∩ X) = ∅. (Suggestion: Sketch a proof along these lines. First,
apply the DeMorgan laws until only complements of individual sets appear. Then
expand the resulting lefthand side by the distributive law 3 so as to transform
it into the union of several terms Tn each of which is an intersection of several
individual sets. Next, if in any Ti , neither X nor X appears, replace Ti by
Ti ∩ (X ∪ X) and expand. Finally, group together the terms containing X and
those containing X and apply distributive law 3’.)
Solution: ...
(c) For all sets A and B, A = B = ∅ iff A ∪ B = ∅.
Solution: Let A = B = ∅. Then A ∪ B = ∅ ∪ ∅ = ∅. Now let A ∪ B = ∅. Then
A = ∅ and B = ∅.

23
 (d) The equation (A ∩ X) ∪ (B ∩ X) = ∅ has a solution iff B ⊆ A, and then any X
such that B ⊆ X ⊆ A is a solution.
Solution: (⇒) Suppose there exists a set X for which (A ∩ X) ∪ (B ∩ X) = ∅.
Now consider some x ∈ B and assume x ∈ A. Then if x ∈ X we have x ∈
A ∩ X ⊆ (A ∩ X) ∪ (B ∩ X) = ∅, a contradiction. Otherwise, x ∈ X and so
x ∈ B ∩ X ⊆ (A ∩ X) ∪ (B ∩ X) = ∅, another contradiction. Therefore, x ∈/A
and so B ⊆ A.
(⇐) Now assuming B ⊆ A consider a set X such that B ⊆ X ⊆ A. Then for any
x ∈ X, x ∈ A ⇒ x ∈/ A ⇒ X ∩ A = ∅. Also, for any x ∈ B, x ∈ X. Therefore
x∈/ X and so B ∩ X = ∅. Therefore (A ∩ X) ∪ (B ∩ X) = ∅.

(e) An alternative form for solutions of the equation in part (d) is X = (B ∪ T ) ∩ A,

where T is an arbitrary set.
Solution: Let X = (B ∪ T ) ∩ A for an arbitrary set T . Then we have X =
(B ∩ T ) ∪ A, A ∩ X = A ∩ [(B ∪ T ) ∩ A] = A ∩ A ∩ (B ∪ T ) = ∅ ∩ (B ∪ T ) = ∅,
and B ∩ X = B ∩ [(B ∩ T ) ∪ A] = (B ∩ B ∩ T ) ∪ (B ∩ A) = ∅ ∩ ∅ = ∅. Therefore
(A ∩ X) ∪ (B ∩ X) = ∅ and so X = (B ∪ T ) ∩ A is alternative form for solutions
of the equation in part (d).

1.5.8 Show that for arbitrary sets A, B, C, D, and X,

(a) [(A ∩ X) ∪ (B ∩ X)] = (A ∩ X) ∪ (B ∩ X)

Solution: [(A ∩ X) ∪ (B ∩ X)] = A ∩ X ∩ B ∩ X = (A ∪ X) ∩ (B ∪ X)).
Since X is an arbitrary set we may reassign X ← X.
Then we have [(A ∩ X) ∪ (B ∩ X)] = (A ∪ X) ∩ (B ∪ X).

(b) [(A ∩ X) ∪ (B ∩ X)] ∪ [(C ∩ X) ∪ (D ∩ X)] = [(A ∪ C) ∩ X] ∪ [(B ∪ D) ∩ X]

Solution:

[(A ∩ X) ∪ (B ∩ X)] ∪ [(C ∩ X) ∪ (D ∩ X)] = (A ∩ X) ∪ (B ∩ X) ∪ (C ∩ X) ∪ (D ∩ X)

= (A ∩ X) ∪ (C ∩ X) ∪ (B ∩ X) ∪ (D ∩ X)
= [(A ∪ C) ∩ X] ∪ [(B ∪ D) ∩ X]

(c) [(A ∩ X) ∪ (B ∩ X)] ∩ [(C ∩ X) ∪ (D ∩ X)] = [(A ∩ C) ∩ X] ∪ [(B ∩ D) ∩ X]

24
 Solution:

[(A ∩ X) ∪ (B ∩ X)] ∩ [(C ∩ X) ∪ (D ∩ X)]

   
= [(A ∩ X) ∪ (B ∩ X)] ∩ (C ∩ X) ∪ [(A ∩ X) ∪ (B ∩ X)] ∩ (D ∩ X)
 
= [(A ∩ X) ∩ (C ∩ X)] ∪ [(B ∩ X) ∩ (C ∩ X)]
 
∪ [(A ∩ X) ∩ (D ∩ X)] ∪ [(B ∩ X) ∩ (D ∩ X)]
= (A ∩ C ∩ X) ∪ (B ∩ C ∩ X ∩ X) ∪ (A ∩ D ∩ X ∩ X) ∪ (B ∩ D ∩ X)
= (A ∩ C ∩ X) ∪ ∅ ∪ ∅ ∪ (B ∩ D ∩ X)
= (A ∩ C ∩ X) ∪ (B ∩ D ∩ X)
= [(A ∩ C) ∩ X] ∪ [(B ∩ D) ∩ X]

1.5.9 Using the results in Exercises 5.7 and 5.8, prove that the equation

(A ∩ X) ∪ (B ∩ X) = (C ∩ X) ∪ (D ∪ X)

has a solution iff B + D ⊆ A + C. In this event determine all solutions.

Solution: Define α = A∩X, β = B ∩X, γ = C ∩X and δ = D∩X. By exercise 5.7a we
have α∪β = γ∪δ ⇔ α∪β+γ∪δ = ∅ ⇒ α∪β+γ∪δ = [(α∪β)−(γ∪δ)]∪[(γ∪δ)−(α∪β)] =
∅. By 5.7c we have [(α ∪ β) − (γ ∪ δ)] = [(γ ∪ δ) − (α ∪ β)] = ∅. Take x ∈ B + D and
assume x ∈ A + C.
(I) x ∈ B ∧ x ∈ A ⇒ x ∈ α ∧ x ∈ β ⇒ x ∈ α ∪ β.x ∈ / C ∧x ∈/D⇒x∈ / γ∧x ∈/δ⇒
x∈ / γ ∪ δ ⇒ (α ∪ β) − (γ ∪ δ) 6= ∅.
(I) x ∈ B ∧ x ∈ C ⇒ (i) x ∈ X ⇒ x ∈ / α∧x∈ /β⇒x∈ / α ∪ β.x ∈ C ∧ x ∈ X ⇒ x ∈
γ ⇒ x ∈ γ ∪ δ ⇒ (α ∪ β) − (γ ∪ δ) 6= ∅.
(III) similar to (II). (IV) similar to (I). Therefore B + D ⊆ A + C.

1.6.1 Show that if hx, y, zi = hu, v, wi then x = u, y = v, z = w.

Solution: By definition of ordered triple, hx, y, zi = hhx, yi, zi = hhu, vi, wi. Then
z = w and hx, yi = hu, vi. Then from theorem 6.1, we have x = u and y = v.

1.6.2 Write the members of {1, 2}×{2, 3, 4}. What are the domain and range of the relation?
What is its graph?
Solution: ρ = {1, 2} × {2, 3, 4} = {h1, 2i, h1, 3i, h1, 4i, h2, 2i, h2, 3i, h2, 4i}
Dρ = {1, 2} ∧ Rρ = {2, 3, 4}

1.6.3 State the domain and range of each of the following relations then draw its graph.

(a) {hx, yi ∈ R × R | x2 + 4y 2 = 1}
Solution: D = {x ∈ R | |x| ≤ 1} ∧ R = {y ∈ R | |y| ≤ 21 }
(b) {hx, yi ∈ R × R | x2 = y 2 }
Solution: D = R = R.

25
 (c) {hx, yi ∈ R × R | |x| + 2|y| = 1}
Solution: ...
(d) {hx, yi ∈ R × R | x2 + y 2 < 1 ∧ x > 0}
Solution: D = {x ∈ R | 0 < x < 1} ∧ R = {y ∈ R | |y| < 1}
(e) {hx, yi ∈ R × R | y ≥ 0 ∧ y ≤ x ∧ x + y ≤ 1}
Solution: D = {x ∈ R | 0 ≤ x ≤ 1} ∧ R = {y ∈ R | 0 ≤ y ≤ 21 }.

1.6.4 Write the relation in Exercise 6.3(c) as the union of four relations and that in Exercise
6.3(e) as the intersection of three relations.
Solution: ρ6.3c = {hx, yi ∈ R × R | y = 21 (1 + x)} ∪ {hx, yi ∈ R × R | y = 21 (1 − x)} ∪
{hx, yi ∈ R × R | y = 12 (−1 + x)} ∪ {hx, yi ∈ R × R | y = 12 (−1 − x)}.
ρ6.3e = {hx, yi ∈ R×R | y ≥ 0}∩{hx, yi ∈ R×R | y ≤ x}∩{hx, yi ∈ R×R | x+y ≤ 1}.

1.6.5 The formation of the cartesian product of two sets is a binary operation for sets. Show
by examples that this operation is neither commutative nor associative.
Solution: Define sets A = {1}, B = {2}, C = {3}. Then A × B = {h1, 2i} while
B × A = {h2, 1i}. Therefore the cartesian product is not commutative. Turning
to associativity, (A × B) × C = {h1, 2i} × {3} = {hh1, 2i, 3i} but A × (B × C) =
{1} × {h2, 3i} = {h1, h2, 3ii}. Therefore the cartesian product is not associative.

1.6.6 Let β be the relation “is a brother of”, and let σ be the relation “is a sister of”. Describe
β ∪ σ, β ∩ σ, and β − σ.
Solution: β ∪ σ corresponds to “is a brother or a sister of”, namely every pair of
siblings. β ∩ σ = ∅ since someone who is a brother cannot be a sister and vice versa.
Because of this we have β − σ = β.

1.6.7 Let β and σ have the same meaning as in Exercise 6.6. Let A be the set of students
now in the reader’s school. What is β[A]? What is (β ∪ σ)[A]?
Solution: β[A] is the set of all the students’ brothers. (β ∪ σ)[A] is the set of all the
students’ siblings.

1.6.8 Prove that if A, B, C, and D are sets, then (A∩B)×(C∩D) = (A×C)∩(B×D). Deduce
that the cartesian multiplication of sets distributes over the operation of intersection,
that is, that (A ∩ B) × C = (A × C) ∩ (B × C) and A × (B ∩ C) = (A × B) ∩ (A × C)
for all A, B, and C.
Solution: Let A, B, C, D be arbitrary sets. Then (A ∩ B) × (C ∩ D) = {hx, yi | x ∈
A ∩ B ∧ y ∈ C ∩ D} = {hx, yi | x ∈ A ∧ x ∈ B ∧ y ∈ C ∧ y ∈ D} = {hx, yi |
x ∈ A ∧ y ∈ C} ∩ {hx, yi | x ∈ B ∧ y ∈ D} = (A × C) ∩ (B × D). Then as a
direct corollary, we have that the cartesian product distributes over set intersection
since (A ∩ B) × C = (A ∩ B) × (C ∩ C) = (A × C) ∩ (B × C) and A ∩ (B × C) =
(A × A) ∩ (B × C) = (A × B) ∩ (A × C).

1.6.9 Exhibit four sets A, B, C, and D for which (A ∪ B) × (C ∪ D) 6= (A × C) ∪ (B × D).

Solution: Define sets A = C = {0} and B = D = {1}. Then (A ∪ B) × (C ∪ D) =

26
 {0, 1}×{0, 1} = {h0, 0i, h0, 1i, h1, 0i, h1, 1i} but (A×C)∪(B×D) = {h0, 0i}∪{h1, 1i} =
{h0, 0i, h1, 1i} and so (A ∪ B) × (C ∪ D) 6= (A × C) ∪ (B × D).

1.6.10 In spite of the result in the preceding exercise, cartesian multiplication distributes over
the operation of union. Prove this.
Solution: A × (B ∪ C) = {ha, ui | a ∈ A ∧ u ∈ B ∪ C} = {ha, ui | a ∈ A ∧ (u ∈ B ∨ u ∈
C)} = {ha, bi | a ∈ A ∧ b ∈ B} ∪ {ha, ci | a ∈ A ∧ c ∈ C} = (A × B) ∪ (A × C).
(A ∪ B) × C = {hu, ci | u ∈ A ∪ B ∧ c ∈ C} = {hu, ci | (u ∈ A ∨ u ∈ B) ∧ c ∈ C} =
{ha, ci | (a ∈ A ∧ c ∈ C} ∪ {hb, ci | (b ∈ B ∧ c ∈ C} = (A × C) ∪ (B × C).

1.6.11 Investigate whether union and intersection distribute over cartesian multiplication.
Solution: Set union fails to distribute over cartesian multiplication. Take sets A =
B = C = {0}. Then A ∪ (B × C) = {0} ∪ {h0, 0i} = {0, h0, 0i} but (A ∪ B) × (A ∪ C) =
{0} × {0} = {h0, 0i} and therefore A ∪ (B × C) 6= (A ∪ B) × (A ∪ C). A similar
derivation will show that (A × B) ∪ C 6= (A ∪ C) × (B ∪ C). Set intersection also fails
to distribute over cartesian multiplication. We have A∩(B×C) = {0}∩{h0, 0i} = ∅ but
(A∩B)×(A∩C) = {0}×{0} = {h0, 0i} and therefore A∩(B ×C) 6= (A∩B)×(A∩C).

1.6.12 Prove that if A, B, and C are sets such that A 6= ∅, B 6= ∅, and (A × B) ∪ (B × A) =

C × C, then A = B = C.
Solution: Let A, B, and C be sets such that A 6= ∅, B 6= ∅, and (A × B) ∪ (B × A) =
C × C. Then (A × B) ∪ (B × A) = {ha, bi | a ∈ A ∧ b ∈ B} ∪ {hb, ai | a ∈ A ∧ b ∈ B} =
{ha, bi | (a ∈ A∧b ∈ B)∨(a ∈ B ∧b ∈ A)} = {hc, ci | c ∈ C} ⇒ [x ∈ C ⇒ (x ∈ A∧x ∈
B)] ∧ [(x ∈ A ∨ x ∈ B) ⇒ x ∈ C] ⇒ C ⊆ A ∧ C ⊆ B ∧ A ⊆ C ∧ B ⊆ C ⇒ A = B = C.

1.7.1 If ρ is a relation in R+ , then its graph is a set of points in the first quadrant of a
coordinate plane. What is the characteristic feature of such a graph if (a) ρ is reflexive,
(b) ρ is symmetric, (c) ρ is transitive?
Solution: (a) ρ contains all points for which y = x (b) all points either exist on the
line y = x or have a complementary point reflected about y = x (c) how to describe??...

1.7.2 Using the results of Exercise 7.1, try to formulate a compact characterization of the
graph of an equivalence relation on R+ .
Solution: ...

1.7.3 The collection of sets {{1, 3, 4}, {2, 7}, {5, 6}} is a partition of {1, 2, 3, 4, 5, 6, 7}. Draw
the graph of the accompanying equivalence relation.
Solution: ...

1.7.4 Let ρ and σ be equivalence relations. Prove that ρ ∩ σ is an equivalence relation.

Solution: Let ρ and σ be equivalence relations. For all hx, yi ∈ ρ∩σ we have hx, yi ∈ ρ
and hx, yi ∈ σ. Since ρ and σ are reflexive, we have hx, xi ∈ ρ and hx, xi ∈ σ and
so hx, xi ∈ ρ ∩ σ hence ρ ∩ σ is reflexive. Since ρ and σ are symmetric, we have

27
 hy, xi ∈ ρ and hy, xi ∈ σ and therefore hy, xi ∈ ρ ∩ σ hence ρ ∩ σ is symmetric. For all
hx, yi, hy, zi ∈ ρ ∩ σ we have hx, yi, hy, zi ∈ ρ and hx, yi, hy, zi ∈ σ since ρ and σ are
transitive we have hx, zi ∈ ρ and hx, zi ∈ σ and therefore hx, zi ∈ ρ ∩ σ and so ρ ∩ σ is
transitive. Therefore ρ ∩ σ is an equivalence relation.

1.7.5 Let ρ be an equivalence relation on X and let Y be a set. Show that ρ ∩ (Y × Y ) is an

equivalence relation on X ∩ Y .
Solution: Take any z ∈ X ∩ Y . Then z ∈ X and so x ∈ Dρ . Since ρ is an equivalence
relation, we have hz, zi ∈ ρ. Furthermore, z ∈ Y and so hz, zi ∈ Y × Y . Therefore
hz, zi ∈ ρ ∩ (Y × Y ) and so ρ ∩ (Y × Y ) is reflexive. Take any ha, bi ∈ ρ ∩ (Y × Y ). Then
ha, bi ∈ ρ and since ρ is symmetric, we also have hb, ai ∈ ρ. Furthermore, since ha, bi ∈
Y ×Y we have a, b ∈ Y and thus hb, ai ∈ Y ×ρ0 Y . Therefore hb, ai ∈ ρ∩(Y ×Y ) and so
ρ∩(Y ×Y ) is symmetric. Now take any ha, bi, hb, ci ∈ ρ∩(Y ×Y ). Then ha, bi, hb, ci ∈ ρ
and since ρ is transitive, we have ha, ci ∈ ρ. Furthermore, since ha, bi, hb, ci ∈ Y × Y
we have a, b, c ∈ Y and so hc, ai ∈ Y × Y . Therefore hc, ai ∈ ρ ∩ (Y × Y ) and so
ρ ∩ (Y × Y ) is an equivalence relation.

1.7.6 Give an example of these relations.

(a) A relation which is reflexive and symmetric but not transitive.

Solution: ρ = {ha, bi | gcd a, b > 1}
(b) A relation which is reflexive and transitive but not symmetric.
Solution: ρ = {ha, bi | a ≤ b}
(c) A relation which is symmetric and transitive but not reflexive in some set.
Solution: ρ = {ha, bi | a is a sibling of b}

1.7.7 Complete the proof of Theorem 7.1

Solution: See the Notes for a full proof.

1.7.8 Each equivalence relation on a set X defines a partition of X according to Theorem

7.1. What equivalence yields the finest partition? the coarsest partition?
Solution: The equivalence which yields the finest partition is that of identity: ρ =
{hx, yi | x = y}. There are |X| equivalence classes in this case. The equivalence
which yields the coarsest partition is ρ = {hx, yi | x, y ∈ X} which determines a single
equivalence class of size |X|.

1.7.9 Complete the proof of Theorem 7.2

Solution: See the Notes for a full proof.

1.7.10 Let ρ be a relation which is reflexive and transitive in the set A. For a, b ∈ A, define
a ∼ b iff aρb and bρa.

(a) Show that ∼ is an equivalence relation on A.

Solution: From the definition of ∼ and the reflexivity of ρ, we get that ∼ is
reflexive. Assume a ∼ b. Then by definition aρb and bρa and so b ∼ a. Therefore

28
 ∼ is symmetric. Assume a ∼ b and b ∼ c. Then aρb and bρc and by the transitivity
of ρ, we have aρc. By symmetry of ρ we also have cρa. Therefore a ∼ c and so ∼
is transitive. Hence ∼ is an equivalence relation.
(b) For [a], [b] ∈ A/ ∼, define [a]ρ0 [b] iff aρb. Show that this definition is independent
of a and b in the sense that if a0 ∈ [a], b0 ∈ [b], and aρb, then a0 ρb0 .
Solution: Take any a0 ∈ [a] and b0 ∈ [b] and assume aρb. Then [a]ρ0 [b]. Then
since [a] = [a0 ] and [b] = [b0 ] we have [a0 ]ρ0 [b] and therefore a0 ρb0 .
(c) Show that ρ0 is reflexive and transitive. Further, show that if [a]ρ0 [b] and [b]ρ0 [a],
then [a] = [b].
Solution: Since ρ is transitive, we have aρa for all a ∈ A. Therefore [a]ρ0 [a]
for all [a] ∈ A/ ∼ by definition and so ρ0 is reflexive. Now assume [a]ρ0 [b] and
[b]ρ0 [c]. Then aρb and bρc. By the transitivity of ρ we have aρc and thus [a]ρ0 [c].
Therefore ρ0 is transitive. Now assume [a]ρ0 [b] and [b]ρ0 [a]. Then aρb and bρa and
so a ∼ b. Then we must have that a and b are in the same equivalence class mod
∼. Since a ∈ [a] and b ∈ [b] we must have [a] = [b].

1.7.11 In the set Z+ × Z+ define ha, bi ∼ hc, di iff a + d = b + c. Show that ∼ is an equivalence
relation on this set. Indicate the graph of Z+ × Z+ , and describe the ∼-equivalence
classes.
Solution: For any x, y ∈ Z+ we have x + y = y + x and so hx, yi ∼ hx, yi. Therefore
∼ is reflexive. By commutativity, a + d = b + c ⇔ d + a = c + b ⇔ c + b = d + a. Thus
whenever ha, bi ∼ hc, di, we also have hc, di ∼ ha, bi and therefore ∼ is symmetric. Now
assume ha, bi ∼ hc, di and hc, di ∼ he, f i. Then we have a + d = b + c and c + f = d + e.
Then (a + d − b) + f = d + e ⇒ a + f = b + e ⇔ ha, bi ∼ he, f i and so ∼ is transitive.
Therefore ∼ is an equivalence relation on Z+ × Z+ .

1.8.1 Give an example of a function on R into Z.

Solution: Trivial example: f : R → Z by f (x) = 0 for all x ∈ R. Non-trivial example:
floor function b·c : R → Z where bxc is the greatest integer less than or equal to x.
bxc = n ∈ Z ⇔ n ≤ x ∧ ∀m ∈ Z : m ≤ x ⇒ m ≤ n.

1.8.2 Show that if A ⊆ X, then iX |A = iA

Solution: Let A ⊆ X. Then iX |A = iX (a) for a ∈ A. Then clearly iX |A is the identity
mapping on A, or iX |A = iA .

1.8.3 If X and Y are sets of n and m elements, respectively, Y X has how many elements?
How many members of P(X × Y ) are functions?
Solution: If X and Y are sets of n and m elements, then we have m distinct ways
to map each of the n distinct elements of X. This amounts to mn possible maps as
the notation Y X suggests. The members of P(X × Y ) that are functions are those
relations which map all members of X to a member of Y and for which no member of

29
 X is mapped to more than one member of Y . This is precisely Y X . Thus only mn out
n
of 2m (only |Y X | = lg |P(X × Y )|) relations in P(X × Y ) are functions.
1.8.4 Using only mappings of the form f : Z+ → Z+ , give an example of a function which
(a) is one-to-one but not onto
Solution: f (x) = 2x.
(b) is onto but not one-to-one
Solution: f (x) = b x+2
2
c.
1.8.5 Let A = {1, 2, . . . , n}. Prove that if a map f : A → A is onto, then it is one-to-one,
and if a map g : A → A is one-to-one, then it is onto.
Solution: Let f be a map on A onto itself and assume f (a1 ) = f (a2 ) for some
a1 , a2 ∈ A. If a1 6= a2 then we have two distinct elements in A corresponding to only
one element under f . This leaves n − 2 elements to be mapped onto n − 1 elements.
Even if f |A − (a1 ∪ a2 ) is an onto map, we have one element of A which doesn’t get
mapped. Then f is not onto, a contradiction. We must have f (a1 ) = f (a2 ) ⇒ a1 = a2
which means that f is one-to-one.
Now let g be a one-to-one map on A into itself. Then for any element b ∈ A we can
find a corresponding element a ∈ A such that f (a) = b because if such an a did not
exist, we would have that the n elements of A be mapped into an A subset of size n−1.
By the pigeonhole principle, we have that two distinct elements must be mapped to
the same element, contradicting that f is one-to-one. Therefore f is onto.
Rx
1.8.6 Let f : R+ → R where f (x) = 1 dtt . Show as best you can that f is a one-to-one and
onto function.
Solution: Let f be defined as above as assume f (x1 ) = f (x2 ) for some x1 , x2 ∈ R+
Then the sum of the area under the curve from 1 to x1 equals the area from 1 to x2 .
But 1/x is positively valued for all x ∈ R+ . Therefore if x1 < x2 we must have that
f (x1 ) < f (x2 ) and similarly for x1 > x2 . Thus we must have x1 = x2 and therefore f
is one-to-one. Now take any y ∈ R. Then we can find y
an x ∈ R+ , namely ey , such that
e
f (x) = y since we know from calculus that f (ey ) = 1 dtt = ln(ey )−ln 1 = y ln e−0 = y.
R

Therefore f is onto.
1.8.7 Prove that the function f defined in Example 8.7 is a one-to-one correspondence be-
tween P(X) and 2X .
Solution: Let f be defined as in Example 8.7 and suppose f (A) = f (B) for some
A, B ∈ P(X). Then we have χA = χB . Then by definition, ∀x ∈ X : (x ∈ A ⇔ x ∈
B) ∧ (x ∈
/A⇔x∈ / B) and so A = B. Then f is one-to-one. Now for any χ ∈ 2X we
have a coded description of some subset A ⊆ X. Then we can easily identify χ with
some member of P(X) and so f is onto. Therefore f is a one-to-one correspondence
between P(X) and 2X .
1.8.8 Referring to Example 8.8, prove that if f is a function and A and B are sets, then
f [A ∪ B] = f [A] ∪ f [B].

30
 Solution: Let f be a function and A, B be sets. (I) Take y ∈ f [A ∪ B]. Then there is
some x ∈ A ∪ B such that f (x) = y. Then x ∈ A ⇒ y ∈ f [A] and x ∈ B ⇒ y ∈ f [B].
Thus y ∈ f [A] ∪ f [B] and so f [A ∪ B] ⊆ f [A] ∪ f [B]. (II) Take y ∈ f [A] ∪ f [B]. If
y ∈ f [A] then there exists some x ∈ A such that f (x) = y and if y ∈ f [B] then there
exists some x ∈ B such that f (x) = y. In both cases x ∈ A ∪ B and so y ∈ f [A ∪ B].
Therefore f [A] ∪ f [B] ⊆ f [A ∪ B]. (I) and (II) imply f [A ∪ B] = f [A] ∪ f [B].

1.8.9 Referring to the previous exercise, prove further that f [A ∩ B] ⊆ f [A] ∩ f [B], and show
that proper inclusion can occur.
Solution: Let f be a function and A, B be sets. (I) Take y ∈ f [A ∩ B]. Then there
exists an x ∈ A ∩ B such that f (x) = y. Then x ∈ A and x ∈ B and so y ∈ f [A]
and y ∈ f [B] and thus y ∈ f [A] ∩ f [B]. Therefore f [A ∩ B] ⊆ f [A] ∩ f [B]. (II) Take
y ∈ f [A] ∩ f [B]. Since y ∈ f [A] there exists an x1 ∈ A such that f (x1 ) = y and since
y ∈ f [B] there exists an x2 ∈ B such that f (x2 ) = y. In the case that x1 = x2 then we
have x1 ∈ A ∩ B and so y ∈ f [A ∩ B]. Therefore f [A] ∩ f [B] ⊆ f [A ∩ B]. In this case
(I) and (II) imply f [A ∩ B] = f [A] ∩ f [B].

1.8.10 Prove that a function f is one-to-one iff for all sets A and B, f [A ∩ B] = f [A] ∩ f [B].
Solution: (⇒) Let f be a one-to-one function. Let A and B be sets. We must show
f [A] ∩ f [B] ⊆ f [A ∩ B]. Take y ∈ f [A] ∩ f [B]. Since y ∈ f [A] there exists an x1 ∈ A
such that f (x1 ) = y and since y ∈ f [B] there exists an x2 ∈ B such that f (x2 ) = y.
But since f is one-to-one we must have that x1 = x2 . By the previous exercise, we get
that f [A] ∩ f [B] ⊆ f [A ∩ B].
(⇐) Let f be a function such that f [A] ∩ f [B] ⊆ f [A ∩ B] for all sets A and B. Assume
f (a) = f (b) for some a ∈ A and b ∈ B. Then from the previous exercise we have that
a = b and so f is one-to-one.

1.8.11 Prove that a function f : X → Y is onto Y iff f [X − A] ⊇ Y − f [A] for all sets A.
Solution: (⇒) Let f be a function on X onto Y . Take y ∈ Y − f [A]. Then y ∈ Y
and y ∈/ f [A]. Then there is an x ∈
/ A such that f (x) = y. So x ∈ X − A and therefore
f [X − A] ⊇ Y − f [A].
(⇐) Let f be a function on X into Y such that f [X − A] ⊇ Y − f [A] for all sets A.
Then taking A = ∅ we have f [X] ⊇ Y . Then for any y ∈ Y we can find an x ∈ X such
that f (x) = y and so f is onto.

1.8.12 Prove that a function f : X → Y is one-to-one and onto iff f [X − A] = Y − f [A] for
all sets A.
Solution: (⇒) Let f : X → Y be a one-to-one and onto function. Take y ∈ f [X − A]
for some set A. Then there exists an x ∈ X − A such that f (x) = y and since y is
one-to-one this is the only such x ∈ X. Then x ∈ / A⇒y ∈ / f [A] ⇒ y ∈ Y − f [A].
Therefore f [X − A] ⊆ Y − f [A]. Because f is onto we have from the previous exercise
that f [X − A] ⊇ Y − f [A]. Together, we have f [X − A] = Y − f [A] for all sets A.
(⇐) Let f : X → Y be a function such that f [X − A] = Y − f [A] for all sets
A. Since f [X − A] ⊇ Y − f [A] for all sets A, we have from the previous exercise

31
 that f is onto. It remains to show that f is one-to-one. Assume f (x1 ) = f (x2 ) for
x1 , x2 ∈ X. Then we have f [X − {x1 }] = Y − f (x1 ) and f [X − {x2 }] = Y − f (x2 )
and so f [X − {x1 }] = f [X − {x2 }]. But x2 ∈ X − {x1 } and so f (x2 ) ∈ f [X − {x1 }
but x2 ∈ / X − {x2 } and so f (x2 ) ∈
/ f [X − {x2 }], a contradiction. Then we must have
x1 = x2 and so f is one-to-one.

1/5
1.9.1 Let f : R → R where f (x) = 1 + (1 − x)1/3 . Express f as the composite of four
functions, none of which is the identity function.
Solution: Define f1 (x) := 1 − x, f2 (x) := x1/3 , f3 (x) := 1 + x, and f4 (x) := x1/5 . Then

f = f4 ◦ f3 ◦ f2 ◦ f1 .

1.9.2 If f : X → Y and A ⊆ X, show that f | A = f ◦ iA .

Solution: Let y ∈ f ◦ iA . Then y = f (iA (x)) for some x ∈ X. Since the domain of iA
is A we must have x ∈ A. Then y = f (iA (x)) = f (x) for some x ∈ A and so y ∈ f | A.
Now let y ∈ f | A. Then y = f (x) for some x ∈ A. Since x = iA (x) for all x ∈ A,
y = f (iA (x)) = (f ◦ iA )(x) and therefore y ∈ f ◦ iA .
1.9.3 Complete the proof of the assertions made in Example 9.2.
Solution: If ρ is an equivalence relation and Dρ = X, then

j : X → X/ρ

with j(x) = [x] is onto the quotient set X/ρ (Surj (j)); j is called the canonical or
natural mapping on X onto X/ρ. If f : X → Y then the relation ρ defined by

x1 ρx2 ⇔ f (x1 ) = f (x2 )

is an equivalence relation on X.

Proof:
∀x : f (x) = f (x) ⇒ xρx.
∀x, y : [f (x) = f (y) ⇔ f (y) = f (x)] ⇒ [xρy ⇔ yρx].
∀x, y, z : [f (x) = f (y) ∧ f (y) = f (z) ⇔ f (x) = f (z)] ⇒ [xρy ∧ yρz ⇔ xρz].

Let j be the canonical map on X onto X/ρ. We contend that a function g on X/ρ into f [X],
the range of f , is defined by setting g([x]) = f (x). To see that g is a function, first note that
Rg ⊆ Rf ⇒ g(X) ⊆ Y ⇔ Rg ⊆ Y ⇔ Cg = Y , where Cg is the codomain of g. To see that g
is well-defined, consider x, y ∈ X. Then xρy ⇔ [x] = [y] ⇔ f (x) = f (y) ⇔ g([x]) = g([y]).
Finally, let i be the injection of f [X] into Y . Then we have defined function j, g, i, where

j :X → X/ρ :: j(x) = [x]

g :X/ρ → f [X] :: g([x]) = f (x)
i :f [X] → Y :: i(y) = y

32
 for a function f : X → Y . Then Surj (j) and Inj (i).
Proof:
∀[x] ∈ X/ρ : ∃x ∈ X : j(x) = [x] (Take element x which is canonical representative of
equivalence class [x].) ⇒ Surj (j). ∀y, z ∈ Y : y = z ⇒ i(y) = y = z = i(z) ⇒ Inj (i).
Bij (g). Proof: ∀[x], [y] ∈ X/ρ : [x] 6= [y] ⇔ ¬xρy ⇔ f (x) 6= f (y) ⇔ g([x]) 6= g([y]) ⇒ Inj (g) .
∀y ∈ f [X]∃x ∈ X/ρ : f (x) = y ⇒ f ([x]) = y ⇒ ∃[x] ∈ X/ρ : g([x]) = f (x) = y ⇒ Surj (g).
Inj (g) ∧ Surj (g) ⇒ Bij (g). By associativity, i ◦ g ◦ j = i ◦ (g ◦ j). By definition,

g ◦ j : X → f [X] :: (g ◦ j)(x) = g(j(x)) = g([x]) = f (x)

and
i ◦ (g ◦ j) : X → Y :: (i ◦ (g ◦ j))(x) = i((g ◦ j)(x)) = i(f (x)) = f (x).
Therefore f = i ◦ g ◦ j.

1.9.4 Complete the proof of (I) and supply a proof of (II) in Example 9.3.
Solution: (I) Let f : X → Y . Then Inj (f ) iff for all functions g and h such that g : Z → X
and h : Z → X, f ◦ g = f ◦ h implies that g = h. Proof: Suppose that Inj (f ) and that g and h
are mappings on Z into X for which f ◦ g = f ◦ h. Then f (g(z)) = f (h(z)) for all z ∈ Z. With
Inj (f ) it follows that g(z) = h(z) for all z ∈ Z. Hence g = h. Now suppose for all functions
g and h such that g : Z → X and h : Z → X, f ◦ g = f ◦ h implies that g = h. Suppose
g(z) = x1 and h(z) = x2 for some z ∈ Z and x1 , x2 ∈ X. Then [(f ◦ g)(z) = (f ◦ h)(z) ⇒
g(z) = h(z)] ⇔ [f (g(z)) = f (h(z)) ⇒ g(z) = h(z)] ⇔ [f (x1 ) = f (x2 ) ⇒ x1 = x2 ] ⇔ Inj (f ).
(II) Let f : X → Y . Then Surj (f ) iff for all functions g and h such that g : Y → Z and
h : Y → Z, g ◦ f = h ◦ f implies g = h. Proof: Suppose Surj (f ) and suppose g and h are
mappings from Y into Z such that g ◦ f = h ◦ f . Then (g ◦ f )(x) = (h ◦ f )(x) for all x ∈ X.
And so g(f (x)) = h(f (x)) for all f (x) ∈ Y . That is, for all y ∈ f [X], g(y) = h(y). Since
Surj (f ) we have that f [X] = Y and so g(y) = h(y) for all y ∈ Y and so g = h. Now suppose
for all functions g and h such that g : Y → Z and h : Y → Z, g ◦ f = h ◦ f implies g = h.
Suppose there is a y ∈ Y such that f (x) 6= y for all x ∈ X. In other words, f [X] 6= Y or
¬Surj (f ). Then suppose g(y) = z1 , h(y) = z2 , and g(y 0 ) = h(y 0 ) for all other y 0 ∈ Y . Then
g ◦ f = h ◦ f since g and h only differ at the evaluation of y. But g 6= h so our assumption is
violated. Therefore Surj (f ).

1.9.5 Prove that f : A → B is a one-to-one correspondence between A and B iff there exists a map
g : B → A such that g ◦ f = iA and f ◦ g = iB .
Solution: Let f : A → B be a one-to-one correspondence between A and B. Then there
exists an inverse f −1 : B → A such that f −1 ◦ f = iA and f ◦ f −1 = iB . Letting g = f −1 we
satisfy the right implication. Suppose there exists a map g : B → A such that g ◦ f = iA and
f ◦ g = iB . Then g(f (a)) = a for all a ∈ A and so g = f −1 and f (g(b)) = b for all b ∈ B and
so f = g −1 . Therefore f and g are both invertible and so are one-to-one correspondences.

1.9.6 If f : A → B and g : B → C are both one-to-one and onto, show that g ◦ f : A → C is

one-to-one and onto and that (g ◦ f )−1 = f −1 ◦ g −1 .
Solution: Suppose Bij (f ) ∧ Bij (g). For all a1 6= a2 ∈ A we have f (a1 ) 6= f (a2 ) since
Inj (f ). Then since Inj (g) we have (g ◦ f )(a1 ) = g(f (a1 )) 6= g(f (a2 )) = (g ◦ f )(a2 ) and

33
 so a1 6= a2 ⇒ (g ◦ f )(a1 ) 6= (g ◦ f )(a2 ). Therefore Inj (g ◦ f ). For any c ∈ C, there is a
b ∈ B with g(b) = c since Surj (g). For any b ∈ B, there is an a ∈ A with f (a) = b since
Surj (f ). Then c = g(b) = g(f (a)) = (g ◦ f )(a) for some a ∈ A. Therefore Surj (g ◦ f ). Since
Inj (g ◦ f ) ∧ Surj (g ◦ f ) we have Bij (g ◦ f ) and so we can define an inverse (g ◦ f )−1 : C → A
such that (g ◦ f )−1 ◦ (g ◦ f ) = iA . Then for all a ∈ A, [(g ◦ f )−1 ◦ (g ◦ f )](a) = (g ◦ f )−1 ◦
g(f (a)) = iA . But (f −1 ◦ g −1 ) ◦ (g(f (a))) = f −1 (g −1 (g(f (a)))) = f −1 (f (a)) = a = iA and so
(g ◦ f )−1 = f −1 ◦ g −1 .

1.9.7 For a function f : A → A, f n is the standard abbreviation for f ◦ f ◦ · · · ◦ f with n occurrences

of f . Suppose that f n = iA . Show that f is one-to-one and onto.
Solution: Let f : A → A and suppose f n = iA . Then for all a1 6= a2 ∈ A and suppose
f (a1 ) = f (a2 ) = a3 . Then f n (f (a1 )) = f n+1 (a1 ) = a3 and f n (f (a2 )) = f n+1 (a2 ) = a3 . But
f n (a1 ) = a1 and f n (a2 ) = a2 and so f (a1 ) = a1 and f (a2 ) = a2 . Since it’s assumed that
a1 6= a2 this is a contradiction. Then a1 6= a2 ∈ A ⇒ f (a1 ) 6= f (a2 ) and so Inj (f ). For any
a ∈ A we have f n−1 (a) ∈ A and f (f n−1 (a)) = f n (a) = a. Then Surj (f ).

1.9.8 Justify the following restatement of Theorem 7.1. Let X be a set. Then there exists a one-
to-one correspondence between the equivalence relations on X and the partitions of X.
Solution: Define a function f from the set of equivalence relations on X to the set of
partitions of X such that the image of a given equivalence relation under f is the set of its
equivalence classes. Theorem 7.1 states that this image is a partition of X. Showing that an
equivalence relation determines a partition of X and vice versa is equivalent to showing that
no two distinct equivalence classes map to the same partition (Inj (f )) and that every partition
has a corresponding equivalence relation (Surj (f )). Therefore the statement of Theorem 7.1
is equivalent to the saying Bij (f ).

1.9.9 Prove that if the inverse of the function f in R exists, then the graph of f −1 may be obtained
from that of f by reflection in the line y = x.
Solution: If the inverse of f in R exists, then for all x ∈ R we have f (x) = y for some y ∈ R
and f −1 (y) = x. Therefore the roles of independent and dependent variable are swapped out
for f −1 . Having a graph with x plotted on one axis and y an a second axis perpendicular
to the first, we must flip the graph 180◦ around the line y = x to achieve this variable swap
graphically.

1.9.10 Show that each of the following functions has an inverse. Determine the domain of each
inverse and its value at each member of its domain. Further, sketch the graph of each inverse.

(a) f : R → R where f (x) = 2x − 1.

Solution: ∀x, y ∈ R, x 6= y ⇒ f (x) = 2x − 1 6= 2y − 1 = f (y) ⇒ Inj (f ) and ∀y ∈ R,
f ( 12 (y + 1)) = 2( 12 (y + 1)) − 1 = y + 1 − 1 = y ⇒ Surj (f ). Then Df −1 = R and
f −1 (x) = 12 (x + 1).
(b) f : R → R where f (x) = x3 .
Solution: ∀x, y ∈ R, x 6= y ⇒ f (x) = x3 6= y 3 = f (y) ⇒ Inj (f ) and ∀y ∈ R,
√ √ √
f ( 3 y) = ( 3 y)3 = y ⇒ Surj (y). Then Df −1 = R and f −1 (x) = 3 x.
(c) f = {hx, (1 − x2 )1/2 i | 0 ≤ x ≤ 1}
Solution: ∀x, y ∈ [0, 1], if x 6= y then f (x) = (1 − x2 )1/2 6= (1 − y 2 )1/2 = f (y) since

34
 g(x) = x2 and h(x) = x1/2 are both monotonically increasing in [0, 1]. So Inj (f ). For all
y ∈ [0, 1] we have f ((1−y 2 )1/2 ) = (1−((1−y 2 )1/2 )2 )1/2 = (1−(1−y 2 ))1/2 = (y 2 )1/2 = y.
Then Df −1 = [0, 1] and f −1 (x) = (1 − x2 )1/2 = f (x).
x
(d) f = {hx, x−1 | −2 ≤ x < 1i}
x y
Solution: ∀x, y ∈ [−2, 1), if x 6= y then f (x) = x−1 6= y−1 = f (y) ⇒ Inj (f ). ∀y ∈
y y/(y−1) y/y−1
[−2, 1) we have f ( y−1
= ) y/(y−1)−1 = 1/y−1 = y ⇒ Surj (f ). Then Df −1 = [−2, 1) and
−1 x
f (x) = x−1 = f (x).

35