Page 630 - Discrete Mathematics and Its Applications

9.5 Equivalence Relations 609

Solution: Because a − a = 0 is an integer for all real numbers a, aRa for all real numbers a.
Hence, R is reflexive. Now suppose that aRb. Then a − b is an integer, so b − a is also an
integer. Hence, bRa. It follows that R is symmetric. If aRb and bRc, then a − b and b − c
are integers. Therefore, a − c = (a − b) + (b − c) is also an integer. Hence, aRc. Thus, R is
transitive. Consequently, R is an equivalence relation. ▲
One of the most widely used equivalence relations is congruence modulo m, where m is an
integer greater than 1.
EXAMPLE 3 Congruence Modulo m Let m be an integer with m> 1. Show that the relation

R ={(a, b) | a ≡ b(mod m)}

is an equivalence relation on the set of integers.
Solution: Recall from Section 4.1 that a ≡ b (mod m) if and only if m divides a − b. Note
that a − a = 0 is divisible by m, because 0 = 0 · m. Hence, a ≡ a (mod m), so congruence
modulo m is reflexive. Now suppose that a ≡ b (mod m). Then a − b is divisible by m,so
a − b = km, where k is an integer. It follows that b − a = (−k)m,so b ≡ a (mod m). Hence,
congruence modulo m is symmetric. Next, suppose that a ≡ b (mod m) and b ≡ c (mod m).
Then m divides both a − b and b − c. Therefore, there are integers k and l with a − b = km and
b − c = lm. Adding these two equations shows that a − c = (a − b) + (b − c) = km + lm =
(k + l)m. Thus, a ≡ c (mod m). Therefore, congruence modulo m is transitive. It follows that
congruence modulo m is an equivalence relation. ▲

EXAMPLE 4 Suppose that R is the relation on the set of strings of English letters such that aRb if and only
if l(a) = l(b), where l(x) is the length of the string x.Is R an equivalence relation?
Solution: Because l(a) = l(a), it follows that aRa whenever a is a string, so that R is reflex-
ive. Next, suppose that aRb, so that l(a) = l(b). Then bRa, because l(b) = l(a). Hence, R
is symmetric. Finally, suppose that aRb and bRc. Then l(a) = l(b) and l(b) = l(c). Hence,
l(a) = l(c),so aRc. Consequently, R is transitive. Because R is reflexive, symmetric, and
transitive, it is an equivalence relation. ▲

EXAMPLE 5 Let n be a positive integer and S a set of strings. Suppose that R n is the relation on S such
that sR n t if and only if s = t, or both s and t have at least n characters and the first n characters
of s and t are the same. That is, a string of fewer than n characters is related only to itself; a
string s with at least n characters is related to a string t if and only if t has at least n characters
and t begins with the n characters at the start of s. For example, let n = 3 and let S be the set
of all bit strings. Then sR 3 t either when s = t or both s and t are bit strings of length 3 or more
that begin with the same three bits. For instance, 01R 3 01 and 00111R 3 00101, but 01 R 3 010
and 01011 R 3 01110.
Show that for every set S of strings and every positive integer n, R n is an equivalence
relation on S.

Solution: The relation R n is reflexive because s = s, so that sR n s whenever s is a string in S.
If sR n t, then either s = t or s and t are both at least n characters long that begin with the
same n characters. This means that tR n s. We conclude that R n is symmetric.
Now suppose that sR n t and tR n u. Then either s = t or s and t are at least n characters
long and s and t begin with the same n characters, and either t = u or t and u are at least n
characters long and t and u begin with the same n characters. From this, we can deduce that
either s = u or both s and u are n characters long and s and u begin with the same n characters
(because in this case we know that s, t, and u are all at least n characters long and both s and u
begin with the same n characters as t does). Consequently, R n is transitive. It follows that R n is
an equivalence relation. ▲