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?
