NAME:Mathematics 144, Fall 2006, Examination 1Answer Key11. [20 points] Let A and B be sets (contained in some large set S). Prove theabsorption law A ∪ (A ∩ B) = A.SOLUTIONWe first note that A ⊂ A ∪(A ∩B) = A because x ∈ A implies x ∈ A or x ∈ A ∩B (infact, the first is always true). Conversely, if x ∈ A ∪(A ∩B) = A then x ∈ A or x ∈ A ∩B.In the first case we know that x ∈ A, while in the second we know that x ∈ A ∩B, so thatx ∈ A and x ∈ B. In either case we see that x ∈ A, and therefore we must have x ∈ A,which implies A ∪ (A ∩ B) = A. Since each set is contained in the other, they are equal.22. [20 points] Let A be the set of all positive integers n such that 100 ≤ n ≤ 999,and let E be the binary relation on A given by x E y if and only if the three digits in xare rearrangements of the three digits in y; then E is an equivalence relation, and you mayassume this without proving it. Determine all elements of A that are in the equivalenceclasses of the number n for each of n = 111, 122, and 135. [Hint: The combined numberof integers in the three equivalence classes is equal to 10.]SOLUTIONThe equivalence class of 111 only contains 111, the equivalence class of 122 is given by{122, 212, 221}, and the equivalence class of 135 is given by {135, 351, 513, 153, 315, 531}.33. [20 points] Suppose that A, B and C are subsets of some set S. Prove thatA × (B − C) = (A × B) − (A × C).SOLUTIONOnce again we show that each is contained in the other. If u ∈ A × (B − C), thenu = (x, y) where x ∈ A and y ∈ B − C. It follows that (x, y) ∈ A × B but (x, y) 6∈ A × C,so we have A ×(B − C) ⊂ (A × B) − (A × C).Conversely, if u ∈ (A × B) − (A × C), then u = (x, y) where x ∈ A and y ∈ B.However, since the pair does not belong to A × C, we either have x 6∈ A or y 6∈ C. Thefirst does not happen because we already know that x ∈ A, and therefore we must havey 6∈ C, which means that y ∈ B − C. Therefore y ∈ B − C, so that (x, y) ∈ A × (B − C).Therefore we also have (A × B) − (A × C) ⊂ A × (B − C). Since each of the two sets iscontained in the other, they are equal.44. [25 points] (a) Let X be the binary operation on the set Z of (signed) integersgiven by a X b if and only if b = arfor some positive integer r. Prove that X defines apartial ordering on Z.(b) If a X b, does it follow that a ≤ b in the usual ordering of the integers? Eitherprove this or give an example of an ordered pair (a, b) where the first relation is true butthe second is false.SOLUTION(a) The relation is reflexive because a = a1. To see it is symmetric, suppose we haveb = arand a = bq. Then by the laws of exponents we have a = arq, which means thateither a = 0 or rq = 1. In the first case it follows that b = 0r= 0 = a, while in the secondit follows that r = q = 1 so that b = a. To see the relation is transitive, note that if b = arand c = bqthen c = aqragain by the laws of exponents.(b) The easiest way to see the answer is NO is to take a = −2 and b = −8, so thatb = a3but b < a.55. [15 points] Let R be the real numbers, and let V be the binary relation on Rdefined by x V y if and only if y2− x2= 1. Give an example to show that V is nottransitive; in other words, find a, b, c such that a V b and b V c are true but a V c isfalse.SOLUTIONTake (0, 1) and (1,√2). Both lie in the subset of ordered pairs for which the relationis true, but the pair (0,√2) does not because y2− x2= 2 in this case.There are many other possibilities of this type; for example one can take a =√n,b =√n + 1, c =√n + 2, where n is an arbitrary nonnegative