Answers
Solutions and Hints for Selected
Exercises
Chapter 1
Section 1.1
5. To prove that two sets are equal, we must show that an element is in the first
set if and only if it is in the second. Suppose
. Then
,
which means that x cannot be in S 1 or in S 2 , that is
. Conversely,
if
, then x is not in S 1 and x is not in S 2 , that is,
.
6. This can be proven by an induction on the number of sets. Let Z = S 1 ∪ S 2 …
∪ S n . Then S 1 ∪ S 2 …∪ S n ∪ S n+1 = Z ∪ S n+1 . By the standard De Morgan's
law,
With the inductive assumption, the relation is true for up to n sets, that is,
Therefore,
completing the inductive step.
8. Suppose S 1 = S 2 . Then
and the entire
expression is the empty set. Suppose now that S 1 ≠ S 2 and that there is an