7.2 EQUIVALENCE RELATIONS 239erties. The ideas in Example 5 are the basis for both Exercise 10 and for
our work in the next article.Exercises
- Prove that the relations R,, and R2,, from parts (a) and (c) of Example 1, are
equivalence relations. - Let A be the set of all people living in the year 1987. For each of the following
relations S,,... , S,, interpret the three properties RST, and verrfy that each of the
five is an equivalence relation (in some cases, on a specified subset of A):
(a) S, = {(x, y)lx and y are of the same sex)
*(b) S, = {(x, y) 1 x and y have the same biological parents)
(c) S, = {(x, y)^1 x and y are the same weight (measured to the nearest pound))
(d) S, = {(x, y) I x and y have the same grade point average), where S, is defined
on the set of all college seniors graduating during 1987.
(e) S, = {(x, y)lx and y had the same number of home runs during the^1986
season), where S, is defined on the set of all major league baseball players
during 1986. - Show that the relation R,, = {(x, y) E R x R lxy 2 0) is not an equivalence rela-
tion on R. - The division algorithm for Z states that, given any two integers m and d, where
d > 0, there exist unique integers q and r such that m = qd + r and 0 4 r < d. The
integer q is called the quotient and r is called the remainder.
(a) Find q and r for:
(i) m=17,d=4 (ii) m = 3, d = 5
(iii) m = 0, d = 5 (iv) m = -17, d = 5
(b) Check that the integers -3 and 27 are congruent modulo 5. Given m, = -3
and d = 5, find 4, and r,. Given m, = 27 and d = 5, find 4, and r,.
(c) Mimic (b), letting m, = 13, m, = - 17, and d = 5, noting that^13 x -^17 mod 5.
(d) Mimic (b), letting m, = 8, m, = - 3, and d = 5, noting that 8 is not congruent
to - 3 modulo 5.
(e) What conclusion do the results in (b), (c), and (d) seem to suggest?
5. (a) Define a relation congruence modulo^9 (denoted m ,) on the set Z in a man-
ner analogous to the definition of congruence modulo 5 (recall Example 5,
Article 7.1). Pr~ve that E, is an equivalence relation on Z.
(b) Define a relation - on R by the rule x - y if and only if x - y is an integer.
Prove that - is an equivalence relation on R.
(c) Define a relation x on R by the rule x x y if and only if x - y is a rational
number. Prove that x is an equivalence relation on R. (Note: Use the facts that
the sum of two rational numbers is rational and the negative of a rational number
is rational.)
6. (a) Let f be a real-valued function having domain R. Define a relation -/ on
R by the rule x - y if and only if f (x) = f (y). Prove that - is an equivalence
relation on R.