Bridge to Abstract Mathematics: Mathematical Proof and Structures

7.2 EQUIVALENCE RELATIONS 237

Solution To show E is reflexive, let x E A be given. Note that (x, x) E E

means that x2 > 0, clearly a true statement. For symmetry, suppose

x, y E R and x E y, so that xy > 0. Since xy = yx, we conclude yx > 0

so that y E x, as desired. As to transitivity, suppose x, y, z E R, that

x E y and y E z. To prove x E z, we need that xz > 0. We proceed by

division into the cases x > 0 and x < 0. If x > 0, then since xy > 0, we

have y > 0. Since y > 0 and yz > 0, then z > 0. Since x > 0 and z > 0,

we conclude xz > 0, as desired. The argument for the case x < 0 is similar.

The relation N is clearly symmetric, since yx = xy, so that xy < 0

certainly implies yx < 0 for any x, y E A. It is not reflexive because, for

instance, (5, 5) 4 N, since 52 = 25 is not less than 0. It is not transitive

since (5, - 5) E N (Why?) and (- 5,7) E N, but (5,7) 4 N.

EXAMPLE 3 Show that the relation "congruence modulo 5" (R,, from

Example 5, Article 7.1) is an equivalence relation on Z.

Solution Integers m and n are related by this relation, denoted m = n mod 5,

if and only if 5 divides the difference m - n. You may wish to recall

Examples 2 and 7, as well as Exercise 2, from Article 6.1. For the reflexive

propejrty, if m E Z, then m = m mod 5, since m - m = 0 and 5 10, by (e) of

Exercise 2 (Article 6.1). For symmetry, assume m, n E Z and m = n mod 5;

thus 5 divides m - n. Since n - m = -(m - n), and since 5 divides

-(m - n) by (h) of the aforementioned Exercise 2, then 5 divides n - m,

so that n = m mod 5, as desired. To prove transitivity, suppose m, n,

p E Z, that 5 1 (m - n) and 5 1 (n - p). We must prove 5 1 (m - p). But

m - p = (m - n) + (n - p), and 5 divides the latter sum, by Example 7,

Article 6.1. 0

At first glance, the relation "congruence modulo 5" seems to be an

exception to our earlier statement that objects related by an equivalence

relation share something in common. The fact that - 2 is congruent to 13,

modulo 5, seems to be saying something only about the diflerence of the two

numbers, not about any property that the numbers might have in common.

-- It can be proved, however, that two integers m and n are congruent modulo

5 if and only if both yield the same remainder upon division by 5, in ac-

cordance with the conditions of the division algorithm for Z (see Exercise 4).

It was observed earlier that a majority of the examples R, through R2,

in Article 7.1 are not equivalence relations. For each such relation, either

zero, one, or two of the three conditions RST are satisfied. An interesting

exercise is to find examples of relations corresponding to the eight possible

I

combinations of the three properties (e.g., R, NS, T or NR, NS, T, etc.).

EXAMPLE 4 Give two examples, one by means of listing ordered pairs, the

other described by a rule, of relations that are reflexive, symmetric, and

not transitive.