Skip to main content
Logo image

Introduction to Groups and Geometries

David W. Lyons

Section 1.4 Equivalence relations

Subsection 1.4.1 Definitions

A relation on a set \(X\) is a subset of \(X\times X\text{.}\) Given a relation \(R\subseteq X\times X\text{,}\) we write \(x\sim_R y\text{,}\) or just \(x\sim y\) if \(R\) is understood by context, to denote that \((x,y)\in R\text{.}\) A relation is reflexive if \(x\sim x\) for every \(x\) in \(X\text{.}\) A relation is symmetric if \(x\sim y\) implies \(y\sim x\text{.}\) A relation is transitive if \(x\sim y\) and \(y\sim z \) together imply that \(x\sim z\text{.}\) A relation is called an equivalence relation if it is reflexive, symmetric, and transitive. Given an equivalence relation on \(X\) and an element \(x\in X\text{,}\) we write \([x]\) to denote the set
\begin{equation} [x] = \{y\in X\colon x\sim y\},\tag{1.4.1} \end{equation}
called the equivalence class of the element \(x\text{.}\) The set of equivalence classes is denoted \(X/\!\!\sim\text{,}\) that is,
\begin{equation} X/\!\!\sim \; = \{[x]\colon x\in X\}.\tag{1.4.2} \end{equation}
A partition of a set \(X\) is a collection of nonempty disjoint sets whose union is \(X\text{.}\)

Subsection 1.4.2 Important example: the integers modulo an integer \(n\)

Let \(n\) be a positive integer. Let \(\sim_n\) be the relation on the integers \(\Z\) given by
\begin{equation*} x\sim_n y \Leftrightarrow n|(x-y) \end{equation*}
(recall that the symbols "\(a|b\)" for integers \(a,b\text{,}\) pronounced "\(a\) divides \(b\)", means \(b=ka\) for some integer \(k\)). It is easy to show that \(\sim_n\) is an equivalence relation, and that the equivalence classes are precisely the set
\begin{equation*} \Z/\!\!\sim_n = \{[0],[1],[2],\ldots,[n-1]\}. \end{equation*}
This set of equivalence classes is fundamental and pervasive in mathematics. Instead of writing \(Z/\!\!\sim_n\text{,}\) the universally used notation is \(\Z_n\text{.}\) Instead of writing \(x\sim_n y\text{,}\) the universally used notation is \(x=y\pmod{n}\) (or sometimes \(x\equiv y\pmod{n}\)).
  1. Verify that the relation \(\sim_n\) is indeed an equivalence relation.
  2. Verify that the equivalence classes of the equivalence relation \(\sim_n\) are indeed \(\{[0],[1],[2],\ldots,[n-1]\}\text{.}\) Hint: Use the division algorithm, which says that for any \(x\in \Z\text{,}\) there are unique integers \(q,r\text{,}\) with \(r\) in the range \(0\leq r\leq n-1\text{,}\) such that \(x=qn+r\text{.}\)
  3. Draw a sketch that shows how \(\Z\) is partitioned by the mod \(n\) equivalence classes.

Instructor’s solution for Checkpoint 1.4.1.

    1. (reflexivity) It is clear that \(n|(x-x)\) for all \(x\in \Z\text{.}\)
    2. (symmetry) If \(n|(x-y)\text{,}\) say \(x-y=kn\text{,}\) then \(y-x = -kn\text{,}\) so \(n|(y-x)\text{.}\)
    3. (transitivity) If \(n|(x-y)\text{,}\) say \(x-y=kn\text{,}\) and \(n|(y-z)\text{,}\) say \(y-z=\ell n\text{,}\) then
      \begin{equation*} x-z=(x-y)+(y-z)= (k+\ell)n\text{,} \end{equation*}
      so \(n|(x-z)\text{.}\)
  2. The division algorithm says that for any \(x\in \Z\text{,}\) there are unique integers \(q,r\text{,}\) with \(r\) in the range \(0\leq r\leq n-1\text{,}\) such that \(x=qn+r\text{.}\) Thus \(x\sim_n r\text{.}\) This means that \([x]=[r]\) for some \(r\text{,}\) \(0\leq r\leq n-1\text{.}\) The uniqueness of \(r\) means that the equivalence classes \([0],[1],\ldots,[n-1]\) are distinct. We conclude that
    \begin{equation*} \Z_n=\{[0],[1],\ldots,[n-1]\}. \end{equation*}
  3. (A simple sketch might be a color-coded doubly-infinite sequence \(\ldots,-3,-2,-1,0,1,2,3,\ldots\) with colors spaced \(n\) units apart. Another possible sketch is an array with \(n\) rows indexed \(0..n-1\text{,}\) with \(k\)th row \(\ldots -3n+k,-2n+k,-n+k,k,n+k,2n+k,3n+k\ldots\text{.}\) Yet another sketch is the unit circle with dots at the \(n\)th roots of unity, with the \(k\)th row in the previously described sketch attached to \(e^{2\pi i k/n}\text{.}\) This last sketch is intructional, and connects ideas from algebra and geometry. The instructor might perform this sketch, starting with the unit circle, then winding counterclockwise adding labels \(0,1,2,\ldots,n,\ldots\text{.}\) Go around three times, inserting commas, and finally ellipses, reinforcing how the sequences grow. Then go around counter clockwise with the sequence \(-1,-2,-3,\ldots\text{,}\) winding a couple of times.)

Subsection 1.4.3 Facts

A key component of the Fact Fact 1.4.2 is that equivalence classes are disjoint. Let \(\sim\) be an equivalence relation on a set \(X\text{,}\) and let \(x,y\in X\text{.}\) Show that either \([x]=[y]\) or \([x]\cap [y]=\emptyset\text{,}\)

Instructor’s solution for Checkpoint 1.4.3.

It suffices to show that \([x]\cap [y]\neq \emptyset\) implies that \([x]=[y]\text{.}\) Suppose that \([x]\cap [y]\neq \emptyset\text{,}\) so that there is some element \(z\in X\) that lies in \([x]\cap [y]\text{.}\) Suppose further that some element \(w\in X\) lies in \([x]\text{.}\) Then we have \(w\sim x\text{,}\) \(x\sim z\text{,}\) and \(z\sim y\text{.}\) It follows from transitivity that \(w\sim y\text{,}\) so we have \(w\in [y]\text{.}\) Since \(w\) was arbitrary, we have shown that \([x]\subseteq [y]\text{.}\) The same argument, reversing the roles of \(x,y\text{,}\) shows that \([y]\subseteq [x]\text{.}\) We conclude that \([x]=[y]\text{,}\) as desired.
Note on terminology: when a function \(f\) is constant on equivalence classes, we say that the associated function \(\overline{f}\) is well-defined.

Exercises 1.4.4 Exercises

1. The rational numbers.

Let \(X\) be the set
\begin{equation*} X=\Z\times(\Z\setminus\{0\})=\{(m,n)\colon m,n\in \Z, n\neq 0\} \end{equation*}
and let \(\Q\) denote the set of rational numbers
\begin{equation*} \Q=\left\{\frac{m}{n}\colon m,n\in \Z,n\neq 0\right\}. \end{equation*}
Define the relation \(\sim\) on \(X\) by
\begin{equation*} (m,n)\sim (m',n')\Leftrightarrow mn' - m'n=0. \end{equation*}
Let \(f\colon X\to \Z\) be given by \(f(m,n)=m^2+n^2 \) and let \(g\colon X\to \Q\) be given by \(g(m,n)=\frac{m}{n} \text{.}\)
  1. Show that \(\sim\) is reflexive, symmetric, and transitive.
  2. Draw a sketch of \(X\) showing the partition \(\{[(m,n)]\colon (m,n)\in X\}\text{.}\)
  3. Is the map \(\overline{f}\colon X/\!\!\sim \to \Z\) given by \(\overline{f}([(m,n)])=f(m,n)\) well-defined? Explain.
  4. Draw a sketch of \(X\) that shows the equivalence classes \(X/\!\!\sim_f\text{.}\)
  5. Is the map \(\overline{g}\colon X/\!\!\sim \to \Q\) given by \(\overline{g}([(m,n)])=g(m,n)\) well-defined? Explain.
  6. Draw a sketch of \(X\) that shows the equivalence classes \(X/\!\!\sim_g\text{.}\)
  7. Explain why \(\sim\) and \(\sim_g\) are the same equivalence relation on \(X\text{.}\) Explain why \(X/\!\!\sim\) is in one-to-one correspondence with the rational numbers \(\Q\text{.}\)

Instructor’s solution for Exercise 1.4.4.1.

  1. Reflexivity and symmetry of \(\sim\) are clear by inspection. To show transitivity, suppose \((m,n)\sim (m',n')\) and \((m',n')\sim (m'',n'')\text{,}\) so we have \(mn'=m'n\) and \(m'n''=m''n'\text{.}\) Multiplying left side by left side and right side by right side, we have
    \begin{equation*} mn'm'n''=m'nm''n' \end{equation*}
    which is the same as
    \begin{equation*} (mn'')(m'n')=(m''n)(m'n').\hspace{1in}(\ast) \end{equation*}
    If \(m'n'=0\text{,}\) then we must have \(m'=0\) (because \(n'\neq 0\) by assumption), so we must also have \(m=m''=0\text{.}\) If \(m'n'\neq 0\text{,}\) then we may cancel \(m'n'\) on both sides of (\(\ast\)), so we have have \(mn''=m''n\text{.}\) In all cases, we have \((m,n)\sim (m'',n'')\text{,}\) as desired. Alternatively, you can jump ahead to the punch line and see that \((m,n)\sim (m',n')\) if and only if \(m/n=m'/n'\text{.}\) This makes transitivity easy.
  2. (Sketch shows integral lattice points in \(\R^2\text{,}\) minus all points on the \(y\)-axis. Equivalence classes are points that lie on lines through the origin.)
  3. The "map" \(\overline{f}\) is not well-defined. For example, we have \([(1,2)]=[(2,4)]\text{,}\) but \(1^2+2^2=5\neq 20 = 2^2+4^2\text{.}\)
  4. (Sketch shows circles, centered at the origin, with radii of sums of square integers. One such circle, with radius 5, passes through the 8 points \((\pm 3,\pm 4), (\pm 4,\pm 3)\text{.}\) The smallest circle with more interesting points has radius \(\sqrt{50}\text{,}\) where \(50=5^2 + 5^2 = 7^2+1^2\text{.}\) The smallest that is slightly more interesting is \(65= 8^2+1^2 = 7^2+4^2\) .)
  5. Yes, \(\overline{g}\) is well-defined because \(g\) is constant on equivalence classes: if \(mn'=m'n\text{,}\) then \(\frac{m}{n}=\frac{m'}{n'}\text{.}\)
  6. (Same sketch as for \(\sim\) above.)
  7. It is clear that \((m,n)\sim (m',n')\) if and only if \(m/n=m'/n'\text{.}\) Because \(g\) is onto, the fact that \(X/\!\!\sim\) is in one-to-one correspondence with \(\Q\) follows from the "furthermore" statement in Fact 1.4.5.

The integers modulo \(n\).

Let \(n\) be a positive integer.
2.
Let \(\omega\) be the complex number \(\omega=e^{2\pi i/n}\text{,}\) and let \(f\colon \Z\to \C\) be given by \(m\to \omega^m\text{.}\) Show that the equivalence relation \(\sim_f\) given by Fact 1.4.5 is the same as \(\sim_n\text{.}\)
3.
Show that the operation of addition on \(\Z_n\) given by
\begin{equation*} [x]+[y] := [x+y] \end{equation*}
is well-defined. This means showing that if \([x]=[x']\) and \([y]=[y']\text{,}\) then \([x+y]=[x'+y']\text{.}\)
4.
Show that the operation of multiplication on \(\Z_n\) given by
\begin{equation*} [x]\cdot [y] := [xy] \end{equation*}
is well-defined.
5. Alternative construction of \(\Z_n\).
Another standard definition of the set \(\Z_n\text{,}\) together with its operations of addition and multiplication, is the following. Given an integer \(a\text{,}\) we write \(a \MOD n\) to denote the remainder obtained when dividing \(a\) by \(n\) (the integer \(a \MOD n\) is the same as the integer \(r\) in the statement of the division algorithm given in Checkpoint 1.4.1). Now define \(\Z_n\) to be the set
\begin{equation*} \Z_n=\{0,1,2,\ldots,n-1\}, \end{equation*}
define the addition operation \(+_n\) on \(\Z_n\) by
\begin{equation*} x+_n y= (x+y)\MOD n \end{equation*}
and define the multiplication operation \(\cdot_n\) on \(\Z_n\) by
\begin{equation*} x\cdot_n y = (xy) \MOD n. \end{equation*}
Show that this version of \(\Z_n\) is equivalent to the version developed in Exercise 1.4.4.3 and Exercise 1.4.4.4.

Instructor’s solution for Exercise 1.4.4.2.

If \(\omega^s=\omega^t\text{,}\) then \(\omega^{s-t}=1\text{.}\) This means that \(\frac{s-t}{n}\) is an integer, which is the same as \(n|(s-t)\text{.}\)

Instructor’s solution for Exercise 1.4.4.3.

Suppose that \(x-x'=kn\) and \(y-y'=\ell n\text{.}\) Then
\begin{equation*} (x+y)-(x'+y')= (x-x')+(y-y')=(k+\ell)n \end{equation*}
so it is indeed the case that \([x+y]=[x'+y']\text{.}\)

Instructor’s solution for Exercise 1.4.4.4.

Suppose that \(x-x'=kn\) and \(y-y'=\ell n\text{.}\) Then
\begin{equation*} (xy)-(x'y')= xy-xy'+xy'-x'y'=x(y-y')+(x-x')y'=(x\ell+ky')n \end{equation*}
so it is indeed the case that \([xy]=[x'y']\text{.}\)

Instructor’s solution for Exercise 1.4.4.5.

We need to show that \(x+_n y\leftrightarrow [x]+[y]\) under the correspondence \(x\leftrightarrow [x]\text{.}\) This is the same as showing \((x+y)\MOD n = [x+y]\text{.}\) Use the division algorithm to write \(x+y=qn+r\text{.}\) Then we have \((x+y)\MOD n = r\) (by definition of \(\MOD\)) and \([x+y]=[qn+r]=[r]\) (by definition of \(\sim_n\)). A similar argument establishes \(x\cdot_n y\leftrightarrow [x][y]\text{.}\)
PrevTopNext