MATHEMATICS 271 L01 WINTER 2014
Quiz 3 Solutions
 1. Prove statement (a) by contradiction, and disprove the statement (b) by writing out
its negation and prove that.
(a) For all sets A;B and C, if C ▯ B ▯ A then A \ C = ;.
Solution: Let A;B and C so that C ▯ B ▯ A. We prove A \ C = ; by contradiction.
Suppose that A \ C 6= ;; that is, there exists an element x 2 A \ C. Since x 2 A \ C, we
know x 2 A and x 2 C. Since x 2 C and C ▯ B ▯ A, we get x 2 B ▯ A, and so we have
x = A. Thus, we have the contradiction x 2 A and x 2 = A. Therefore, A \ C = ;.
(b) For all sets A;B and C, if A ▯ B ▯ C and B ▯ C ▯ A then C ▯ A ▯ B.
Solution: The negation of this statement is: \There are sets A;B and C so that A▯B ▯ C
and B ▯ C ▯ A, but C ▯ A * B."
For example, consider the sets A = B = ; and C = f1g. In this case we have
A▯B = ;▯B = ; ▯ C and B▯C = ;▯C = ; ▯ A but C▯A = C▯; = C = f1g * ; = B.
 2. For each of the following questions, give a brief explanation on how you get the answers.
(a) How many positive four-digit integers can be formed using only the digits 1,2,3,4,5,6,7,8,9?
Solution: There are 9 such numbers since we have 9 choices for each of the four digits of
(b) How many integers in part (a) have the property that the digit 1 appears at least once?
Solution: The answer to this question is 9 ▯ 8 , that is the total number of the integers
in (a) minus the number of integers without 1. The number of integer