# 7.3: Equivalence Relations

- Page ID
- 8423

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)A relation on a set \(A\) is an ** equivalence relation** if it is reflexive, symmetric, and transitive. We often use the tilde notation \(a\sim b\) to denote an equivalence relation.

Example \(\PageIndex{1}\label{eg:equivrel-01}\)

The relations in Examples 7.2.4, 7.2.5, and 7.2.7, are equivalence relations, so are those in Hands-On Exercises 7.2.2 and 7.2.6.

Example \(\PageIndex{2}\label{eg:relmod4}\)

Define a relation \(\sim\) on \(\mathbb{Z}\) by \[a\sim b \,\Leftrightarrow\, a\equiv b \mbox{ (mod~4)}. \nonumber\] Verify that \(\sim\) is an equivalence relation.

**Answer**-
We need to check three properties:

- It is obvious \(a\equiv a\) (mod 4), hence \(a\sim a\). The relation \(\sim\) is reflexive.
- If \(a\sim b\), then \(a\equiv b\) (mod 4). It is clear that we also have \(b\equiv a\) (mod 4). Hence, \(\sim\) is symmetric.
- If \(a\sim b\) and \(b\sim c\), then \[a\equiv b \pmod{4}, \qquad\mbox{and}\qquad b\equiv c \pmod{4}. \nonumber\] It follows that \(a\equiv c\) (mod 4). Thus \(a\sim c\). This shows that \(\sim\) is transitive.

Therefore, \(\sim\) is an equivalence relation.

exercise \(\PageIndex{1}\label{he:relmod6}\)

Define a relation \(\sim\) on \(\mathbb{Z}\) by \[a\sim b \,\Leftrightarrow\, a\equiv b \mbox{ (mod~6)}. \nonumber\] Verify that \(\sim\) is an equivalence relation.

exercise \(\PageIndex{2}\label{he:relmodn}\)

Let \(n\geq2\) be a positive integer. Define a relation \(\sim\) on \(\mathbb{Z}\) by \[a\sim b \,\Leftrightarrow\, a\equiv b \mbox{ (mod~$n$)}. \nonumber\] Verify that \(\sim\) is an equivalence relation.

Take a closer look at Example 7.3.2. All the integers having the same remainder when divided by 4 are related to each other. Define the sets \[\begin{array}{lclcr} {[0]} &=& \{n\in\mathbb{Z} \mid n\bmod 4 = 0 \} &=& 4\mathbb{Z}, \\ [3pt] {[1]} &=& \{n\in\mathbb{Z} \mid n\bmod 4 = 1 \} &=& 1+4\mathbb{Z}, \\ [3pt] {[2]} &=& \{n\in\mathbb{Z} \mid n\bmod 4 = 2 \} &=& 2+4\mathbb{Z}, \\ [3pt] {[3]} &=& \{n\in\mathbb{Z} \mid n\bmod 4 = 3 \} &=& 3+4\mathbb{Z}. \end{array} \nonumber\] It is clear that every integer belongs to exactly one of these four sets. Hence, \[\mathbb{Z} = [0] \cup [1] \cup [2] \cup [3]. \nonumber\] These four sets are pairwise disjoint, so \(\mathbb{Z}\) is a *disjoint union* of these four sets. We say that \(\{[0], [1], [2], [3]\}\) is a partition of \(\mathbb{Z}\).

Definition

A collection \(\{S_1,S_2,\ldots,S_n\}\) of nonempty subsets of \(S\) is said to be a ** partition** of \(S\) if the subsets \(S_1,S_2,\ldots,S_n\) are pairwise disjoint (\(S_i \cap S_j = \emptyset\) whenever \(i\neq j\)), and \[S_1\cup S_2\cup \cdots \cup S_n = S. \nonumber\] The subsets \(S_1,S_2,\ldots,S_n\) are called the

**or**

*parts***of the partition.**

*components*Because of transitivity and symmetry, all the elements related to a fixed element must be related to each other. Thus, if we know one element in the group, we essentially know all its “relatives.”

Definition: equivalence class

Let \(\sim\) be an equivalence relation on \(A\). The set \[[a] = \{ x\in A \mid x\sim a \}. \nonumber\] is called the ** equivalence class** of \(a\).

Example \(\PageIndex{3}\)

In Example 7.2.4, each equivalence class of the relation \(S\) consists of all the triangles that are similar. Note that no triangle can belong to two different equivalence classes. This means that the equivalence classes are pairwise disjoint.

In the same example, each equivalence class of the relation \(P\) consists of all the lines that are parallel. Again, take note that no line can belong to two different equivalence classes. Thus, the equivalence classes are pairwise disjoint.

Example \(\PageIndex{4}\label{eg:equivmod4}\)

For the relation \(\sim\) on \(\mathbb{Z}\) defined by \(a\sim b\,\Leftrightarrow\, a\equiv b\) (mod 4), there are four equivalence classes \([0],[1],[2]\) and \([3]\), and the set \(\{[0], [1], [2], [3]\}\) forms a partition of \(\mathbb{Z}\). Therefore, \[\mathbb{Z} = [0]\cup[1]\cup[2]\cup[3], \nonumber\] and the four components \([0]\), \([1]\), \([2]\) and \([3]\) are pairwise disjoint.

exercise \(\PageIndex{3}\label{he:equivmod6}\)

What are the equivalence classes of the relation \(\sim\) in Exercise 7.3.1?

exercise \(\PageIndex{4}\label{he:equivmodn}\)

What are the equivalence classes of the relation \(\sim\) in in Exercise 7.3.2?

exercise \(\PageIndex{5}\label{he:equivrel-01}\)

For each of the equivalence relations mentioned in Example 7.3.1, determine its equivalence classes.

All the elements in the same equivalence class are related to each other. Therefore, the elements in \([a]\) all share the same property that \(a\) enjoys, from the viewpoint of the relation \(\sim\). In Example 7.3.4, the equivalence class \([0]\) consists of elements that are multiples of 4. The equivalence class \([1]\) consists of elements that, when divided by 4, leave 1 as the remainder, and similarly for the equivalence classes \([2]\) and \([3]\). Because of the common bond between the elements in an equivalence class \([a]\), all these elements can be represented by *any* member within the equivalence class. This is the spirit behind the next theorem.

Theorem \(\PageIndex{1}\label{thm:equivclass}\)

If \(\sim\) is an equivalence relation on \(A\), then \(a\sim b \Leftrightarrow [a]=[b]\).

**Proof**-
We leave the proof as an exercise.

One may regard equivalence classes as objects with many aliases. Every element in an equivalence class can serve as its representative. So we have to take extra care when we deal with equivalence classes. Do not be fooled by the representatives, and consider two apparently different equivalence classes to be distinct when in reality they may be identical.

Example \(\PageIndex{5}\label{eg:sameLN}\)

Define \(\sim\) on a set of individuals in a community according to \[a\sim b \,\Leftrightarrow\, \mbox{$a$ and $b$ have the same last name}. \nonumber\] We have seen that \(\sim\) is an equivalence relation. Each equivalence class consists of all the individuals with the same last name in the community. Hence, for example, James Smith, Lucy Smith, and Peter Smith all belong to the same equivalence class. Any Smith can serve as its representative, so we can denote it as, for example, \([\)Peter Smith\(]\).

Example \(\PageIndex{6}\label{eg:samedec}\)

Define \(\sim\) on \(\mathbb{R}^+\) according to \[x\sim y \,\Leftrightarrow\, x-y\in\mathbb{Z}. \nonumber\] Hence, two real numbers are related if and only if they have the same decimal parts. It is easy to verify that \(\sim\) is an equivalence relation, and each equivalence class \([x]\) consists of all the positive real numbers having the same decimal parts as \(x\) has. Notice that \[\mathbb{R}^+ = \bigcup_{x\in(0,1]} [x], \nonumber\] which means that the equivalence classes \([x]\), where \(x\in(0,1]\), form a partition of \(\mathbb{R}\).

exercise \(\PageIndex{6}\label{he:samedec2}\)

Prove that the relation \(\sim\) in Example 7.3.6 is indeed an equivalence relation.

exercise \(\PageIndex{7}\label{he:samedec3}\)

Define \(\sim\) on \(\mathbb{R}\) according to \[x\sim y \,\Leftrightarrow\, x-y\in\mathbb{Z}. \nonumber\] Show that \(\sim\) is an equivalence class. True or false: \(-2.14\in[5,14]\)? Explain.

What makes equivalence relations so important is the following ** Fundamental Theorem on Equivalence Relations**.

Theorem \(\PageIndex{2}\label{thm:FTequiv}\): Fundamental Theorem on Equivalence Relation

Given any equivalence relation on a nonempty set \(A\), the set of equivalence classes forms a partition of \(A\). Conversely, any partition \(\{A_1,A_2,\ldots,A_n\}\) of a nonempty set \(A\) into a finite number of nonempty subsets induces an equivalence relation \(\sim\) on \(A\), where \(a\sim b\) if and only if \(a,b\in A_i\) for some \(i\) (thus \(a\) and \(b\) belong to the same component).

**Proof**-
It is clear that \(A\) is the union of the equivalence classes induced by \(\sim\), so it remains to show that these equivalence classes are pairwise disjoint. Assume \([a]\cap[b]\neq\emptyset\). Let \(x\in [a]\cap[b]\). Then \(x\in[a]\) and \(x\in[b]\). Having \(x\in[a]\) means \(x\sim a\), and \(x\in[b]\) implies that \(x\sim b\). Symmetry and transitivity imply that \(a\sim b\). Theorem 7.3.1 assures that \([a]=[b]\). Therefore, if \([a]\neq[b]\), then \([a]\cap[b] = \emptyset\). This proves that the equivalence classes form a partition of \(A\).

Let \(A = A_1\cup A_2\cup\cdots\cup A_n\) be a partition of \(A\), define the relation \(\sim\) on \(A\) according to \[x\sim y \,\Leftrightarrow\, x,y\in A_i \mbox{ for some $i$}. \nonumber\] It follows immediately from the definition that \(x\sim x\), so the relation is reflexive. It is also clear that \(x\sim y\) implies \(y\sim x\), hence, the relation is symmetric. Finally, if \(x\sim y\) and \(y\sim z\), then \(x,y\in A_i\) for some \(i\), and \(y,z\in A_j\) for some \(j\). Since the \(A_i\)s form a partition of \(A\), the element \(y\) cannot belong to two components. This means \(i=j\), hence, \(x,z\in A_i\). This proves that \(\sim\) is transitive. Consequently, \(\sim\) is an equivalence relation.

The idea behind the theorem is rather simple. Each equivalence class consists of all the “relatives” from the same family, so obviously the set \(A\) can be divided into families (equivalence classes). These families do not share any common elements (hence pairwise disjoint), because Theorem 7.3.1 states that any two equivalence classes sharing some common elements must be identical. Therefore, the families form a partition of \(A\). Conversely, given a partition \(\cal P\), we could define a relation that relates all members in the same component. This relation turns out to be an equivalence relation, with each component forming an equivalence class. This equivalence relation is referred to as the ** equivalence relation induced by \(\cal P\)**.

Example \(\PageIndex{7}\)

In Example 7.2.4, the relation \(S\) is an equivalence relation, and the equivalence classes are the sets of similar triangles, which form a partition of the set \({\cal T}\). This means any triangle belongs to one and only one equivalence class. In other words, we can classify the triangles on a plane according to their three interior angles.

The relation \(P\) in the same example is also an equivalence relation. Its equivalence classes are the sets of lines that are parallel. Every line on the plane belongs to exactly one equivalence class. Consequently, we can classify the lines on a plane by their slopes.

Example \(\PageIndex{8}\label{eg:equivrelat-06}\)

Over \(\mathbb{Z}^*\), define \[R_3 = \{ (m,n) \mid m,n\in\mathbb{Z}^* \mbox{ and } mn > 0\}. \nonumber\] It is not difficult to verify that \(R_3\) is an equivalence relation. There are only two equivalence classes: \([1]\) and \([-1]\), where \([1]\) contains all the positive integers, and \([-1]\) all the negative integers. It is obvious that \(\mathbb{Z}^*=[1]\cup[-1]\).

Example \(\PageIndex{9}\label{eg:equivrelat-07}\)

For each \(b\in\mathbb{R}\), define \(L_b\) to be the line in \(\mathbb{R}^2\) (which is also called the \(xy\)-plane) with equation \(y=2x+b\). Then \({\cal L} =\{L_b \mid b\in \mathbb{R}\}\) is a partition of \(\mathbb{R}^2\) because given any point on \(\mathbb{R}^2\), there is only one straight line with slope 2 that can pass through it. Such a partition induces an equivalence relation \(\sim\) defined by \[(p,q) \sim (s,t) \Leftrightarrow \mbox{both $(p,q)$ and $(s,t)$ lie on $L_b$ for some $b$}. \nonumber\] Thus, \((p,q)\sim(s,t)\) if and only if the two points \((p,q)\) and \((s,t)\) lie on the same straight line of slope 2. This means \(\frac{q-t}{p-s}=2\). Therefore, we can restate the definition as \[(p,q) \sim (s,t) \Leftrightarrow q-t=2(p-s). \nonumber\] For example, \((1,5)\sim (0,3)\). In fact, \([(1,5)]\) corresponds to the line \(y=2x+3\) or \(L_3\). Similarly, \([(1,1.25)]\) corresponds to the line \(y=2x-0.75\) or \(L_{-0.75}\). In general, \(L_b=[(0,b)]\).

exercise \(\PageIndex{8}\label{he:equivrelat-02}\)

Consider the partition of \(\mathbb{R}^2\) (the \(xy\)-plane) \[\mathbb{R}^2 = \bigcup_{b\in\mathbb{R}} L_b, \nonumber\] where \(L_b\) is the line satisfying the equation \(y=5x+b\). Determine the equivalence relation induced by this partition.

We have studied modular arithmetic extensively. In Exercise 7.3.2, you have already proved the following result.

Theorem \(\PageIndex{3}\)

For any positive integer \(n\geq2\), the relation congruence modulo \(n\) is an equivalence relation on \(\mathbb{Z}\)

We can now provide a more rigorous definition of \(\mathbb{Z}_n\).

Definition

Let \(n\geq2\) be an integer. The equivalence classes \([0], [1], \ldots, [n-1]\) of the relation congruence modulo \(n\) are called the ** residue classes modulo \(n\)**. The set \[\mathbb{Z}_n = \big\{ [0], [1], \ldots, [n-1] \big\} \nonumber\] is called the set of residue classes modulo \(n\).

**Remark**

We define two operations \(\oplus\) and \(\odot\) on the elements of \(\mathbb{Z}_n\) according to \[[a]\oplus[b] = [a+b], \qquad\mbox{and}\qquad [a]\odot[b] = [ab]. \nonumber\] We will not go into the details, but we would like to remark that \(\<\mathbb{Z}_n,\oplus,\odot\>\) forms an algebraic structure called ring. In practice, we seldom write \(\mathbb{Z}_n=\big\{[0],[1],\ldots,[n-1]\big\}\) because it is too cumbersome. Instead, we just write \(\mathbb{Z}_n = \{0,1,2,\ldots,n-1\}\). However, what we really work with in \(\mathbb{Z}_n\) are the residue classes represented by the integers 0 through \(n-1\).

The incidence matrix of an equivalence relation exhibits a beautiful pattern. Conversely, by examining the incidence matrix of a relation, we can tell whether the relation is an equivalence relation.

If we can rearrange the rows and columns of an incidence matrix so that the modified incidence matrix can be divided into blocks of submatrices containing entirely 1s or entirely 0s, such that the 1-submatrices lie on the diagonal, then the underlying relation \(R\) is an equivalence relation. Here is the reason. Since the entries in each 1-submatrix are all 1s, this means the corresponding elements are all related to each other. This is the notion of transitivity. Obviously, every element is related to itself. Since the 1-submatrices lie on the diagonal, the matrix, hence the relation, is symmetric. This proves that the underlying relation is an equivalence relation. Each equivalence class consists of all the elements that correspond to the row and columns in the same 1-matrix.

Example \(\PageIndex{10}\label{eg:equivrelat-08}\)

Let \(A=\{1,2,3,4,5\}\) and define the relation \(R_1\) on \(A\) by \[R_1 = \{ (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3), (4,4), (4,4), (5,4), (5,5) \}. \nonumber\] It is clear from the incidence matrix (we add lines to make the 0- and 1-submatrices more outstanding) \[\begin{array}{cc} & \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{array} & \left(\begin{array}{ccc|cc} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ \hline 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{array}\right) \end{array} \nonumber\] that \(R_1\) is an equivalence relation and that it has two equivalence classes: \([1]=[2]=[3]=\{1,2,3\}\), and \([4]=[5]=\{4,5\}\), such that \(A=[1]\cup[4]\).

Example \(\PageIndex{11}\label{eg:equivrelat-09}\)

Let \(A=\{a,b,c,d\}\). Define the relation \(R_2\) on \(A\) by \[R_2 = \{(a,a), (a,c), (b,b), (b,d), (c,a), (c,c), (d,b), (d,d)\}. \nonumber\] After rewriting the incidence matrix \[\begin{array}{cc} & \begin{array}{cccc} a & b & c & d \end{array} \\ \begin{array}{c} a \\ b \\ c \\ d \end{array} & \left( \begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array} \right) \end{array} \qquad\leadsto\qquad \begin{array}{cc} & \begin{array}{cccc} a & c & b & d \end{array} \\ \begin{array}{c} a \\ c \\ b \\ d \end{array} & \left( \begin{array}{cc|cc} 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{array} \right) \end{array} \nonumber\] it becomes clear that \(R_2\) is an equivalence relation, with \([a]=[c]=\{a,c\}\), and \([b]=[d]=\{b,d\}\), such that \(A=[a]\cup[b]\).

exercise \(\PageIndex{9}\label{he:equivrelat-03}\)

The relation \(S\) defined on the set \(\{1,2,3,4,5,6\}\) is known to be \[\displaylines{ S = \{ (1,1), (1,4), (2,2), (2,5), (2,6), (3,3), \hskip1in \cr (4,1), (4,4), (5,2), (5,5), (5,6), (6,2), (6,5), (6,6) \}. \cr} \nonumber\] Show that \(S\) is an equivalence relation by studying its incidence matrix, and rewriting it if necessary. Determine the contents of its equivalence classes.

Example \(\PageIndex{12}\label{eg:equivrelat-10}\)

Find the equivalence relation \(R\) induced by the partition \[{\cal P} = \big\{ \{1\}, \{3\}, \{2,4,5,6\} \big\} \nonumber\] of \(A=\{1,2,3,4,5,6\}\).

**Answer**-
From the two 1-element equivalence classes \(\{1\}\) and \(\{3\}\), we find two ordered pairs \((1,1)\) and \((3,3)\) that belong to \(R\). From the equivalence class \(\{2,4,5,6\}\), any pair of elements produce an ordered pair that belongs to \(R\). Therefore, \[\begin{aligned} R &=& \{ (1,1), (3,3), (2,2), (2,4), (2,5), (2,6), (4,2), (4,4), (4,5), (4,6), \\ & & \quad (5,2), (5,4), (5,5), (5,6), (6,2), (6,4), (6,5), (6,6) \}. \end{aligned} \nonumber\] Alternatively, we can construct the incidence matrix \[\begin{array}{cc} & \begin{array}{cccccc} 1 & 3 & 2 & 4 & 5 & 6 \end{array} \\ \begin{array}{c} 1 \\ 3 \\ 2 \\ 4 \\ 5 \\ 6 \end{array} & \left( \begin{array}{c|c|cccc} 1 & 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \end{array} \right) \end{array} \nonumber\] from which the ordered pairs in \(R\) can be easily obtained.

exercise \(\PageIndex{10}\label{he:equivrelat-04}\)

Find the equivalence relation \(R\) induced by the partition \[{\cal P} = \big\{ \{a,d\}, \{b,c,g\}, \{e,f\} \big\} \nonumber\] of \(A=\{a,b,c,d,e,f,g\}\) by listing all its ordered pairs (the roster method).

## Summary Review

- A relation \(R\) on a set \(A\) is an equivalence relation if it is reflexive, symmetric, and transitive.
- If \(R\) is an equivalence relation on the set \(A\), its equivalence classes form a partition of \(A\).
- In each equivalence class, all the elements are related and every element in \(A\) belongs to one and only one equivalence class.
- The relation \(R\) determines the membership in each equivalence class, and every element in the equivalence class can be used to represent that equivalence class.
- In a sense, if you know one member within an equivalence class, you also know all the other elements in the equivalence class because they are all related according to \(R\).
- Conversely, given a partition of \(A\), we can use it to define an equivalence relation by declaring two elements to be related if they belong to the same component in the partition.

Exercise \(\PageIndex{1}\label{ex:equivrelat-01}\)

Show that each of the following relations \(\sim\) on \(\mathbb{Z}\) is an equivalence relation, and find its equivalence classes.

- \(m\sim n \,\Leftrightarrow\, |m-3|=|n-3|\)
- \(m\sim n \,\Leftrightarrow\, m+n\) is even

Exercise \(\PageIndex{2}\label{ex:equivrel-02}\)

Show that each of the following relations \(\sim\) on \(\mathbb{Z}\) is an equivalence relation, and find its equivalence classes.

- \(m\sim n \,\Leftrightarrow\, 3\mid(m+2n)\)
- \(m\sim n \,\Leftrightarrow\, 5\mid(2m+3n)\)

Exercise \(\PageIndex{3}\label{ex:equivrel-03}\)

Let \(T\) be a fixed subset of a nonempty set \(S\). Define the relation \(\sim\) on \(\wp(S)\) by \[X\sim Y \,\Leftrightarrow\, X\cap T = Y\cap T, \nonumber\] Show that \(\sim\) is an equivalence relation. In particular, let \(S=\{1,2,3,4\}\) and \(T=\{1,3\}\).

- True or false: \(\{1,2,4\}\sim\{1,4,5\}\)?
- How about \(\{1,2,4\}\sim\{1,3,4\}\)?
- Find \([\{1,5\}]\)
- Describe \([X]\) for any \(X\in\wp(S)\).

Exercise \(\PageIndex{4}\label{ex:equivrel-04}\)

For each of the following relations \(\sim\) on \(\mathbb{R}\times\mathbb{R}\), determine whether it is an equivalence relation. For those that are, describe geometrically the equivalence class \([(a,b)]\).

- \((x_1,y_1)\sim(x_2,y_2) \,\Leftrightarrow\, y_1-x_1^2=y_2-x_2^2\).
- \((x_1,y_1)\sim(x_2,y_2) \,\Leftrightarrow\, (x_1-1)^2+y_1^2=(x_2-1)^2+y_2^2\)

Exercise \(\PageIndex{5}\label{ex:equivrel-05}\)

For each of the following relations \(\sim\) on \(\mathbb{R}\times\mathbb{R}\), determine whether it is an equivalence relation. For those that are, describe geometrically the equivalence class \([(a,b)]\).

- \((x_1,y_1)\sim(x_2,y_2) \,\Leftrightarrow\, x_1+y_2=x_2+y_1\)
- \((x_1,y_1)\sim(x_2,y_2) \,\Leftrightarrow\, (x_1-x_2)(y_1-y_2)=0\)

Exercise \(\PageIndex{6}\label{ex:equivrel-06}\)

For each of the following relations \(\sim\) on \(\mathbb{R}\times\mathbb{R}\), determine whether it is an equivalence relation. For those that are, describe geometrically the equivalence class \([(a,b)]\).

- \((x_1,y_1)\sim(x_2,y_2) \,\Leftrightarrow\, |x_1|+|y_1|=|x_2|+|y_2|\)
- \((x_1,y_1)\sim(x_2,y_2) \,\Leftrightarrow\, x_1y_1=x_2y_2\)

Exercise \(\PageIndex{7}\label{ex:equivrel-07}\)

Define the relation \(\sim\) on \(\mathbb{Q}\) by \[x\sim y \,\Leftrightarrow\, 2(x-y)\in\mathbb{Z}. \nonumber\] Show that \(\sim\) is an equivalence relation. Describe the equivalence classes \([0]\) and \(\big[\frac{1}{4}\big]\).

Exercise \(\PageIndex{8}\label{ex:equivrel-08}\)

Define the relation \(\sim\) on \(\mathbb{Q}\) by \[x\sim y \,\Leftrightarrow\, \frac{x-y}{2}\in\mathbb{Z}. \nonumber\] Show that \(\sim\) is an equivalence relation. Describe the equivalence classes \([0]\), \([1]\) and \(\big[\frac{1}{2}\big]\).

Exercise \(\PageIndex{9}\label{ex:equivrel-09}\)

Consider the following relation on \(\{a,b,c,d,e\}\): \[\displaylines{ R = \{(a,a),(a,c),(a,e),(b,b),(b,d),(c,a),(c,c),(c,e), \cr (d,b),(d,d),(e,a),(e,c),(e,e)\}. \hskip0.7in \cr} \nonumber\] Show that it is an equivalence relation, and describe its equivalence classes.

**Answer**-
Use the matrix representation of the relation.

Exercise \(\PageIndex{10}\label{ex:equivrel-10}\)

Each part below gives a partition of \(A=\{a,b,c,d,e,f,g\}\). Find the equivalence relation on \(A\) induced by the partition.

**Answer**-
- \(\mathcal{P}_1 = \big\{\{a,b\},\{c,d\},\{e,f\},\{g\}\big\}\)
- \(\mathcal{P}_2 = \big\{\{a,c,e,g\},\{b,d,f\}\big\}\)
- \(\mathcal{P}_3 = \big\{\{a,b,d,e,f\},\{c,g\}\big\}\)
- \(\mathcal{P}_4 = \big\{\{a,b,c,d,e,f,g\}\big\}\)

Exercise \(\PageIndex{11}\label{ex:equivrel-11}\)

Let \(\sim\) be an equivalence relation on \(A\). Prove that if \(a\sim b\), then \([a]=[b]\).

Exercise \(\PageIndex{12}\label{ex:equivrel-12}\)

Let \(\sim\) be an equivalence relation on \(A\). Prove that if \([a]=[b]\), then \(a\sim b\).