COMP S264F Discrete Mathematics
Unit 3: Set Theory
Tutorial Exercises – Suggested Solution
Question 1.
(a) {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
(b) {2, 3, 5, 7}
(c) {4, 25, 64}
(d) {6, 7, 9}
Question 2.
(a) True (c) False (e) False (g) True
(b) False (d) True (f) True (h) True
Question 3.
(a) By solving x2 + x = 2, we have A = {1, −2}. Then, −2 ∈ A and −2 ∈
/ B, so A ⊈ B.
(b) B = A ∩ C = ∅. Hence, A ⊈ B.
(c) A = {2, 4, 6, 8, · · · } is the set of positive even integers.
B = {1, 2, 3, 4, · · · } is the set of positive integers.
Hence, A ⊆ B.
Formal proof: Assume y ∈ A. Then y = 2x for some positive integer x. Thus, y is also a positive integer,
i.e., y ∈ B. A ⊆ B follows.
(d) B = {1, 2, 3}. Then, 4 ∈ A and 4 ∈
/ B, so A ⊈ B.
Question 4.
(a) B must contain all of the elements in A so that A ∩ B = A.
Hence, we can deduce that A ⊆ B.
(b) A must contain all of the elements in B so that A ∪ B = A.
Hence, we can deduce that B ⊆ A.
(c) A and B should be disjoint, i.e., having completely different elements.
In other words, A = U − A contain all of the elements in B, where U is the domain (i.e., universal set).
Hence, B ⊆ A.
(d) By De Morgan’s Law, A ∩ B = A ∪ B = B
From (b), we can deduce that A ⊆ B.
Therefore, B = U − B ⊆ U − A = A, i.e., B ⊆ A.
Question 5.
(a) (A ∪ B) ∩ C = ({1, 4, 7, 10} ∪ {1, 2, 3, 4, 5}) ∩ {2, 4, 6, 8}
= {1, 2, 3, 4, 5, 7, 10} ∩ {2, 4, 6, 8}
= {2, 4}
Thus, |(A ∪ B) ∩ C| = 2.
1
(b) A ∪ (B ∩ C) = {1, 4, 7, 10} ∪ ({1, 2, 3, 4, 5} ∩ {2, 4, 6, 8})
= {1, 4, 7, 10} ∪ {2, 4}
= {1, 2, 4, 7, 10}
Thus, |A ∪ (B ∩ C)| = 5.
(c) A − B = {1, 4, 7, 10} − {1, 2, 3, 4, 5}
= {7, 10}
Thus, |A − B| = 2.
(d) B − A = {1, 2, 3, 4, 5} − {1, 4, 7, 10}
= {2, 3, 5}
Thus, |(B − A)| = 3.
(e) U = ∅.
Thus, |U | = 0.
(f) (A ∩ B) ∪ C = ({1, 4, 7, 10} ∩ {1, 2, 3, 4, 5}) ∪ {2, 4, 6, 8}
= {1, 4} ∪ {2, 4, 6, 8}
= {2, 3, 5, 6, 7, 8, 9, 10} ∪ {2, 4, 6, 8}
= {2, 3, 4, 5, 6, 7, 8, 9, 10}
Thus, |(A ∩ B) ∪ C| = 9.
(g) A ∪ B ∪ C = {1, 4, 7, 10} ∪ {1, 2, 3, 4, 5} ∪ {2, 4, 6, 8}
= {2, 3, 5, 6, 8, 9} ∪ {6, 7, 8, 9, 10} ∪ {2, 4, 6, 8}
= {2, 3, 4, 5, 6, 7, 8, 9, 10}
Thus, |A ∪ B ∪ C| = 9.
(h) (A ∪ C) − (B − A) = ({1, 4, 7, 10} ∪ {2, 4, 6, 8}) − ({1, 2, 3, 4, 5} − {1, 4, 7, 10})
= ({1, 4, 7, 10} ∪ {1, 3, 5, 7, 9, 10}) − ({1, 2, 3, 4, 5} − {2, 3, 5, 6, 8, 9})
= {1, 3, 4, 5, 7, 9, 10} − {1, 4}
= {3, 5, 7, 9, 10}
Thus, |(A ∪ C) − (B − A)| = 5.
Question 6.
(a) A △ B = (A ∪ B) − (A ∩ B)
= ({1, 2, 3} ∪ {2, 3, 4, 5}) − ({1, 2, 3} ∩ {2, 3, 4, 5})
= {1, 2, 3, 4, 5} − {2, 3}
= {1, 4, 5}
(b) Let U be the universal set. The Venn diagram is
U
A B
(c) A △ B is the set of elements in either sets A or B, but not both.
2
Question 7. There are many possible combinations. Here are some suggestions.
(a) A = {1}
B = {2}
C = {1, 2}
(b) A = {1}
B = {2}
C = {3}
(c) A = {1}
B = {2}
C = {1, 2}
(d) A = {1, 2, 3}
B = {1, 2}
C = {2, 3}
Question 8.
(a) A ∩ (B − A) = A ∩ (B ∩ A)
=A∩A∩B
=∅∩B
=∅
U
A B
(b) A ∩ (A ∩ B) = A ∩ (A ∪ B) (by De Morgan’s law)
= (A ∩ A) ∪ (A ∩ B) (by distributive law)
= ∅ ∪ (A ∩ B)
=A∩B
=A−B
U
A B
3
(c) (A − B) ∪ (A − C) = (A ∩ B) ∪ (A ∩ C)
= A ∩ (B ∪ C) (by distributive law)
B C
(d) (A − B) ∩ (A ∪ C) = (A ∩ B) ∩ (A ∪ C)
= (A ∩ B) ∩ (A ∩ C) (by De Morgan’s law)
=A∩A∩B∩C
=A∩B∩C
B C
Question 9.
(a) P (A) = {∅ , {a}, {∅} , {a, ∅}}
(b) (i) True (v) False (ix) True (xiii) False
(ii) False (vi) True (x) True (xiv) True
(iii) False (vii) True (xi) True (xv) True
(iv) False (viii) False (xii) True (xvi) True
Question 10.
(a) A × A = {(1, 1), (1, 2) , (2, 1), (2, 2)}
Thus, |A × A| = 4.
(b) A × B = {(1, x), (1, y), (1, z) , (2, x), (2, y), (2, z)}
Thus, |A × B| = 6.
(c) B × A = {(x, 1), (x, 2) , (y, 1), (y, 2) , (z, 1), (z, 2)}
Thus, |B × A| = 6.
(d) B × B = {(x, x), (x, y), (x, z) , (y, x), (y, y), (y, z) , (z, x), (z, y), (z, z)}
Thus, |B × B| = 9.
4
Question 11.
(a) Assume A ⊆ B. Then,
x ∈ A ∩ C =⇒ x ∈ A and x ∈ C
=⇒ x ∈ B and x ∈ C (as A ⊆ B)
=⇒ x ∈ B ∩ C
Thus, A ∩ C ⊆ B ∩ C.
(b) Assume P (A) ⊆ P (B).
By definition, A ∈ P (A).
Since P (A) ⊆ P (B), we have A ∈ P (B), which implies A ⊆ B.
(c) Assume A ∩ B = A ∩ C and A ∪ B = A ∪ C.
U
A X
By the above Venn diagram, we can deduce that X = [(A ∪ X) − A] ∪ (A ∩ X) for any set X.
This can be formally proven, as follows:
[(A ∪ X) − A] ∪ (A ∩ X) = [(A ∪ X) ∩ A] ∪ (A ∩ X)
= [(A ∩ A) ∪ (X ∩ A)] ∪ (A ∩ X) (by distributive law)
= [∅ ∪ (X ∩ A)] ∪ (A ∩ X)
= (X ∩ A) ∪ (A ∩ X)
= X ∩ (A ∪ A) (by distributive law)
=X ∩U =X .
Therefore, B = [(A ∪ B) − A] ∪ (A ∩ B)
= [(A ∪ C) − A] ∪ (A ∩ C) (by assumptions)
=C .
(d) We need to prove the biconditional statement in both directions.
(i) We first prove that A ⊆ C and B ⊆ C =⇒ A ∪ B ⊆ C.
Assume A ⊆ C and B ⊆ C.
If x ∈ A ∪ B, then x ∈ A or x ∈ B =⇒ x ∈ C or x ∈ C (as A ⊆ C and B ⊆ C)
=⇒ x ∈ C
Thus, A ∪ B ⊆ C.
Hence, A ⊆ C and B ⊆ C =⇒ A ∪ B ⊆ C follows.
(ii) Next, we prove that A ∪ B ⊆ C =⇒ A ⊆ C and B ⊆ C.
Assume A ∪ B ⊆ C. We consider prove the following two cases.
Case 1: A ∪ B ⊆ C =⇒ A ⊆ C.
If x ∈ A, then x ∈ A ∪ B =⇒ x ∈ C (as A ∪ B ⊆ C).
Thus, A ⊆ C.
Case 2: A ∪ B ⊆ C =⇒ B ⊆ C.
Similarly, if x ∈ B, then x ∈ A ∪ B =⇒ x ∈ C (as A ∪ B ⊆ C).
Thus, B ⊆ C.
To sum up, A ∪ B ⊆ C =⇒ A ⊆ C and B ⊆ C follow.
Therefore, the bidirectional statement follows.
