Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL
Help

Basic Set Theory and Indexed Families > Cartesian Product of Sets - Pg. 82

82 CHAPTER 4 Some Mathematical Topics on Which to Practice Proof Techniques 6. Prove or disprove the following statement: The sets A = {all integer multiples of 16 and 36} and B = {all integer multiples of 576} are equal. 7. Prove or disprove the following equalities, with A, B, and C subsets of a universal set U: a. A (B C) = (A B) C b. (A B C) = A B C 8. Prove or disprove the claim that the sets A = fðx, y Þ j y = x 2 - 1 with x and x g & ' 4 B = ðx, y Þ j y = x 2 - 1 with x and y x + 1 and are equal. 9. Prove or disprove the following statement: Let A and B be two subsets of the same set U. If A - B is empty, then either A is empty or A B. 10. Prove or disprove the following statement: Let A and B be two sets. If either A = or A B, then A B = B. 11. Prove by induction that ðA 1 A 2 ...:: A n Þ = A A ...:: A n for all n 2. (See Example 4.1.10 1 2 for the base case n = 2.) 12. Prove by induction that if a set has n elements, then it has 2 n subsets, where n 0. Cartesian Product of Sets There is another operation that can be defined between sets. This operation is somewhat different from the ones in the previous section because very often it changes the nature of the sets used, as we will see. Let A and B be two sets. The Cartesian product of A and B is the set defined as A × B = fða, bÞ j a A and b Bg: The element (a, b) is a pair. The element a is called the first coordinate and the element b is the second coordinate. Two pairs (a, b) and (c, d) are equal if and only if a = c and (b = d). This operation can easily be extended to any number of sets. EXAMPLE 4.1.15 Let A = {1, 2, 3} and B = {3, 4}. Build the sets A × B and B × A. Solution: To construct the set A × B we construct all possible pairs using the elements of A for the first coordinate and the elements of B for the second. Therefore A × B = fð1, 3Þ, ð1, 4Þ, ð2, 3Þ, ð2, 4Þ, ð3, 3Þ, ð3, 4Þg: To construct the set B × A we construct all possible pairs using the elements of B for the first coordinate and the elements of A for the second. Therefore B × A = fð3, 1Þ, ð3, 2Þ, ð3, 3Þ, ð4, 1Þ, ð4, 2Þ, ð4, 3Þg: