Multi-Page Printing

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