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