Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Section 18.3 Classes, partitions, and quotients

As desired (see Section 18.1), an equivalence relation can be used to group equivalent objects together.

Example 18.3.1.

Consider \(\mathord{\equiv_5}\) on \(\N\text{.}\) Notice that the elements in each of the following sets are all equivalent to each other with respect to \(\mathord{\equiv_5}\text{.}\)
\begin{gather*} \{ 0, 5, 10, 15, \dotsc \} \\ \{ 1, 6, 11, 16, \dotsc \} \\ \{ 2, 7, 12, 17, \dotsc \} \\ \{ 3, 8, 13, 18, \dotsc \} \\ \{ 4, 9, 14, 19, \dotsc \} \end{gather*}
Also notice that \(\N\) is the disjoint union of the above sets.
In fact, we could do the same for every divisor \(n\text{,}\) not just for \(n = 5\text{,}\) as \(\N\) is also the disjoint union of the sets
\begin{gather*} \{ \, 0, \, n, \, 2n, \, 3n, \, \dotsc \, \}, \\ \{ \, 1, \, n+1, \, 2n+1, \, 3n+1, \, \dotsc \, \}, \\ \{ \, 2, \, n+2,\, 2n+2,\, 3n+2, \, \dotsc \, \}, \\ \vdots \\ \{ \, n-1, \, n + (n-1), \, 2n + (n-1), \, 3n + (n-1), \, \dotsc \, \}, \end{gather*}
and again elements in each of the above sets are all equivalent to each other with respect to \(\mathord{\equiv_n}\text{.}\)
equivalence class (of an element \(a\))
the subset of \(A\) consisting of all elements that are equivalent to the given element \(a \in A\text{,}\) relative to a specific equivalence relation \(\mathord{\equiv}\) on \(A\text{;}\) i.e. the set
\begin{equation*} \setdef{x\in A}{ x \equiv a } \end{equation*}
\(\eqclass{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\) by \(5\text{,}\) we get \(1\) with \(3\) remainder. So the equivalence class of \(8\) relative to \(\mathord{\equiv_5}\) consists of all natural numbers that have remainder \(3\) when divided by \(5\text{:}\)
\begin{equation*} \eqclass{8} = \{ 3, 8, 13, 18, \dotsc \} \text{.} \end{equation*}
Now, \(3\) is in this class because when we divide \(3\) by \(5\) we get \(0\) with \(3\) remainder. But if we had started with \(3\) instead of \(8\text{,}\) we would have also said that the equivalence class of \(3\) relative to \(\mathord{\equiv_5}\) consists of all natural numbers that have remainder \(3\) when divided by \(5\text{:}\)
\begin{equation*} \eqclass{3} = \{ 3, 8, 13, 18, \dotsc \} \text{.} \end{equation*}
This is just the reflexive property, \(a \equiv a\text{.}\)
If \(a_1,a_2 \in \eqclass{a}\text{,}\) then by definition we have both \(a_1 \equiv a\) and \(a_2 \equiv a\text{.}\) Applying symmetry to the latter equivalence, we may write \(a_1 \equiv a \equiv a_2\text{,}\) to which we may apply transitivity to obtain \(a_1 \equiv a_2\text{,}\) as desired.

(⇒) 

Suppose \(a_1 \equiv a_2\text{.}\) To verify \(\eqclass{a_1} = \eqclass{a_2}\text{,}\) we follow the Test for Set Equality. First, assume \(x\) is an arbitrary element in \(\eqclass{a_1}\text{.}\) Then \(x \equiv a_1 \equiv a_2\text{,}\) so \(x \equiv a_2\) by the transitive property. Therefore, \(x \in \eqclass{a_2}\text{,}\) as required. This shows that \(\eqclass{a_1} \subseteq \eqclass{a_2}\text{;}\) the argument to show \(\eqclass{a_2} \subseteq \eqclass{a_1}\) is almost exactly the same, just using the symmetric property to first obtain \(a_2 \equiv a_1\text{.}\)

(⇐) 

By Statement 1 of this proposition, we have \(a_1 \in \eqclass{a_1}\text{.}\) If we assume \(\eqclass{a_1} = \eqclass{a_2}\text{,}\) then we also have \(a_1 \in \eqclass{a_2}\text{,}\) which means that \(a_1 \equiv a_2\text{,}\) as required.
Let us prove the equivalent “double contrapositive” biconditional \(a_1 \equiv a_2 \lgcequiv \eqclass{a_1} \intersection \eqclass{a_2} \ne \emptyset\text{.}\) (See Worked Example 2.1.4.)

(⇒) 

Suppose \(a_1 \equiv a_2\text{.}\) Then \(\eqclass{a_1} = \eqclass{a_2}\) by Statement 3, so
\begin{equation*} \eqclass{a_1} \intersection \eqclass{a_2} = \eqclass{a_1} \intersection \eqclass{a_1} = \eqclass{a_1} \text{.} \end{equation*}
But \(\eqclass{a_1}\) is nonempty by Statement 1.

(⇐) 

Suppose \(\eqclass{a_1} \intersection \eqclass{a_2} \ne \emptyset\text{.}\) Then there exists some element \(x \in A\) that is in both \(\eqclass{a_1}\) and \(\eqclass{a_2}\text{,}\) so that both \(x \equiv a_1\) and \(x \equiv a_2\text{.}\) By the symmetric property, we have \(a_1 \equiv x\text{,}\) and combining this with \(x \equiv a_2\) in the transitive property gives \(a_1 \equiv a_2\text{.}\)
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
\begin{equation*} \eqclass{a} = \setdef{x\in A}{ x \equiv a } \end{equation*}
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 \eqclass{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\text{:}\)
\begin{equation*} \eqclass{8} = \{ 3, 8, 13, 18, \dotsc \} \text{.} \end{equation*}
But it seems more “natural” to represent this class by the number \(3\text{:}\)
\begin{equation*} \eqclass{3} = \{ 3, 8, 13, 18, \dotsc \} \text{.} \end{equation*}
Notice that each of the numbers \(0,1,2,3,4\) has a different remainder when divided by \(5\text{,}\) 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\text{,}\) 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\text{.}\) And then the remainders repeat again when we go past \(9\text{.}\) 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\text{:}\)
\begin{align*} \eqclass{0} \amp = \{ 0, 5, 10, 15, \dotsc \}, \\ \eqclass{1} \amp = \{ 1, 6, 11, 16, \dotsc \}, \\ \eqclass{2} \amp = \{ 2, 7, 12, 17, \dotsc \}, \\ \eqclass{3} \amp = \{ 3, 8, 13, 18, \dotsc \}, \\ \eqclass{4} \amp = \{ 4, 9, 14, 19, \dotsc \}. \end{align*}
The definition of complete set of equivalence class representatives implicitly assumes that the equivalence classes “fill up” the whole set \(A\text{.}\) 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 \sqcup A_2 \sqcup A_3 \sqcup \dotsb \sqcup A_n\text{.}\)

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.
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\text{.}\) And then the pattern of remainders repeats, starting over at remainder \(0\text{,}\) when we continue on to the numbers \(n,n+1,\dotsc\text{.}\) So \(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{align*} \eqclass{0} \amp = \{ \, 0, \, n, 2n, \, 3n, \, \dotsc \, \}, \\ \eqclass{1} \amp = \{ \, 1, \, n+1, 2n+1, \, 3n+1, \, \dotsc \, \}, \\ \eqclass{2} \amp = \{ \, 2, \, n+2, 2n+2, \, 3n+2, \, \dotsc \, \}, \\ \phantom{\eqclass{0}} \amp \vdots \\ \eqclass{n-1} \amp = \{ \, n-1, \, 2n-1, 3n-1, \, 4n-1, \, \dotsc \, \}. \end{align*}

Example 18.3.10.

Let \(\mathscr{L}\) be the set of all lines in the plane, and consider \(\ell_1 \equiv \ell_2\) if \(\ell_1, \ell_2\) are parallel. Then \(\mathord{\equiv}\) partitions \(\mathscr{L}\) into sets of parallel lines.

Example 18.3.11.

Recall that for alphabet \(\Sigma\text{,}\) \(\words{\Sigma}_n\) is the subset of \(\words{\Sigma}\) consisting of all words whose length is exactly \(n\text{.}\) Then
\begin{equation*} \words{\Sigma}_0, \words{\Sigma}_1, \words{\Sigma}_2, \dotsc \end{equation*}
is a partition of \(\words{\Sigma}\text{.}\) (See Exercise 9.9.9.)
Recall that a relation on \(\words{\Sigma}\) can be defined as a subset of \(\words{\Sigma} \cartprod \words{\Sigma}\text{.}\) So consider the relation \(R\) on \(\words{\Sigma}\) defined by
\begin{equation*} R \;\; =\;\; (\words{\Sigma}_0 \cartprod \words{\Sigma}_0) \;\; \sqcup \;\; (\words{\Sigma}_1 \cartprod \words{\Sigma}_1) \;\; \sqcup \;\; (\words{\Sigma}_2 \cartprod \words{\Sigma}_2) \;\; \sqcup \;\; \dotsb \end{equation*}
Then \(R\) is the equivalence relation on \(\words{\Sigma}\) where \(w \mathrel{R} y\) if \(\length{w} = \length{y}\text{,}\) and its equivalence classes are precisely the sets \(\words{\Sigma}_n\text{,}\) \(n\ge 0\text{.}\)
Given a partition of \(A\text{,}\) for each \(a \in A\) there exists exactly one partition cell containing \(a\text{.}\) So define \(a_1 \equiv a_2\) to mean “elements \(a_1,a_2\) are contained in the same partition cell of \(A\text{.}\)”

Remark 18.3.13.

Theorem 18.3.8 and Theorem 18.3.12 combine to provide, for each set \(A\text{,}\) a bijective correspondence
\begin{equation*} \{ \text{equivalence relations on } A \} \;\; \longleftrightarrow \;\; \{ \text{partitions of } A \}. \end{equation*}

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

Determine an explicit equivalence relation \(\mathord{\equiv}\) on \(\Z\) for which the equivalence classes give the following partition.
\begin{equation*} \Z \;\; = \;\; \dotsb \;\; \sqcup \;\; \{ -3, -2, -1 \} \;\; \sqcup \;\; \{ 0, 1, 2 \} \;\; \sqcup \;\; \{ 3, 4, 5 \} \;\; \sqcup \;\; \dotsb \end{equation*}
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\text{,}\) define \(a \equiv b\) to be true if there exists \(n \in \Z\) such that \(3 n \le a,b \le 3 n + 2\text{.}\) (Note: Details showing that this is an equivalence relation are omitted.)
quotient (of a set \(A\) relative to an equivalence relation \(\mathord{\equiv}\))
the subset of \(\powset{A}\) whose elements are the equivalence classes of \(\mathord{\equiv}\)
\(A / \mathord{\equiv} \)
the quotient of \(A\) relative to equivalence relation \(\mathord{\equiv}\text{,}\) so that
\begin{equation*} (A / \mathord{\equiv}) = \setdef{\eqclass{a}}{a \in A} \end{equation*}

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 \(\mathrel{\equiv}\text{.}\) To describe \(\Z / \equiv\text{,}\) we just need to pick a representative of each class. The most obvious way in this case is
\begin{equation*} (\Z / \mathord{\equiv}) = \{ \dotsc, \eqclass{-3}, \eqclass{0}, \eqclass{3}, \eqclass{6}, \dotsc \} \text{.} \end{equation*}

Worked Example 18.3.16. Determining a quotient.

Let \(\mathord{\equiv}\) represent the equivalence relation on \(\Z\) defined by
  1. \(0 \equiv 0\text{,}\) and
  2. for non-zero \(m,n \in \Z\text{,}\)
    \begin{align*} m \amp \equiv n \amp \amp \text{if} \amp \frac{m}{\abs{m}} \amp = \frac{n}{\abs{n}} \text{.} \end{align*}
Determine the corresponding partition and quotient of \(\Z\text{.}\)
Solution.
First notice that \(0\) will be in an equivalence class all by itself. Next, consider the values that \(m/\abs{m}\) can possibly take.
  • If \(m \gt 0\text{,}\) then \(\abs{m} = m\) so \(m/\abs{m} = 1\text{.}\)
  • If \(m \lt 0\text{,}\) then \(\abs{m} = - m\) so \(m/\abs{m} = -1\text{.}\)
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 \(\mathord{\equiv}\) is then
\begin{equation*} \Z \;\; = \;\; \{ \dotsc, -3, -2, -1 \} \;\; \sqcup \;\; \{ 0 \} \;\; \sqcup \;\; \{ 1, 2, 3, \dotsc \}\text{.} \end{equation*}
To describe \(\Z / \mathord{\equiv}\text{,}\) we just need to pick a representative of each equivalence class. One possibility is
\begin{equation*} \Z = \eqclass{-1} \sqcup \eqclass{0} \sqcup \eqclass{1} \text{,} \end{equation*}
so that
\begin{equation*} (\Z / \mathord{\equiv}) = \{ \eqclass{-1}, \eqclass{0}, \eqclass{1} \} \text{.} \end{equation*}
natural projection (on a set \(A\) relative to an equivalence relation \(\mathord{\equiv}\))
the function \(A \to (A / \mathord{\equiv})\) defined by \(a \mapsto \eqclass{a}\)

Note 18.3.17.

The natural projection \(A \to (A / \mathord{\equiv})\) is always surjective, but it is almost never injective.

Example 18.3.18. Natural projection modulo-\(5\).

Recall that \(\mathord{\equiv}_5\) represents the modulo-\(5\) equivalence relation on \(\N\text{.}\) In Example 18.3.4 we determined that there are five equivalence classes, represented by elements \(0,1,2,3,4\text{,}\) so that
\begin{equation*} (\N / \mathord{\equiv}_5) = \{\eqclass{0},\eqclass{1},\eqclass{2},\eqclass{3},\eqclass{4}\} \text{.} \end{equation*}
Below are some examples of images of elements under the natural projection.
\begin{align*} 2 \amp \mapsto \eqclass{2} \amp 7 \amp \mapsto \eqclass{2} \amp 104 \amp \mapsto \eqclass{4} \amp 76 \amp \mapsto \eqclass{1} \amp 2045 \amp \mapsto \eqclass{0}\text{.} \end{align*}
<Prev^TopNext>