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?