Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{\nmid} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\transpose}{\text{t}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \setcounter{chapter}{-1}\)

Subsection5.3Equivalence Relations and Partitions

A fundamental notion in mathematics is that of equality. We can generalize equality with equivalence relations and equivalence classes. An equivalence relation on a set \(X\) is a relation \(R \subset X \times X\) such that

  • \((x, x) \in R\) for all \(x \in X\) (reflexive property);

  • \((x, y) \in R\) implies \((y, x) \in R\) (symmetric property);

  • \((x, y)\) and \((y, z) \in R\) imply \((x, z) \in R\) (transitive property).

Given an equivalence relation \(R\) on a set \(X\text{,}\) we usually write \(x \sim y\) instead of \((x, y) \in R\text{.}\) If the equivalence relation already has an associated notation such as \(=\text{,}\) \(\equiv\text{,}\) or \(\cong\text{,}\) we will use that notation.

Example5.21

Let \(p\text{,}\) \(q\text{,}\) \(r\text{,}\) and \(s\) be integers, where \(q\) and \(s\) are nonzero. Define \(p/q \sim r/s\) if \(ps = qr\text{.}\) Clearly \(\sim\) is reflexive and symmetric. To show that it is also transitive, suppose that \(p/q \sim r/s\) and \(r/s \sim t/u\text{,}\) with \(q\text{,}\) \(s\text{,}\) and \(u\) all nonzero. Then \(ps = qr\) and \(ru = st\text{.}\) Therefore,

\begin{equation*} psu = qru = qst. \end{equation*}

Since \(s \neq 0\text{,}\) \(pu = qt\text{.}\) Consequently, \(p/q \sim t/u\text{.}\)

Example5.22

Suppose that \(f\) and \(g\) are differentiable functions on \({\mathbb R}\text{.}\) We can define an equivalence relation on such functions by letting \(f(x) \sim g(x)\) if \(f'(x) = g'(x)\text{.}\) It is clear that \(\sim\) is both reflexive and symmetric. To demonstrate transitivity, suppose that \(f(x) \sim g(x)\) and \(g(x) \sim h(x)\text{.}\) From calculus we know that \(f(x) - g(x) = c_1\) and \(g(x)- h(x) = c_2\text{,}\) where \(c_1\) and \(c_2\) are both constants. Hence,

\begin{equation*} f(x) - h(x) = ( f(x) - g(x)) + ( g(x)- h(x)) = c_1 - c_2 \end{equation*}

and \(f'(x) - h'(x) = 0\text{.}\) Therefore, \(f(x) \sim h(x)\text{.}\)

Example5.23

For \((x_1, y_1 )\) and \((x_2, y_2)\) in \({\mathbb R}^2\text{,}\) define \((x_1, y_1 ) \sim (x_2, y_2)\) if \(x_1^2 + y_1^2 = x_2^2 + y_2^2\text{.}\) Then \(\sim\) is an equivalence relation on \({\mathbb R}^2\text{.}\)

Example5.24

Let \(A\) and \(B\) be \(2 \times 2\) matrices with entries in the real numbers. We can define an equivalence relation on the set of \(2 \times 2\) matrices, by saying \(A \sim B\) if there exists an invertible matrix \(P\) such that \(PAP^{-1} = B\text{.}\) For example, if

\begin{equation*} A = \begin{pmatrix} 1 & 2 \\ -1 & 1 \end{pmatrix} \quad \text{and} \quad B = \begin{pmatrix} -18 & 33 \\ -11 & 20 \end{pmatrix}, \end{equation*}

then \(A \sim B\) since \(PAP^{-1} = B\) for

\begin{equation*} P = \begin{pmatrix} 2 & 5 \\ 1 & 3 \end{pmatrix}. \end{equation*}

Let \(I\) be the \(2 \times 2\) identity matrix; that is,

\begin{equation*} I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}. \end{equation*}

Then \(IAI^{-1} = IAI = A\text{;}\) therefore, the relation is reflexive. To show symmetry, suppose that \(A \sim B\text{.}\) Then there exists an invertible matrix \(P\) such that \(PAP^{-1} = B\text{.}\) So

\begin{equation*} A = P^{-1} B P = P^{-1} B (P^{-1})^{-1}. \end{equation*}

Finally, suppose that \(A \sim B\) and \(B \sim C\text{.}\) Then there exist invertible matrices \(P\) and \(Q\) such that \(PAP^{-1} = B\) and \(QBQ^{-1} = C\text{.}\) Since

\begin{equation*} C = QBQ^{-1} = QPAP^{-1} Q^{-1} = (QP)A(QP)^{-1}, \end{equation*}

the relation is transitive. Two matrices that are equivalent in this manner are said to be similar.

A partition \({\mathcal P}\) of a set \(X\) is a collection of nonempty sets \(X_1, X_2, \ldots\) such that \(X_i \cap X_j = \emptyset\) for \(i \neq j\) and \(\bigcup_k X_k = X\text{.}\) Let \(\sim\) be an equivalence relation on a set \(X\) and let \(x \in X\text{.}\) Then \([x] = \{ y \in X : y \sim x \}\) is called the equivalence class of \(x\text{.}\) We will see that an equivalence relation gives rise to a partition via equivalence classes. Also, whenever a partition of a set exists, there is some natural underlying equivalence relation, as the following theorem demonstrates.

Proof

Suppose there exists an equivalence relation \(\sim\) on the set \(X\text{.}\) For any \(x \in X\text{,}\) the reflexive property shows that \(x \in [x]\) and so \([x]\) is nonempty. Clearly \(X = \bigcup_{x \in X} [x]\text{.}\) Now let \(x, y \in X\text{.}\) We need to show that either \([x] = [y]\) or \([x] \cap [y] = \emptyset\text{.}\) Suppose that the intersection of \([x]\) and \([y]\) is not empty and that \(z \in [x] \cap [y]\text{.}\) Then \(z \sim x\) and \(z \sim y\text{.}\) By symmetry and transitivity \(x \sim y\text{;}\) hence, \([x] \subset [y]\text{.}\) Similarly, \([y] \subset [x]\) and so \([x] = [y]\text{.}\) Therefore, any two equivalence classes are either disjoint or exactly the same.

Conversely, suppose that \({\mathcal P} = \{X_i\}\) is a partition of a set \(X\text{.}\) Let two elements be equivalent if they are in the same partition. Clearly, the relation is reflexive. If \(x\) is in the same partition as \(y\text{,}\) then \(y\) is in the same partition as \(x\text{,}\) so \(x \sim y\) implies \(y \sim x\text{.}\) Finally, if \(x\) is in the same partition as \(y\) and \(y\) is in the same partition as \(z\text{,}\) then \(x\) must be in the same partition as \(z\text{,}\) and transitivity holds.

Let us examine some of the partitions given by the equivalence classes in the last set of examples.

Example5.27

In the equivalence relation in Example 5.21, two pairs of integers, \((p,q)\) and \((r,s)\text{,}\) are in the same equivalence class when they reduce to the same fraction in its lowest terms.

Example5.28

In the equivalence relation in Example 5.22, two functions \(f(x)\) and \(g(x)\) are in the same partition when they differ by a constant.

Example5.29

We defined an equivalence class on \({\mathbb R}^2\) by \((x_1, y_1 ) \sim (x_2, y_2)\) if \(x_1^2 + y_1^2 = x_2^2 + y_2^2\text{.}\) Two pairs of real numbers are in the same partition when they lie on the same circle about the origin.

Example5.30

Let \(r\) and \(s\) be two integers and suppose that \(n \in {\mathbb N}\text{.}\) We say that \(r\) is congruent to \(s\) modulo \(n\text{,}\) or \(r\) is congruent to \(s\) mod \(n\text{,}\) if \(r - s\) is evenly divisible by \(n\text{;}\) that is, \(r - s = nk\) for some \(k \in {\mathbb Z}\text{.}\) In this case we write \(r \equiv s \pmod{n}\text{.}\) For example, \(41 \equiv 17 \pmod{ 8}\) since \(41 - 17=24\) is divisible by \(8\text{.}\) We claim that congruence modulo \(n\) forms an equivalence relation of \({\mathbb Z}\text{.}\) Certainly any integer \(r\) is equivalent to itself since \(r - r = 0\) is divisible by \(n\text{.}\) We will now show that the relation is symmetric. If \(r \equiv s \pmod{ n}\text{,}\) then \(r - s = -(s -r)\) is divisible by \(n\text{.}\) So \(s - r\) is divisible by \(n\) and \(s \equiv r \pmod{ n}\text{.}\) Now suppose that \(r \equiv s \pmod{ n}\) and \(s \equiv t \pmod{ n}\text{.}\) Then there exist integers \(k\) and \(l\) such that \(r -s = kn\) and \(s - t = ln\text{.}\) To show transitivity, it is necessary to prove that \(r - t\) is divisible by \(n\text{.}\) However,

\begin{equation*} r - t = r - s + s - t = kn + ln = (k + l)n, \end{equation*}

and so \(r - t\) is divisible by \(n\text{.}\)

If we consider the equivalence relation established by the integers modulo \(3\text{,}\) then

\begin{align*} {[0]} & = \{ \ldots, -3, 0, 3, 6, \ldots \},\\ {[1]} & = \{ \ldots, -2, 1, 4, 7, \ldots \},\\ {[2]} & = \{ \ldots, -1, 2, 5, 8, \ldots \}. \end{align*}

Notice that \([0] \cup [1] \cup [2] = {\mathbb Z}\) and also that the sets are disjoint. The sets \([0]\text{,}\) \([1]\text{,}\) and \([2]\) form a partition of the integers.

The integers modulo \(n\) are a very important example in the study of abstract algebra and will become quite useful in our investigation of various algebraic structures such as groups and rings. In our discussion of the integers modulo \(n\) we have actually assumed a result known as the division algorithm, which will be stated and proved in Section 7.