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

#### Checkpoint1.4.1.

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.

### Subsection1.4.3Facts

#### Checkpoint1.4.3.

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

#### 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.