Page 631 - Discrete Mathematics and Its Applications

610 9 / Relations

In Examples 6 and 7 we look at two relations that are not equivalence relations.
EXAMPLE 6 Show that the “divides” relation is the set of positive integers in not an equivalence relation.

Solution: By Examples 9 and 15 in Section 9.1, we know that the “divides” relation is reflex-
ive and transitive. However, by Example 12 in Section 9.1, we know that this relation is not
symmetric (for instance, 2 | 4 but 4 | 2). We conclude that the “divides” relation on the set of
positive integers is not an equivalence relation. ▲

EXAMPLE 7 Let R be the relation on the set of real numbers such that xRy if and only if x and y are real
numbers that differ by less than 1, that is |x − y| < 1. Show that R is not an equivalence relation.

Solution: R is reflexive because |x − x|= 0 < 1 whenever x ∈ R. R is symmetric, for if xRy,
where x and y are real numbers, then |x − y| < 1, which tells us that |y − x|=|x − y| < 1, so
that yRx. However, R is not an equivalence relation because it is not transitive. Take x = 2.8,
y = 1.9, and z = 1.1, so that |x − y|=|2.8 − 1.9|= 0.9 < 1, |y − z|=|1.9 − 1.1|=
0.8 < 1, but |x − z|=|2.8 − 1.1|= 1.7 > 1. That is, 2.8R 1.9, 1.9R 1.1, but 2.8 R 1.1. ▲

Equivalence Classes

Let A be the set of all students in your school who graduated from high school. Consider the
relation R on A that consists of all pairs (x, y), where x and y graduated from the same high
school. Given a student x, we can form the set of all students equivalent to x with respect to R.
This set consists of all students who graduated from the same high school as x did. This subset
of A is called an equivalence class of the relation.

DEFINITION 3 Let R be an equivalence relation on a set A. The set of all elements that are related to an
element a of A is called the equivalence class of a. The equivalence class of a with respect
to R is denoted by [a] R . When only one relation is under consideration, we can delete the
subscript R and write [a] for this equivalence class.

In other words, if R is an equivalence relation on a set A, the equivalence class of the
element a is

[a] R ={s | (a, s) ∈ R}.

If b ∈[a] R , then b is called a representative of this equivalence class. Any element of a class
can be used as a representative of this class. That is, there is nothing special about the particular
element chosen as the representative of the class.

EXAMPLE 8 What is the equivalence class of an integer for the equivalence relation of Example 1?

Solution: Because an integer is equivalent to itself and its negative in this equivalence relation,
it follows that [a]={−a, a}. This set contains two distinct integers unless a = 0. For instance,
[7]={−7, 7}, [−5]={−5, 5}, and [0]={0}. ▲

EXAMPLE 9 What are the equivalence classes of 0 and 1 for congruence modulo 4?

Solution: The equivalence class of 0 contains all integers a such that a ≡ 0 (mod 4). The integers
in this class are those divisible by 4. Hence, the equivalence class of 0 for this relation is

[0]={..., −8, −4, 0, 4, 8,... }.