Page 632 - Discrete Mathematics and Its Applications

9.5 Equivalence Relations 611

The equivalence class of 1 contains all the integers a such that a ≡ 1 (mod 4). The integers
in this class are those that have a remainder of 1 when divided by 4. Hence, the equivalence
class of 1 for this relation is
[1]={..., −7, −3, 1, 5, 9,... }. ▲

In Example 9 the equivalence classes of 0 and 1 with respect to congruence modulo 4
were found. Example 9 can easily be generalized, replacing 4 with any positive integer m.
The equivalence classes of the relation congruence modulo m are called the congruence
classes modulo m. The congruence class of an integer a modulo m is denoted by [a] m ,so
[a] m ={...,a − 2m, a − m, a, a + m, a + 2m,...}. For instance, from Example 9 it follows
that [0] 4 ={..., −8, −4, 0, 4, 8,... } and [1] 4 ={..., −7, −3, 1, 5, 9,... }.
EXAMPLE 10 What is the equivalence class of the string 0111 with respect to the equivalence relation R 3 from
Example 5 on the set of all bit strings? (Recall that sR 3 t if and only if s and t are bit strings
with s = t or s and t are strings of at least three bits that start with the same three bits.)

Solution: The bit strings equivalent to 0111 are the bit strings with at least three bits that begin
with 011. These are the bit strings 011, 0110, 0111, 01100, 01101, 01110, 01111, and so on.
Consequently,

={011, 0110, 0111, 01100, 01101, 01110, 01111,...}. ▲
[011] R 3

EXAMPLE 11 Identifiers in the C Programming Language In the C programming language, an identifier
is the name of a variable, a function, or another type of entity. Each identifier is a nonempty
string of characters where each character is a lowercase or an uppercase English letter, a digit,
or an underscore, and the first character is a lowercase or an uppercase English letter. Identifiers
can be any length. This allows developers to use as many characters as they want to name an
entity, such as a variable. However, for compilers for some versions of C, there is a limit on the
number of characters checked when two names are compared to see whether they refer to the
same thing. For example, Standard C compilers consider two identifiers the same when they
agree in their first 31 characters. Consequently, developers must be careful not to use identifiers
with the same initial 31 characters for different things. We see that two identifiers are considered
the same when they are related by the relation R 31 in Example 5. Using Example 5, we know
that R 31 , on the set of all identifiers in Standard C, is an equivalence relation.
What are the equivalence classes of each of the identifiers Number_of_tropical_
storms, Number_of_named_tropical_storms, and Number_of_named_tropical_storms_in_the_
Atlantic_in_2005?

Solution: Note that when an identifier is less than 31 characters long, by the definition of R 31 ,
its equivalence class contains only itself. Because the identifier Number_of_tropical_storms is
25 characters long, its equivalence class contains exactly one element, namely, itself.
The identifier Number_of_named_tropical_storms is exactly 31 characters long. An identi-
fier is equivalent to it when it starts with these same 31 characters. Consequently, every identifier
at least 31 characters long that starts with Number_of_named_tropical_storms is equivalent to
this identifier. It follows that the equivalence class of Number_of_named_tropical_storms is the
set of all identifiers that begin with the 31 characters Number_of_named_tropical_storms.
An identifier is equivalent to the Number_of_named_tropical_storms_in_the_Atlantic_in_
2005 if and only if it begins with its first 31 characters. Because these characters
are Number_of_named_tropical_storms, we see that an identifier is equivalent to Num-
ber_of_named_tropical_storms_in_the_Atlantic_in_2005 if and only if it is equivalent to Num-
ber_of_named_tropical_storms. It follows that these last two identifiers have the same equiva-
lence class. ▲