Equivalence Relations

Section 8.3 Equivalence Relations

In Section 8.2 we studied three properties of a relation, the reflexive, symmetric, and transitive properties. These three properties are important for generalizing the idea of equality in mathematics. We may want to relate objects based on certain criteria; objects that share that criteria are “equivalent.” For example, you may recall from geometry, the idea of congruent triangles. Two triangles are congruent if they have the same angles. In geometry, we may not care at all about the lengths of the sides, just the angles. In this case, we relate triangles with the same angles and treat them as the same triangle.

🔗

Definition 8.3.1.

A relation that is reflexive, symmetric and transitive is an equivalence relation.

🔗

In Example 8.2.8 we proved that the relation given by

(m, n) \in R \Leftrightarrow 3 ∣ (m - n)

is an equivalence relation since we proved it is reflexive, symmetric, and transitive.

🔗

In fact, the proof can easily be adapted to show

(m, n) \in R \Leftrightarrow d ∣ (m - n)

is an equivalence relation for

d \neq 0, d \in Z .

The details are left as an exercise, Exercise 8.3.9

🔗

This relation is an important enough that it has its own definition.

🔗

Definition 8.3.2.

Let

m, n, d \in Z, d > 0 .

Then

m

and

n

are congruent modulo

d

d ∣ (m - n) .

🔗

We often just say

m

is congruent to

n

mod

d,

and denote it

🔗

m \equiv n \mod d .

🔗

Example 8.3.3. Congruence mod 3.

True or false:

7 \equiv 1 \mod 3 .

Answer 1.

Since

3 ∣ (7 - 1),

true.

True or false:

7 \equiv - 2 \mod 3 .

Answer 2.

Since

3 ∣ (7 + 2),

true.

True or false:

7 \equiv - 7 \mod 3 .

Answer 3.

Since

3 ∤ (7 + 7),

false.

True or false:

7 \equiv 2 \mod 3 .

Answer 4.

Since

3 ∤ (7 - 2),

false.

Let

R

be an equivalence relation on

A .

Let

a \in A .

The set

🔗

[a] = {b \in A : b R a}

is the equivalence class of

a .

🔗

Given a specific

a \in A,

we find the equivalence class of

a

by finding all the elements that are related to

a .

Keep in mind the equivalence class is a set, denoted

[a] .

🔗

Example 8.3.4. Equivalence Classes.

Consider the equivalence relation

m \equiv n \mod 3,

Z .

Find

[0],

the set of elements in

Z

equivalent to 0.

Answer 1.

[0] = {0, 3, - 3, 6, - 6, \dots} = {3 k : k \in Z}

Find

[1],

the set of elements in

Z

equivalent to 1.

Answer 2.

[1] = {1, 4, - 2, - 5, 7, 10, \dots} = {3 k + 1 : k \in Z}

Find

[2],

the set of elements in

Z

equivalent to 2.

Answer 3.

[2] = {2, 5, - 1, - 4, - 7, \dots} = {3 k + 2 : k \in Z}

Find

[3],

the set of elements in

Z

equivalent to 3.

Answer 4.

[3] = {0, 3, - 3, 6, - 6, \dots} = {3 k : k \in Z}

Find

[- 1],

the set of elements in

Z

equivalent to -1.

Answer 5.

[- 1] = {2, 5, - 1, - 4, - 7, \dots} = {3 k + 2 : k \in Z}

We can notice a few things from this last example. We can see that some of our equivalence classes are the same. In particular,

[0] = [3]

and

[2] = [- 1] .

In fact, there are only three distinct equivalence classes,

[0], [1], [2],

any other equivalence class will equal one of these.

🔗

A few other things to notice, distinct equivalence classes are disjoint--they have no elements in common. Also,

[a]

contains

a .

We may also recognize that the equivalence classes

[0], [1], [2]

partition the integers.

🔗

Example 8.3.5. More Equivalence Classes.

Consider the equivalence relation

A R B \Leftrightarrow | A | = | B |,

P ({1, 2, 3}) .

This is the relation where two subsets of

{1, 2, 3}

are related if they have the same number of elements. You can check that this is an equivalence relation.

Find

[\emptyset],

the set of elements in

P ({1, 2, 3})

equivalent to

\emptyset .

Answer 1.

[\emptyset] = {\emptyset},

Find

[{1}] .

Answer 2.

[{1}] = {{1}, {2}, {3}},

Find

[{1, 2}] .

Answer 3.

[{1, 2}] = {{1, 2}, {2, 3}, {1, 3}}

Find

[{1, 2, 3}] .

Answer 4.

[{1, 2, 3}] = {{1, 2, 3}}

Once again, the distinct equivalence classes are disjoint--they have no elements in common. Furthermore, the equivalence classes

[\emptyset], [{1}], [{1, 2}], [{1, 2, 3}]

partition the power set by size of the subset.

🔗

Activity 8.3.1.

Define the relation on

Z

x R y ⟺ | x | = | y | .

🔗

(a)

Prove

R

is an equivalence relation.

🔗

(b)

Find

[0]

and

[- 5] .

🔗

Activity 8.3.2.

Recall that

n \equiv m \mod 5 ⟺ 5 ∣ (m - n) .

🔗

(a)

Prove the relation

n R m ⟺ n \equiv m \mod 5

is an equivalence relation on

Z .

🔗

(b)

Find

[0]

and

[2] .

🔗

Activity 8.3.3.

Let

S = {1, 2, 3, 4, 5, 6} .

Let

A_{1} = {1, 2, 3}, A_{2} = {4}, A_{3} = {5, 6} .

🔗

(a)

Check the conditions in Definition 6.1.17 to show

{A_{i}}

is a partition of

S .

🔗

(b)

Define the relation on

S,

x R y ⟺

x

and

y

are in the same subset of the partition. Draw the directed graph for

R .

🔗

(c)

Show

R

is reflexive, symmetric and transitive.

🔗

(d)

Find

[1],

the equivalence class of 1.

🔗

(e)

Do you think this particular partition matters? Could we define this relation on any partition of any set and still have it be reflexive, symmetric and transitive?

🔗

There is an important connection between equivalence classes and partitions, as we see in the next two theorems.

🔗

Theorem 8.3.6.

Let

A

be a set and

R

an equivalence relation. The equivalence classes of

R

form a partition of

A

🔗

Conversely, as we saw in Activity 8.3.3, if we have a partition

{A_{1}, A_{2}, \dots, A_{n} \dots}

A

and define the relation

(a, b) \in R \Leftrightarrow a

and

b

are in the same subset

A_{i},

then

R

is an equivalence relation. We call this the equivalence relation induced by the partition.

🔗

Theorem 8.3.7.

Let

A

be a set and

{A_{1}, A_{2}, \dots, A_{n}, \dots}

be a partition of

A .

Let

R

be the relation induced by the partition. Then

R

is an equivalence relation.

🔗

We leave the details of the proof of Theorem 8.3.7 as an exercise.

🔗

The proof of Theorem 8.3.6 follows directly from the next two Lemmas.

🔗

Lemma 8.3.8.

Let

R

be an equivalence relation on

A

and

a, b \in A .

a R b

then

[a] = [b] .

🔗

Proof.

Since we want to show the sets are equal, we will show

[a], [b]

are subsets of each other.

Show

[a] \subseteq [b] .

Let

x \in [a] .

Then by defintion of equivalence class,

x R a .

We assumed

a R b .

By the transitive property,

x R b .

Thus,

x \in [b] .

Show

[b] \subseteq [a] .

Let

x \in [b] .

Then by definition of equivalence class,

x R b .

We assumed

a R b .

By the symmetric property,

b R a .

By the transitive property,

x R a .

Thus,

x \in [a] .

Lemma 8.3.8 really says that if two elements are related in an equivalence relation, they must have the same equivalence class. You can check this with the above examples. Note, we needed the symmetric and transitive properties to prove this lemma.

🔗

Lemma 8.3.9.

Let

R

be an equivalence relation on

A

and

a, b \in A .

Either

[a] \cap [b] = \emptyset

[a] = [b] .

🔗

Proof.

Assume

[a] \cap [b] \neq \emptyset .

We want to show

[a] = [b] .

Since

[a] \cap [b] \neq \emptyset,

there exists

x \in [a] \cap [b] .

This means

x R a

and

x R b .

By the symmetric property,

a R x .

By the transitive property, since

a R x

and

x R b,

we have

a R b .

By Lemma 8.3.8,

[a] = [b] .

Lemma 8.3.9 really says that any two equivalence classes are either disjoint or exactly the same.

🔗

Theorem 8.3.6 follows since, by the reflexive property,

x R x, \forall x \in A

means every element is in an equivalence class. Thus, the union of the equivalence classes is all of

A .

By Lemma 8.3.9 distinct equivalence classes are disjoint. Thus, we have a partition of

A .

🔗

Reading Questions Check Your Understanding

1.

Determine if the relation is an equivalence relation. If it is, give the number of distinct equivalence classes.

R

is the relation on

A = {1, 2, 3}

given by

🔗

a R b \Leftrightarrow a \leq b .

🔗

Not an equivalence relation.
Correct.
Equivalence relation with 1 equivalence class.
$R$ is not symmetric.
Equivalence relation with 2 equivalence classes.
$R$ is not symmetric.
Equivalence relation with 3 equivalence classes.
$R$ is not symmetric.

🔗

2.

Determine if the relation is an equivalence relation. If it is, give the number of distinct equivalence classes.

R

is the relation on

C = {0, 1}

given by

🔗

a R b \Leftrightarrow a + b is even .

🔗

Not an equivalence relation.
Check that $R$ is reflexive, symmetric, and transitive.
Equivalence relation with 1 equivalence class.
Is $0 R 1 ?$
Equivalence relation with 2 equivalence classes.
Correct. The equivalence classes are $[0] = {0}, [1] = {1} .$

🔗

3.

Determine if the relation is an equivalence relation. If it is, give the number of distinct equivalence classes.

R

is the relation on

B = {2, 4, 6, 8}

given by

🔗

a R b \Leftrightarrow a + b is even .

🔗

Not an equivalence relation.
Check that $R$ is reflexive, symmetric, and transitive.
Equivalence relation with 1 equivalence class.
Correct. The equivalence class is $[2] = {2, 4, 6, 8} .$
Equivalence relation with 2 equivalence classes.
Check that the sum of any two elements in $B$ is even. Thus, all elements are related to each other.

🔗

4.

Determine if the relation is an equivalence relation. If it is, give the number of distinct equivalence classes.

R

is the relation on

A = {1, 2, 3}

given by

🔗

a R b \Leftrightarrow a + b is even .

🔗

Not an equivalence relation.
Check that $R$ is reflexive, symmetric, and transitive.
Equivalence relation with 1 equivalence class.
Note, $2 + 3$ is odd, so 2 is not related to 3.
Equivalence relation with 2 equivalence classes.
Correct. The equivalence classes are $[1] = {1, 3}, [2] = {2} .$
Equivalence relation with 3 equivalence classes.
Note, $1 + 3$ is even, so 1 is related to 3.

🔗

5.

Determine if the relation is an equivalence relation. If it is, give the number of distinct equivalence classes.

R

is the relation on

B = {2, 4, 6, 8}

given by

🔗

a R b \Leftrightarrow a ∣ b .

🔗

Not an equivalence relation.
Correct.
Equivalence relation with 1 equivalence class.
$R$ is not symmetric.
Equivalence relation with 2 equivalence classes.
$R$ is not symmetric.
Equivalence relation with 4 equivalence classes.
$R$ is not symmetric.

🔗

6.

Determine if the relation is an equivalence relation. If it is, give the number of distinct equivalence classes.

R

is the relation on

Z

given by

🔗

a R b \Leftrightarrow a + b = 0.

🔗

Not an equivalence relation.
Correct.
Equivalence relation with 1 equivalence class.
$R$ is not transitive.
Equivalence relation with 2 equivalence classes.
$R$ is not transitive.
Equivalence relation with infinitely many equivalence classes.
$R$ is not transitive.

🔗

7.

Determine if the relation is an equivalence relation. If it is, find the equivalence classes.

R

is the relation on

Z

given by

🔗

a R b \Leftrightarrow a \equiv b \mod 4.

🔗

Not an equivalence relation.
Check that $R$ is reflexive, symmetric, and transitive.
Equivalence relation with 1 equivalence class.
Note, 2 is not equivalent to 1 mod 4. So there is more than one equivalence class.
Equivalence relation with 4 equivalence classes.
Correct. The equivalence classes are $[0] = {4 k : k \in Z},$ $[1] = {4 k + 1 : k \in Z},$ $[2] = {4 k + 2 : k \in Z},$ $[3] = {4 k + 3 : k \in Z} .$
Equivalence relation with infinitely many equivalence classes.
Although each equivalence class has infinitely many elements, there are only as many equivalence classes as possible remainders when dividing by 4.