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).