Equivalence Relations 181rnEquivalence Relations
Equivalence relations generalize the familiar relation of equality (=). More specifically,
equivalence relations identify elements that are the same in some respect. For instance,
university students are classified by major, with two students being "related" if they have
the same major. Two students are also "related" if they are in the same class, such as the
sophomore class.
Definition 1. Let R be a binary relation on a set X. R is an equivalence relation if R is
reflexive, symmetric, and transitive.
Example 1.
(a) For any set X, the equality relation (=) is an equivalence relation on X.
(b) The relation IsSameGeneration (see Section 3.1) as defined using Figure 3.2 is an
equivalence relation.
The IsSameGeneration relation as based on Figure 3.2 is not a particularly interest-
ing equivalence relation because there are so few elements. The reader is encouraged to
construct his or her own family tree for three or four generations and see how the relation
conveys information conveniently.
Example 2. The relation SameSuit (see Section 3.1) shown in Table 3.3 is an equivalence
relation.
Solution. It is obvious that SameSuit is reflexive and symmetric, but is SameSuit transi-
tive? Let cards x and y be in the same suit, and let cards y and z be in the same suit. Since
y is in the same suit as z and in the same suit as x, it follows that x and z are in the same
suit. Therefore, SameSuit is transitive. 0
Recall that when we divide a natural number n by a positive number p, we obtain an
integer quotient, which we will call q, and a remainder, which we will call r. That is, we
get an equation
n = pq + rwhere q, r e N and 0 < r < p - 1. For example, 7 + 3 = 2.3 + 1, so the quotient is 2,
the remainder is 1, and 7 = 3 • 2 + 1.
If the remainder is zero, then n = p • q, and we say that n is divisible by p.
Definition 2. Let p be a positive integer, and let x, y e N. We say that x is congruent to
y modulo p, and write x =_ y (mod p), if (x - y) is divisible by p; that is, (x - y) = m • p
for some integer m.
With this terminology, we will prove that (mod p) is an equivalence relation for p > 1.
Example 3. Let p be any natural number greater than zero. Then, = (mod p) is an equiv-
alence relation on N.
Solution. Check that all the properties hold:
Reflexive: For any n e N, (n - n) = 0 = p • 0, so (n - n) is divisible by p. Therefore,
n =_ n(modp).