# Introduction to Groups and Geometries

## Section1.4Equivalence relations

### Subsection1.4.1Definitions

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
$$[x] = \{y\in X\colon x\sim y\},\tag{1.4.1}$$
called the equivalence class of the element $$x\text{.}$$ The set of equivalence classes is denoted $$X/\!\!\sim\text{,}$$ that is,
$$X/\!\!\sim \; = \{[x]\colon x\in X\}.\tag{1.4.2}$$
A partition of a set $$X$$ is a collection of nonempty disjoint sets whose union is $$X\text{.}$$

### Subsection1.4.2Important 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{.}$$
1. 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*}
2. (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.)

### Subsection1.4.3Facts

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.

### Exercises1.4.4Exercises

#### 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{.}$$