2.2. Sets 19
35 years of age. Since 35 is more than 30, the person we chose is a
member of the second set.
We can further show that this containment is proper, by demon-
strating a member of the second set who is not a member of the first
set. For example, a 40-year-old who is not a U.S. citizen.
Exercise 2.2.6. Prove that the set of squares of even numbers, {x :
∃y(x =
(2y)2)},
is a proper subset of the set of multiples of 4, {x :
∃y(x = 4y)}.
To prove two sets are equal, there are three options: show the
criteria for membership on each side are the same, manipulate set
operations until the expressions are the same, or show each side is a
subset of the other side.
An extremely basic example of the first option is showing {x :
x
2
, x
4
∈ N} = {x : (∃y)(x = 4y)}. For the second, we have a bunch of
set identities, including a set version of De Morgan’s Laws.
A ∩ B = A ∪ B
A ∪ B = A ∩ B
We also have distribution laws.
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
To prove identities we have to turn to the first or third option.
Example 2.2.7. Prove that A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
We work by showing each set is a subset of the other. Suppose
first that x ∈ A ∪ (B ∩ C). By definition of union, x must be in A or
in B ∩ C. If x ∈ A, then x is in both A ∪ B and A ∪ C, and hence in
their intersection. On the other hand, if x ∈ B ∩ C, then x is in both
B and C, and hence again in both A ∪ B and A ∪ C.
Now suppose x ∈ (A ∪ B) ∩ (A ∪ C). Then x is in both unions,
A ∪ B and A ∪ C. If x ∈ A, then x ∈ A ∪ (B ∩ C). If, however, x / ∈ A,
then x must be in both B and C, and therefore in B ∩ C. Again, we
obtain x ∈ A ∪ (B ∩ C).
