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 =
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
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).
Previous Page Next Page