Skip to main content
🔗

Section 7.3 Equivalence Classes

🔗

Beginning Activity Beginning Activity 1: Sets Associated with a Relation
A4US

🔗
As was indicated in Section 7.2, an equivalence relation on a set A is a relation with a certain combination of properties (reflexive, symmetric, and transitive) that allow us to sort the elements of the set into certain classes. This is done by means of certain subsets of A that are associated with the e lements of the set A. This will be illustrated with the following example. Let A={a,b,c,d,e}, and let R be the relation on the set A defined as follows:

aRabRbcRcdRdeReaRbbRabReeRbaReeRacRddRc

🔗
For each y∈A, define the subset R[y] of A as follows:

R[y]={x∈A∣xRy}.

🔗
That is, R[y] consists of those elements in A such that xRy. For example, using y=a, we see that aRa, bRa, and eRa, and so R[a]={a,b,e}.

🔗

1.

Determine R[b], R[c], R[d], and R[e].

🔗

2.

Draw a directed graph for the relation R and explain why R is an equivalence relation on A.

🔗

3.

Which of the sets R[a], R[b], R[c], R[d], and R[e] are equal?

🔗

4.

Which of the sets R[a], R[b], R[c], R[d], and R[e] are disjoint?

🔗
As we will see in this section, the relationships between these sets are typical for an equivalence relation. The following example will show how different this can be for a relation that is not an equivalence relation.

🔗
Let A={a,b,c,d,e}, and let S be the relation on the set A defined as follows:

bSbcScdSdeSeaSbaSdbSccSddSc

🔗

🔗

5.

Draw a digraph that represents the relation S on A. Explain why S is not an equivalence relation on A.

🔗

🔗
For each y∈A, define the subset S[y] of A as follows:

S[y]={x∈A∣xSy}={x∈A∣(x,y)∈S}.

🔗
For example, using y=b, we see that S[b]={a,b} since (a,b)∈S and (b,b)∈S. In addition, we see that S[a]=∅ since there is no x∈A such that (x,a)∈S.

🔗

6.

Determine S[c], S[d], and S[e].

🔗

7.

Which of the sets S[a], S[b], S[c], S[d], and S[e] are equal?

🔗

8.

Which of the sets S[b], S[c], S[d], and S[e] are disjoint?

🔗

Beginning Activity Beginning Activity 2: Congruence Modulo 3
A4US

🔗
An important equivalence relation that we have studied is congruence modulo n on the integers. We can also define subsets of the integers based on congruence modulo n. We will illustrate this with congruence modulo 3. For example, we can define C[0] to be the set of all integers a that are congruent to 0 modulo 3. That is,

C[0]={a∈Z∣a≡0(mod3)}.

🔗
Since an integer a is congruent to 0 modulo 3 if and only if 3 divides a, we can use the roster method to specify this set as follows:

C[0]={…,−9,−6,−3,0,3,6,9,…}.
🔗

1.

Use the roster method to specify each of the following sets:

🔗
(a)

The set C[1] of all integers a that are congruent to 1 modulo 3. That is, C[1]={a∈Z∣a≡1(mod3)}.

🔗
(b)

The set C[2] of all integers a that are congruent to 2 modulo 3. That is, C[2]={a∈Z∣a≡2(mod3)}.

🔗
(c)

The set C[3] of all integers a that are congruent to 3 modulo 3. That is, C[3]={a∈Z∣a≡3(mod3)}.

🔗

2.

Now consider the three sets, C[0], C[1], and C[2].

🔗
(a)

Determine the intersection of any two of these sets. That is, determine C[0]∩C[1], C[0]∩C[2], and C[1]∩C[2].

🔗
(b)

Let n=734. What is the remainder when n is divided by 3? Which of the three sets, if any, contains n=734?

🔗
(d)

Do you think that C[0]∪C[1]∪C[2]=Z? Explain.

🔗
(e)

Is the set C[3] equal to one of the sets C[0],C[1], or C[2]?

🔗
(f)

We can also define C[4]={a∈Z∣a≡4(mod3)}. Is this set equal to any of the previous sets we have studied in this part? Explain.

🔗

Subsection The Definition of an Equivalence Class

🔗
We have indicated that an equivalence relation on a set is a relation with a certain combination of properties (reflexive, symmetric, and transitive) that allow us to sort the elements of the set into certain classes. We saw this happen in the beginning activities. We can now illustrate specifically what this means. For example, in Beginning Activity 2, we used the equivalence relation of congruence modulo 3 on Z to construct the following three sets:

C[0]={a∈Z∣a≡0(mod3)},C[1]={a∈Z∣a≡1(mod3)}, and C[2]={a∈Z∣a≡2(mod3)}.

🔗
The main results that we want to use now are Theorem 3.37 and Corollary 3.38. This corollary tells us that for any a∈Z, a is congruent to precisely one of the integers 0, 1, or 2. Consequently, the integer a must be congruent to 0, 1, or 2, and it cannot be congruent to two of these numbers. Thus

  1. For each a∈Z, a∈C[0], a∈C[1], or a∈C[2]; and

  2. C[0]∩C[1]=∅, C[0]∩C[2]=∅ , and C[1]∩C[2]=∅.

🔗
This means that the relation of congruence modulo 3 sorts the integers into three distinct sets, or classes, and that each pair of these sets have no elements in common. So if we use a rectangle to represent Z, we can divide that rectangle into three smaller rectangles, corresponding to C[0], C[1], and C[2], and we might picture this situation as follows:

The Integers
C[0] consisting
of all integers with a
remainder of 0 when
divided by 3		 C[1] consisting
of all integers with a
remainder of 1 when
divided by 3		 C[2] consisting
of all integers with a
remainder of 2 when
divided by 3

🔗
Each integer is in exactly one of the three sets C[0], C[1], or C[2], and two integers are congruent modulo 3 if and only if they are in the same set. We will see that, in a similar manner, if n is any natural number, then the relation of congruence modulo n can be used to sort the integers into n classes. We will also see that in general, if we have an equivalence relation R on a set A, we can sort the elements of the set A into classes in a similar manner.

🔗

Definition.

Let ∼ be an equivalence relation on a nonempty set A. For each a∈A, the equivalence class of a determined by ∼ is the subset of A, denoted by [a], consisting of all the elements of A that are equivalent to a. That is,

[a]={x∈A∣x∼a}.

We read [a] as “the equivalence class of a” or as “bracket a.”

🔗

Notes.

  1. We use the notation [a] when only one equivalence relation is being used. If there is more than one equivalence relation, then we need to distinguish between the equivalence classes for each relation. We often use something like [a]∼, or if R is the name of the relation, we can use R[a] or [a]R for the equivalence class of a determined by R. In any case, always remember that when we are working with any equivalence relation on a set A if a∈A, then the equivalence class [a] is a subset of A.

  2. We know that each integer has an equivalence class for the equivalence relation of congruence modulo 3. But as we have seen, there are really only three distinct equivalence classes. Using the notation from the definition, they are:

    [0]={a∈Z∣a≡0(mod3)},[1]={a∈Z∣a≡1(mod3)}, and [2]={a∈Z∣a≡2(mod3)}.
🔗

Progress Check 7.16. Equivalence Classes from Beginning Activity 1.

Without using the terminology at that time, we actually determined the equivalence classes of the equivalence relation R in Beginning Activity 1. What are the distinct equivalence classes for this equivalence relation?

Solution.

The distinct equivalence classes for the relation R are: {a,b,e} and {c,d}.

🔗

Subsection Congruence Modulo n and Congruence Classes

🔗
In Beginning Activity 2, we used the notation C[k] for the set of all integers that are congruent to k modulo 3. We could have used a similar notation for equivalence classes, and this would have been perfectly acceptable. However, the notation [a] is probably the most common notation for the equivalence class of a. We will now use this same notation when dealing with congruence modulo n when only one congruence relation is under consideration.

🔗

Definition.

Let n∈N. Congruence modulo n is an equivalence relation on Z. So for a∈Z,

[a]={x∈Z∣x≡a(modn)}.

In this case, [a] is called the congruence class of a modulo n.

🔗
We have seen that congruence modulo 3 divides the integers into three distinct congruence classes. Each congruence class consists of those integers with the same remainder when divided by 3. In a similar manner, if we use congruence modulo 2, we simply divide the integers into two classes. One class will consist of all the integers that have a remainder of 0 when divided by 2, and the other class will consist of all the integers that have a remainder of 1 when divided by 2. That is, congruence modulo 2 simply divides the integers into the even and odd integers.

🔗

Progress Check 7.17. Congruence Modulo 4.

Determine all of the distinct congruence classes for the equivalence relation of congruence modulo 4 on the integers. Specify each congruence class using the roster method.

Solution.

The distinct congruence classes for congruence modulo 4 are

[0]={…,−12,−8,−4,0,4,8,12,…}[1]={…,−11,−7,−3,1,5,9,13,…}[2]={…,−10,−6,−2,2,6,10,14,…}[3]={…,−9,−5,−1,3,7,11,15,…}.
🔗

Subsection Properties of Equivalence Classes

🔗
As we have seen, in Beginning Activity 1, the relation R was an equivalence relation. For that activity, we used R[y] to denote the equivalence class of y∈A, and we observed that these equivalence classes were either equal or disjoint.

🔗
However, in Beginning Activity 1, the relation S was not an equivalence relation, and hence we do not use the term “equivalence class” for this relation. We should note, however, that the sets S[y] were not equal and were not disjoint. This exhibits one of the main distinctions between equivalence relations and relations that are not equivalence relations.

🔗
In Theorem 7.18, we will prove that if ∼ is an equivalence relation on the set A, then we can “sort” the elements of A into distinct equivalence classes. The properties of equivalence classes that we will prove are as follows: (1) Every element of A is in its own equivalence class; (2) two elements are equivalent if and only if their equivalence classes are equal; and (3) two equivalence classes are either identical or they are disjoint.

🔗

Proof.

Let A be a nonempty set and assume that ∼ is an equivalence relation on A. To prove the first part of the theorem, let a∈A. Since ∼ is an equivalence relation on A, it is reflexive on A. Thus, a∼a, and we can conclude that a∈[a].

The second part of this theorem is a biconditional statement. We will prove it by proving two conditional statements. We will first prove that if a∼b, then [a]=[b]. So let a,b∈A and assume that a∼b. We will now prove that the two sets [a] and [b] are equal. We will do this by proving that each is a subset of the other.

First, assume that x∈[a]. Then, by definition, x∼a. Since we have assumed that a∼b, we can use the transitive property of ∼ to conclude that x∼b, and this means that x∈[b]. This proves that [a]⊆[b].

We now assume that y∈[b]. This means that y∼b, and hence by the symmetric property, that b∼y. Again, we are assuming that a∼b. So we have a∼b and b∼y. We use the transitive property to conclude that a∼y and then, using the symmetric property, we conclude that y∼a. This proves that y∈[a] and, hence, that [b]⊆[a]. This means that we can conclude that if a∼b, then [a]=[b].

We must now prove that if [a]=[b], then a∼b. Let a,b∈A and assume that [a]=[b]. Using the first part of the theorem, we know that a∈[a] and since the two sets are equal, this tells us that a∈[b]. Hence by the definition of [b], we conclude that a∼b. This completes the proof of the second part of the theorem.

For the third part of the theorem, let a,b∈A. Since this part of the theorem is a disjunction, we will consider two cases: Either

[a]∩[b]=∅ or [a]∩[b]≠∅.

In the case where [a]∩[b]=∅, the first part of the disjunction is true, and hence there is nothing to prove. So we assume that [a]∩[b]≠∅ and will show that [a]=[b]. Since [a]∩[b]≠∅, there is an element x in A such that

x∈[a]∩[b].

This means that x∈[a] and x∈[b]. Consequently, x∼a and x∼b, and so we can use the second part of the theorem to conclude that [x]=[a] and [x]=[b]. Hence, [a]=[b], and we have proven that [a]=[b] or [a]∩[b]=∅.

🔗
Theorem 7.18 gives the primary properties of equivalence classes. Consequences of these properties will be explored in the exercises. The following table restates the properties in Theorem 7.18 and gives a verbal description of each one.

Formal Statement from
Theorem 7.18 		Verbal Description
For each a∈A, a∈[a]. Every element of A is in its own
equivalence class.
For each a,b∈A, a∼b if and
only if [a]=[b]. 		Two elements of A are equivalent if
and only if their equivalence classes
are equal.
For each a,b∈A, [a]=[b] or
[a]∩[b]=∅. 		Any two equivalence classes are
either equal or they are disjoint.
This means that if two equivalence classes
are not disjoint then they
must be equal.
🔗

Progress Check 7.19. Equivalence Classes.

Let f:R→R be defined by f(x)=x2−4 for each x∈R. Define a relation ∼ on R as follows: For a,b∈R, a∼b if and only if f(a)=f(b). In Exercise 6 of Section 7.2, we proved that  ∼ is an equivalence relation on R. Consequently, each real number has an equivalence class. For this equivalence relation,

🔗
(a)

Determine the equivalence classes of 5, −5, 10, −10, π, and −π.

Solution.

[5]=[−5]={−5,5}

[10]=[−10]={−10,10}

[π]=[−π]={−π,π}

🔗
(c)

If a∈R, use the roster method to specify the elements of the equivalence class [a].

Solution.

[a]={−a,a}

🔗
The results of Theorem 7.18 are consistent with all the equivalence relations studied in the beginning activities and in the progress checks. Since this theorem applies to all equivalence relations, it applies to the relation of congruence modulo n on the integers. Because of the importance of this equivalence relation, these results for congruence modulo n are given in the following corollary.

🔗
For the equivalence relation of congruence modulo n, Theorem 3.37 and Corollary 3.38 tell us that each integer is congruent to its remainder when divided by n, and that each integer is congruent modulo n to precisely one of one of the integers 0,1,2,…,n−1. This means that each integer is in precisely one of the congruence classes [0], [1], [2],…,[n−1]. Hence, Corollary 7.20 gives us the following result.

🔗

Subsection Partitions and Equivalence Relations

🔗
A partition of a set A is a collection of subsets of A that “breaks up” the set A into disjoint subsets. Technically, each pair of distinct subsets in the collection must be disjoint. We then say that the collection of subsets is pairwise disjoint. We introduce the following formal definition.

🔗

Definition.

Let A be a nonempty set, and let C be a collection of subsets of A. The collection of subsets C is a partition of A provided that

  1. For each V∈C, V≠∅.

  2. For each x∈A, there exists a V∈C such that x∈V.

  3. For every V,W∈C, V=W or V∩W=∅.

🔗
There is a close relation between partitions and equivalence classes since the equivalence classes of an equivalence relation form a partition of the underlying set, as will be proven in Theorem 7.22. The proof of this theorem relies on the results in Theorem 7.18.

🔗

Proof.

Let ∼ be an equivalence relation on the nonempty set A, and let C be the collection of all equivalence classes determined by ∼. That is,

C={[a]∣a∈A}.

We will use Theorem 7.18 to prove that C is a partition of A.

Item 1 of Theorem 7.18 states that for each a∈A, a∈[a]. In terms of the equivalence classes, this means that each equivalence class is nonempty since each element of A is in its own equivalence class. Consequently, C, the collection of all equivalence classes determined by ∼, satisfies the first two conditions of the definition of a partition.

We must now show that the collection C of all equivalence classes determined by ∼ satisfies the third condition for being a partition. That is, we need to show that any two equivalence classes are either equal or are disjoint. However, this is exactly the result in Item 3 of Theorem 7.18.

Hence, we have proven that the collection C of all equivalence classes determined by ∼ is a partition of the set A.

🔗
Note: Theorem 7.22 has shown us that if ∼ is an equivalence relation on a nonempty set A, then the collection of the equivalence classes determined by ∼ form a partition of the set A.

🔗
This process can be reversed. This means that given a partition C of a nonempty set A, we can define an equivalence relation on A whose equivalence classes are precisely the subsets of A that form the partition. This will be explored in Activity 44.

🔗

Exercises Exercises

🔗

1.

Let A={a,b,c,d,e} and let ∼ be the relation on A that is represented by the directed graph in Figure 7.23.

Figure 7.23. Directed Graph for the Relation in Exercise 1
Prove that ∼ is an equivalence relation on the set A, and determine all of the equivalence classes determined by this equivalence relation.

Answer.

Use the directed graph to examine all the cases necessary to prove that ∼ is reflexive, symmetric, and transitive. The distinct equivalence classes are: [a]=[b]={a,b}; [c]={c}; [d]=[e]={d,e}

🔗

2.

Let A={a,b,c,d,e,f}, and assume that ∼ is an equivalence relation on A. Also assume that it is known that

a∼ba≁ce∼fa∼da≁fe≁c

Draw a complete directed graph for the equivalence relation ∼ on the set A, and then determine all of the equivalence classes for this equivalence relation.

Answer.

The equivalence class are

[a]=[b]=[d]={a,b,d},[c]={c},[e]=[f]={e,f}.

Following is the directed graph for this equivalence relation.

🔗

3.

Let A={0,1,2,3,…,999,1000}. Define the relation R on A as follows:

For x,y∈A, xRy if and only if x and y have the same number of digits.
Prove that R is an equivalence relation on the set A and determine all of the distinct equivalence classes determined by R.

Answer.

Let x∈A. Since x has the same number of digits as itself, the relation R is reflexive. Now let x,y,z∈A. If xRy, then x and y have the same number of digits. Hence, y and x have the same number of digits and yRx, and so R is symmetric.

If xRy and yRz,then x and y have the same number of digits and y and z have the same number of digits. Hence, x and z have the same number of digits, and so xRz. Therefore, R is transitive.

The equivalence classes are: {0,1,2,…,9}, {10,11,12,…,99}, {100,101,102,…,999}, {1000}.

🔗

4.

Determine all of the congruence classes for the relation of congruence modulo 5 on the set of integers.

Answer.

The congruence classes for the relation of congruence modulo 5 on the set of integers are

[0]={5n∣n∈Z}[1]={5n+1∣n∈Z}[2]={5n+2∣n∈Z}[3]={5n+3∣n∈Z}[4]={5n+4∣n∈Z}
🔗

5.

Let Z9={0,1,2,3,4,5,6,7,8}.

🔗
(a)

Define the relation ∼ on Z9 as follows: For all a,b∈Z9, a∼b if and only if a2≡b2(mod9). Prove that ∼ is an equivalence relation on Z9 and determine all of the distinct equivalence classes of this equivalence relation.

Answer.

Let a,b,c∈Z9. Since a2≡a2(mod9), we see that a∼a and ∼ is reflexive. Let a,b,c∈Z9. If a∼b, then a2≡b2(mod9) and hence, by the symmetric property of congruence, b2≡a2(mod9). This proves that ∼ is symmetric. Finally, if a∼b and b∼c, then a2≡b2(mod9) and b2≡c2(mod9). By the transitive property of congruence, we conclude that a2≡c2(mod9) and hence, a∼c. This proves that ∼ is transitive. The distinct equivalence classes are {0,3,6}, {1,8}, {2,7}, and {4,5}.

🔗
(b)

Define the relation ≈ on Z9 as follows: For all a,b∈Z9, a≈b if and only if a3≡b3(mod9). Prove that ≈ is an equivalence relation on Z9 and determine all of the distinct equivalence classes of this equivalence relation.

🔗

6.

Define the relation ∼ on Q as follows: For a,b∈Q, a∼b if and only if a−b∈Z. In Progress Check 7.13 of Section 7.2, we showed that the relation ∼ is an equivalence relation on Q. Also, see Exercise 9 in Section 7.2.

🔗
(a)

Prove that [57]={m+57|m∈Z}.

Answer.

Let x∈[57]. Then x−57∈Z, which means that there is an integer m such that x−57=m, or x=57+m. This proves that x∈{m+57|m∈Z} and, hence, that [57]⊆{m+57|m∈Z}. We still need to prove that {m+57|m∈Z}⊆[57].

🔗
(b)

If a∈Z, then what is the equivalence class of a?

🔗
(c)

If a∈Z, prove that there is a bijection from [a] to [57].

🔗

7.

Define the relation ∼ on R as follows:

For x,y∈R, x∼y if and only if x−y∈Q.

🔗
(a)

Prove that ∼ is an equivalence relation on R.

🔗
(b)

List four different real numbers that are in the equivalence class of 2.

🔗
(c)

If a∈Q, what is the equivalence class of a?

🔗
(d)

Prove that [2]={r+2∣r∈Q}.

🔗
(e)

If a∈Q, prove that there is a bijection from [a] to [2].

🔗

8.

Define the relation ∼ on Z as follows: For a,b∈Z, a∼b if and only if 2a+3b≡0(mod5). The relation ∼ is an equivalence relation on Z. (See Exercise 13 in Section 7.2). Determine all the distinct equivalence classes for this equivalence relation.

🔗

9.

Let A=Z×(Z−{0}). That is, A={(a,b)∈Z×Z∣b≠0}. Define the relation ≈ on A as follows:

For (a,b),(c,d)∈A, (a,b)≈(c,d) if and only if ad=bc.

🔗
(a)

Prove that ≈ is an equivalence relation on A.

Answer.

To prove the relation is symmetric, note that if (a,b)≈(c,d), then ad=bc. This implies that cb=da and, hence, (c,d)≈(a,b).

🔗
(b)

Why was it necessary to include the restriction that b≠0 in the definition of the set A?

🔗
(c)

Determine an equation that gives a relation between a and b if (a,b)∈A and (a,b)≈(2,3).

Answer.

3a=2b

🔗
(d)

Determine at least four different elements in [(2,3)], the equivalence class of (2,3).

🔗
(e)

Use set builder notation to describe [(2,3)], the equivalence class of (2,3).

🔗

10.

For (a,b),(c,d)∈R×R, define (a,b)∼(c,d) if and only if a2+b2=c2+d2. In Exercise 15 of Section 7.2, we proved that ∼ is an equivalence relation on R×R.

🔗
(a)

Determine the equivalence class of (0,0).

🔗
(b)

Use set builder notation (and do not use the symbol ∼) to describe the equivalence class of (2,3) and then give a geometric description of this equivalence class.

🔗
(c)

Give a geometric description of a typical equivalence class for this equivalence relation.

🔗
(d)

Let R∗={x∈R∣x≥0}. Prove that there is a one-to-one correspondence (bijection) between R∗ and the set of all equivalence classes for this equivalence relation.

🔗

11.

Let A be a nonempty set and let ∼ be an equivalence relation on A. Prove each of the following:

🔗
(a)

For each a,b∈A, a≁b if and only if [a]∩[b]=∅.

🔗
(b)

For each a,b∈A, if [a]≠[b], then [a]∩[b]=∅.

🔗
(c)

For each a,b∈A, if [a]∩[b]≠∅ then [a]=[b].

🔗

Activity 44. A Partition Defines an Equivalence Relation.

Let A={a,b,c,d,e} and let C={{a,b,c},{d,e}}.

🔗
(a)

Explain why C is a partition of A.

🔗
(b)

Define a relation ∼ on A as follows: For x,y∈A, x∼y if and only if there exists a set U in C such that x∈U and y∈U.

Prove that ∼ is an equivalence relation on the set A, and then determine all the equivalence classes for ∼. How does the collection of all equivalence classes compare to C?

🔗
(c)

What we did for the specific partition in Task 44.b can be done for any partition of a set. So to generalize Task 44.b, we let A be a nonempty set and let C be a partition of A. We then define a relation ∼ on A as follows:

For x,y∈A, x∼y if and only if there exists a set U in C such that x∈U and y∈U.

Prove that ∼ is an equivalence relation on the set A.

🔗
(d)

Let a∈A and let U∈C such that a∈U. Prove that [a]=U.

🔗

Activity 45. Equivalence Relations on a Set of Matrices.

The following exercises require a knowledge of elementary linear algebra. We let Mn,n(R) be the set of all n by n matrices with real number entries.

🔗
(a)

Define a relation ∼ on Mn,n(R) as follows: For all A,B∈Mn,n(R), A∼B if and only if there exists an invertible matrix P in Mn,n(R) such that B=PAP−1. Is ∼ an equivalence relation on Mn,n(R)? Justify your conclusion.

🔗
(b)

Define a relation R on Mn,n(R) as follows: For all A,B∈Mn,n(R), ARB if and only if  det (A)= det (B). Is R an equivalence relation on Mn,n(R)? Justify your conclusion.

🔗
(c)

Let ∼ be an equivalence relation on R. Define a relation ≈ on Mn,n(R) as follows: For all A,B∈Mn,n(R), A≈B if and only if  det (A)∼ det (B). Is ≈ an equivalence relation on Mn,n(R)? Justify your conclusion.