Multi-Page Printing

26 2. Background (i) Represent R as a graph. (ii) How many elements does A/R have? (iii) Write out the sets [1], [2], and [3]. Exercise 2.3.16. A partition of a set A is a collection of disjoint subsets of A with union equal to A. Prove that any partition of A determines an equivalence relation on A, and every equivalence relation on A determines a partition of A. Exercise 2.3.17. Let R(m, n) be the relation on Z that holds when m − n is a multiple of 3. (i) Prove that R is an equivalence relation. (ii) What are the equivalence classes of 1, 2, and 3? (iii) What are the equivalence classes of −1, −2, and −3? (iv) Prove that Z/R has three elements. Exercise 2.3.18. Let R(m, n) be the relation on N that holds when m − n is even. (i) Prove that R is an equivalence relation. (ii) What are the equivalence classes of R? Give a concise verbal description of each. The two exercises above are examples of modular arithmetic, which is also sometimes called clock-face arithmetic because its most widespread use in day-to-day life is telling what time it will be some hours from now. This is a notion that is used only in N and Z. The idea of modular arithmetic is that it is only the number’s remainder upon division by a fixed value that matters. For clock-face arithmetic, that value is 12 we say we are working modulo 12, or just mod 12, and the equivalence classes are represented by the numbers 0 through 11 (in mathematics 1 through 12 in usual life). The fact that if it is currently 7:00 then in eight hours it will be 3:00 would be written as the equation 7 + 8 = 3 (mod 12), where ≡ is sometimes used in place of the equals sign. Exercise 2.3.19. (i) Exercises 2.3.17 and 2.3.18 consider equiva- lence relations that give rise to arithmetic mod k for some k. For each, what is the correct value of k?