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

\begin{equation} [x] = \{y\in X\colon x\sim y\},\label{equivalenceclass}\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\}.\label{setofequivclasses}\tag{1.4.2} \end{equation}

A partition of a set $$X$$ is a collection of nonempty disjoint sets whose union is $$X\text{.}$$

### Subsection1.4.2Facts

Note on terminology: when a function $$f$$ is constant on equivalence classes, we say that the associated function $$\overline{f}$$ is well-defined.

### Subsection1.4.3Important 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 = \{,,,\ldots,[n-1]\}. \end{equation*}
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 $$\{,,,\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{.}$$

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

### Subsection1.4.4A useful tool: commutative diagrams

A directed graph (or digraph ) is a set $$V$$ of vertices and a set $$E\subset V\times V$$ of directed edges. We draw pictures of digraphs by drawing an arrow pointing from a vertex $$v$$ to a vertex $$w$$ whenever $$(v,w)\in E\text{.}$$ See Figure 1.4.5.

A path in a directed graph is a sequence of vertices $$v_0,v_2,\ldots,v_{n}$$ such that $$(v_{i-1},v_i)\in E$$ for $$1\leq i\leq n\text{.}$$ The vertex $$v_0$$ is called the initial vertex and $$v_n$$ is called the final vertex of the path $$v_0,v_2,\ldots,v_{n}\text{.}$$ Figure 1.4.5. Example of a directed graph with vertex set $$V=\{a,b,c,d\}$$ and edge set $$E=\{(a,b),(c,b),(c,a),(a,d),(d,c)\text{.}$$ The vertex sequences $$c,b$$ and $$c,a,b$$ are both paths from $$c$$ to $$b\text{.}$$

A commutative diagram is a directed graph with two properties.

1. Vertices are labeled by sets and directed edges are labeled by functions between those sets. That is, the directed edge $$f=(X,Y)$$ denotes a function $$f\colon X\to Y\text{.}$$
2. Whenever there are two paths from an initial vertex $$X$$ to a final vertex $$Y\text{,}$$ the composition of functions along one path is equal to the composition of functions along the other path. That is, if $$X_0,X_1,\ldots,X_n$$ is a path with edges $$f_i\colon X_{i-1}\to X_{i}$$ for $$1\leq i\leq n$$ and $$X_0=Y_0,Y_1,Y_2,\ldots,Y_m=X_n$$ is a path with edges $$g_i\colon Y_{i-1}\to Y_{i}$$ for $$1\leq i\leq m\text{,}$$ then
\begin{equation*} f_n\circ f_{n-1}\circ\cdots\circ f_1=g_m\circ g_{m-1}\circ\cdots\circ g_1. \end{equation*}

Figure 1.4.6 shows a commutative diagram that goes with Fact 1.4.2. Figure 1.4.7 shows a commutative diagram that illustrates the definition of conjugate transformations. Figure 1.4.6. A commutative diagram showing the relationship $$\overline{f}\circ \pi = f$$ in Fact 1.4.2. Figure 1.4.7. A commutative diagram illustrating the definition of conjugate transformations $$f,g$$ given in Exercise Group 1.3.3.3–6.

### Exercises1.4.5Exercises

###### The integers modulo $$n\text{.}$$
Let $$n$$ be a positive integer.
###### 1.

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.3 is the same as $$\sim_n\text{.}$$

###### 2.

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

###### 3.

Show that the operation of multiplication on $$\Z_n$$ given by

\begin{equation*} [x]\cdot [y] := [xy] \end{equation*}

is well-defined.

###### 4.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.4). 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.5.2 and Exercise 1.4.5.3.

###### 5.Commutative diagram examples.
1. Draw a commutative diagram that illustrates the results of Exercise 1.3.3.5.
2. The distributive law for $$\Z_n$$ says that
\begin{equation*} [x]\left([y]+[z]\right) = [x][y] + [x][z] \end{equation*}
for all $$[x],[y],[z]\in \Z_n\text{.}$$ Label the maps in the commutative diagram below to express the distributive law. Figure 1.4.8.