Discrete Mathematics for Computer Science

182 CHAPTER 3 Relations

Symmetric: If n =-m(mod p), then (n - m) = pk for some k e Z. So, (m - n)=

p(-k), giving m =- n(mod p).

Transitive: Suppose n = m(mod p) and m = k(mod p). Show that n =- k(mod p). The

hypothesis implies that (n - m) = ip and (m - k) = jp for some i, j e Z. Then, however,

(n - k) = (n - m) + (m - k) = ip +jp= (i + j)p

which gives n -k(mod p).

Since -- (mod p) is reflexive, symmetric, and transitive, it is an equivalence relation.

0

We will study this equivalence relation more carefully later. For now, the reader

might determine the elements of this relation when p = 8 and the universal set is

{0,1, 2,..., 24, 251.

Example4. Let Ubeanyset. ForX, Y CU, setX- YifXE)Y=(X-Y)U (Y-

X) is finite. Then, -is an equivalence relation on the subsets of U. The relation - is

uninteresting if U is finite.

Solution.

Reflexive: X E X = 0, which is finite, so X -X.

Symmetric: If X - Y, then X ED Y is finite. Recall that

X E Y = (X - Y) U (Y - X) = (Y - X) U (X - Y) = Y ( X

so Y X.

Transitive: Suppose X -Y and Y - Z, and show X - Z. It is given that X E Y is finite

and that Y • Z is finite. What must be shown is that X @ Z is finite. Figure 3.8 shows how

(X D Y) - (Y E Z) and (Y e Z) - (X E Y) contribute to (X D Z).

(X E Y) G (Y E Z) = (X E (Y E Y)) Z (is associative)

= (XE 0) z

=Xe3Z

Figure 3.8 How X D Z is formed.

Therefore, X e Z is also finite, implying that X - Z. Since -is reflexive, transitive,

and symmetric, the relation -'• is an equivalence relation. U

Some relations on R that were defined earlier are not equivalence relations.