Page 629 - Discrete Mathematics and Its Applications

608 9 / Relations

uppercase or lowercase letters, digits, or underscores.) Consequently, the compiler considers
strings longer than eight characters that agree in their first eight characters the same. Let R be
the relation on the set of strings of characters such that sRt, where s and t are two strings, if s
and t are at least eight characters long and the first eight characters of s and t agree, or s = t.It
is easy to see that R is reflexive, symmetric, and transitive. Moreover, R divides the set of all
strings into classes, where all strings in a particular class are considered the same by a compiler
for traditional C.
The integers a and b are related by the “congruence modulo 4” relation when 4
divides a − b. We will show later that this relation is reflexive, symmetric, and transitive. It
is not hard to see that a is related to b if and only if a and b have the same remainder when
divided by 4. It follows that this relation splits the set of integers into four different classes.
When we care only what remainder an integer leaves when it is divided by 4, we need only
know which class it is in, not its particular value.
These two relations, R and congruence modulo 4, are examples of equivalence relations,
namely, relations that are reflexive, symmetric, and transitive. In this section we will show that
such relations split sets into disjoint classes of equivalent elements. Equivalence relations arise
whenever we care only whether an element of a set is in a certain class of elements, instead of
caring about its particular identity.

Equivalence Relations

In this section we will study relations with a particular combination of properties that allows
them to be used to relate objects that are similar in some way.

DEFINITION 1 A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and
transitive.

Equivalence relations are Equivalence relations are important throughout mathematics and computer science. One
important in every branch
of mathematics! reason for this is that in an equivalence relation, when two elements are related it makes sense
to say they are equivalent.

DEFINITION 2 Two elements a and b that are related by an equivalence relation are called equivalent. The
notation a ∼ b is often used to denote that a and b are equivalent elements with respect to a
particular equivalence relation.

For the notion of equivalent elements to make sense, every element should be equivalent to
itself, as the reflexive property guarantees for an equivalence relation. It makes sense to say
that a and b are related (not just that a is related to b) by an equivalence relation, because
when a is related to b, by the symmetric property, b is related to a. Furthermore, because an
equivalence relation is transitive, if a and b are equivalent and b and c are equivalent, it follows
that a and c are equivalent.
Examples 1–5 illustrate the notion of an equivalence relation.
EXAMPLE 1 Let R be the relation on the set of integers such that aRb if and only if a = b or a =−b.In
Section 9.1 we showed that R is reflexive, symmetric, and transitive. It follows that R is an
equivalence relation. ▲

EXAMPLE 2 Let R be the relation on the set of real numbers such that aRb if and only if a − b is an integer.
Is R an equivalence relation?