EF Classes, partitions, and quotients

equivalence class (of an element $a$ ): 🔗

🔗
the subset of $A$ consisting of all elements that are equivalent to the given element $a \in A,$ relative to a specific equivalence relation $\equiv$ on $A;$ i.e. the set

${x \in A | x \equiv a}$
$[a]$: 🔗
the equivalence class of the element $a \in A$ relative to some specific equivalence relation on $A$

🔗

Example 18.3.2. Equivalence classes of natural numbers modulo $5$ .

🔗

If we divide

8

5,

we get

1

with

3

remainder. So the equivalence class of

8

relative to

\equiv_{5}

consists of all natural numbers that have remainder

3

when divided by

5 :

[8] = {3, 8, 13, 18, \dots} .

🔗

Now,

3

is in this class because when we divide

3

5

we get

0

with

3

remainder. But if we had started with

3

instead of

8,

we would have also said that the equivalence class of

3

relative to

\equiv_{5}

consists of all natural numbers that have remainder

3

when divided by

5 :

[3] = {3, 8, 13, 18, \dots} .

🔗

Proposition 18.3.3. Properties of equivalence classes.

🔗

Suppose

\equiv

is an equivalence relation on a nonempty set

A .

🔗
For every $a \in A,$ we have $a \in [a] .$
🔗
For $a, a_{1}, a_{2} \in A$ with $a_{1}, a_{2} \in [a],$ we have $a_{1} \equiv a_{2} .$
🔗
For each pair $a_{1}, a_{2} \in A,$ we have $a_{1} \equiv a_{2}$ if and only if $[a_{1}] = [a_{2}] .$
🔗
For each pair $a_{1}, a_{2} \in A,$ we have $a_{1} ≢ a_{2}$ if and only if $[a_{1}] \cap [a_{2}] = \emptyset .$

🔗

Proof of Statement 4.

Let us prove the equivalent “double contrapositive” biconditional

a_{1} \equiv a_{2} \Leftrightarrow [a_{1}] \cap [a_{2}] \neq \emptyset .

(See Worked Example 2.1.4.)

(⇒)

Suppose

a_{1} \equiv a_{2} .

Then

[a_{1}] = [a_{2}]

by Statement 3, so

[a_{1}] \cap [a_{2}] = [a_{1}] \cap [a_{1}] = [a_{1}] .

But

[a_{1}]

is nonempty by Statement 1.

(⇐)

Suppose

[a_{1}] \cap [a_{2}] \neq \emptyset .

Then there exists some element

x \in A

that is in both

[a_{1}]

and

[a_{2}],

so that both

x \equiv a_{1}

and

x \equiv a_{2} .

By the symmetric property, we have

a_{1} \equiv x,

and combining this with

x \equiv a_{2}

in the transitive property gives

a_{1} \equiv a_{2} .

🔗

Statement 3 of Proposition 18.3.3 tells us that any member of an equivalence class may be used to define the class.

equivalence class representative: 🔗

🔗
an element $a \in A$ used to define the equivalence class

$[a] = {x \in A | x \equiv a}$
complete set of equivalence class representatives: 🔗
a subset $C \subseteq A$ so that for each $x \in A$ there exists exactly one $a \in C$ so that $x \in [a]$

🔗

Remember that elements that are equivalent to one another relative to some equivalence relation are viewed to be “essentially the same” from the point of view of the property used to define the equivalence relation. So different but equivalent elements become interchangeable (see Section 18.1). When we have a complete set of representatives for the equivalence classes, we are deciding to always interchange an element for the chosen representative of the class containing that element.

🔗

Example 18.3.4. A complete set of equivalence class representatives for natural numbers modulo $5$ .

🔗

Continuing Example 18.3.2, we could represent the class of numbers that have remainder

3

by the number

8 :

[8] = {3, 8, 13, 18, \dots} .

🔗

But it seems more “natural” to represent this class by the number

3 :

[3] = {3, 8, 13, 18, \dots} .

🔗

Notice that each of the numbers

0, 1, 2, 3, 4

has a different remainder when divided by

5,

so no two of them are equivalent. That also means that each is in a different class (Statement 4 of Proposition 18.3.3). But when we go past

4,

the remainders when divided by

5

start repeating: each of the numbers in the list

5, 6, 7, 8, 9

has the same remainder as the number in the corresponding position in the list

0, 1, 2, 3, 4 .

And then the remainders repeat again when we go past

9 .

And so on. So it seems “natural” to use

0, 1, 2, 3, 4

as a complete set of representatives of the equivalence classes for

N

modulo

5 :

\begin{aligned} [0] & = {0, 5, 10, 15, \dots}, \\ [1] & = {1, 6, 11, 16, \dots}, \\ [2] & = {2, 7, 12, 17, \dots}, \\ [3] & = {3, 8, 13, 18, \dots}, \\ [4] & = {4, 9, 14, 19, \dots} . \end{aligned}

🔗

The definition of complete set of equivalence class representatives implicitly assumes that the equivalence classes “fill up” the whole set

A .

But that is always precisely the case.

partition: 🔗
a collection of subsets of a set $A$ that are pairwise disjoint and whose union is $A$
partition cell: 🔗
one of the subsets that make up a partition of a set

A diagram illustrating a partition of a set. — 🔗
Figure 18.3.5. A diagram illustrating a partition of a set, so that $A = A_{1} ⊔ A_{2} ⊔ A_{3} ⊔ \dots ⊔ A_{n} .$

🔗

Remark 18.3.6.

🔗

In essence, partition is just a synonym for disjoint union. So a collection of subsets form a partition when each element of the set is in exactly one partition cell.

🔗

Note 18.3.7.

🔗

It is not necessary for a partition of a set to be made up of a finite (or even countable) number of cells; see the examples below.

🔗

Theorem 18.3.8. Equivalence classes form a partition.

🔗

\equiv

is an equivalence relation on a set

A,

then the equivalence classes with respect to

\equiv

are a partition of

A .

🔗

Proof idea.

This theorem claims that every element of

A

is in exactly one equivalence class. But this follows from the statements of Proposition 18.3.3.

🔗

Example 18.3.9. Equivalence classes modulo $n$ .

🔗

Generalizing Example 18.3.4, each of the numbers

0, 1, 2, 3, \dots, n - 1

is its own remainder when divided by

n .

And then the pattern of remainders repeats, starting over at remainder

0,

when we continue on to the numbers

n, n + 1, \dots .

0, 1, 2, 3, \dots, n - 1

is a complete set of equivalence class representatives, and the classes modulo

n

partition

N

into the disjoint subsets

\begin{aligned} [0] & = {0, n, 2 n, 3 n, \dots}, \\ [1] & = {1, n + 1, 2 n + 1, 3 n + 1, \dots}, \\ [2] & = {2, n + 2, 2 n + 2, 3 n + 2, \dots}, \\ ⋮ \\ [n - 1] & = {n - 1, 2 n - 1, 3 n - 1, 4 n - 1, \dots} . \end{aligned}

🔗

Example 18.3.10.

🔗

Let

L

be the set of all lines in the plane, and consider

ℓ_{1} \equiv ℓ_{2}

ℓ_{1}, ℓ_{2}

are parallel. Then

\equiv

partitions

L

into sets of parallel lines.

🔗

Example 18.3.11.

🔗

Recall that for alphabet

Σ,

Σ_{n}^{*}

is the subset of

Σ^{*}

consisting of all words whose length is exactly

n .

Then

Σ_{0}^{*}, Σ_{1}^{*}, Σ_{2}^{*}, \dots

🔗

is a partition of

Σ^{*} .

(See Exercise 9.9.9.)

🔗

Recall that a relation on

Σ^{*}

can be defined as a subset of

Σ^{*} \times Σ^{*} .

So consider the relation

R

Σ^{*}

defined by

R = (Σ_{0}^{*} \times Σ_{0}^{*}) ⊔ (Σ_{1}^{*} \times Σ_{1}^{*}) ⊔ (Σ_{2}^{*} \times Σ_{2}^{*}) ⊔ \dots

🔗

Then

R

is the equivalence relation on

Σ^{*}

where

w R y

| w | = | y |,

and its equivalence classes are precisely the sets

Σ_{n}^{*},

n \geq 0 .

🔗

Theorem 18.3.12. Partitions arise from equivalence relations.

🔗

Given a partition of a set

A,

there exists an equivalence relation

\equiv

A

whose equivalence classes are precisely the cells of the partition.

🔗

Proof idea.

Given a partition of

A,

for each

a \in A

there exists exactly one partition cell containing

a .

So define

a_{1} \equiv a_{2}

to mean “elements

a_{1}, a_{2}

are contained in the same partition cell of

A .

”

🔗

Remark 18.3.13.

🔗

Theorem 18.3.8 and Theorem 18.3.12 combine to provide, for each set

A,

a bijective correspondence

{equivalence relations on A} ⟷ {partitions of A} .

🔗

Worked Example 18.3.14. Determining an equivalence relation from a partition.

🔗

Determine an explicit equivalence relation

\equiv

Z

for which the equivalence classes give the following partition.

Z = \dots ⊔ {- 3, - 2, - 1} ⊔ {0, 1, 2} ⊔ {3, 4, 5} ⊔ \dots

Solution.

Notice that each cell in the partition contains a multiple of

3

along with the next two consecutive integers. So one way to explicitly define the corresponding equivalence relation is: for

a, b \in Z,

define

a \equiv b

to be true if there exists

n \in Z

such that

3 n \leq a, b \leq 3 n + 2 .

(Note: Details showing that this is an equivalence relation are omitted.)

🔗

quotient (of a set $A$ relative to an equivalence relation $\equiv$ ): 🔗
the subset of $P (A)$ whose elements are the equivalence classes of $\equiv$
$A / \equiv$: 🔗

🔗
the quotient of $A$ relative to equivalence relation $\equiv,$ so that

$(A / \equiv) = {[a] | a \in A}$

🔗

Example 18.3.15. A quotient described by class representatives.

🔗

Consider the partition of

Z

from Worked Example 18.3.14, and the corresponding equivalence relation

\equiv .

To describe

Z / \equiv,

we just need to pick a representative of each class. The most obvious way in this case is

(Z / \equiv) = {\dots, [- 3], [0], [3], [6], \dots} .

🔗

Worked Example 18.3.16. Determining a quotient.

🔗

Let

\equiv

represent the equivalence relation on

Z

defined by

🔗
$0 \equiv 0,$ and
🔗
for non-zero $m, n \in Z,$
$\begin{aligned} m & \equiv n & if & \frac{m}{| m |} & = \frac{n}{| n |} . \end{aligned}$

🔗

Determine the corresponding partition and quotient of

Z .

Solution.

First notice that

0

will be in an equivalence class all by itself. Next, consider the values that

m / | m |

can possibly take.

If $m > 0,$ then $| m | = m$ so $m / | m | = 1 .$
If $m < 0,$ then $| m | = - m$ so $m / | m | = - 1 .$

So this equivalence relation is just a fancy way of saying that

m, n

have the same sign. Therefore, all positive numbers will be in the same equivalence class, and all negative numbers will be in the same equivalence class. It now makes sense that

0

is in a class by itself, since

0

is neither positive nor negative. The partition of

Z

corresponding to

\equiv

is then

Z = {\dots, - 3, - 2, - 1} ⊔ {0} ⊔ {1, 2, 3, \dots} .

To describe

Z / \equiv,

we just need to pick a representative of each equivalence class. One possibility is

Z = [- 1] ⊔ [0] ⊔ [1],

so that

(Z / \equiv) = {[- 1], [0], [1]} .

🔗

natural projection (on a set $A$ relative to an equivalence relation $\equiv$ ): 🔗
the function $A \to (A / \equiv)$ defined by $a \mapsto [a]$

🔗

Note 18.3.17.

🔗

The natural projection

A \to (A / \equiv)

is always surjective, but it is almost never injective.

🔗

Example 18.3.18. Natural projection modulo- $5$ .

🔗

Recall that

\equiv_{5}

represents the modulo-

5

equivalence relation on

N .

In Example 18.3.4 we determined that there are five equivalence classes, represented by elements

0, 1, 2, 3, 4,

so that

(N / \equiv_{5}) = {[0], [1], [2], [3], [4]} .

🔗

Below are some examples of images of elements under the natural projection.

\begin{aligned} 2 & \mapsto [2] & 7 & \mapsto [2] & 104 & \mapsto [4] & 76 & \mapsto [1] & 2045 & \mapsto [0] . \end{aligned}

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 18.3 Classes, partitions, and quotients

Example 18.3.1.

Example 18.3.2. Equivalence classes of natural numbers modulo $5$ .

Proposition 18.3.3. Properties of equivalence classes.

Proof of Statement 1.

Proof of Statement 2.

Proof of Statement 3.

(⇒)

(⇐)

Proof of Statement 4.

(⇒)

(⇐)

Example 18.3.4. A complete set of equivalence class representatives for natural numbers modulo $5$ .

Remark 18.3.6.

Note 18.3.7.

Theorem 18.3.8. Equivalence classes form a partition.

Proof idea.

Example 18.3.9. Equivalence classes modulo $n$ .

Example 18.3.10.

Example 18.3.11.

Theorem 18.3.12. Partitions arise from equivalence relations.

Proof idea.

Remark 18.3.13.

Worked Example 18.3.14. Determining an equivalence relation from a partition.

Example 18.3.15. A quotient described by class representatives.

Worked Example 18.3.16. Determining a quotient.

Note 18.3.17.

Example 18.3.18. Natural projection modulo- $5$ .

Section 18.3 Classes, partitions, and quotients

Example 18.3.1.

Example 18.3.2. Equivalence classes of natural numbers modulo 5.

Proposition 18.3.3. Properties of equivalence classes.

Proof of Statement 1.

Proof of Statement 2.

Proof of Statement 3.

(⇒)

(⇐)

Proof of Statement 4.

(⇒)

(⇐)

Example 18.3.4. A complete set of equivalence class representatives for natural numbers modulo 5.

Remark 18.3.6.

Note 18.3.7.

Theorem 18.3.8. Equivalence classes form a partition.

Proof idea.

Example 18.3.9. Equivalence classes modulo n.

Example 18.3.10.

Example 18.3.11.

Theorem 18.3.12. Partitions arise from equivalence relations.

Proof idea.

Remark 18.3.13.

Worked Example 18.3.14. Determining an equivalence relation from a partition.

Example 18.3.15. A quotient described by class representatives.

Worked Example 18.3.16. Determining a quotient.

Note 18.3.17.

Example 18.3.18. Natural projection modulo-5.

Example 18.3.2. Equivalence classes of natural numbers modulo $5$ .

Example 18.3.4. A complete set of equivalence class representatives for natural numbers modulo $5$ .

Example 18.3.9. Equivalence classes modulo $n$ .

Example 18.3.18. Natural projection modulo- $5$ .