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

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.

Draw a commutative diagram that illustrates the distributive law for $\Z_n\text{.}$

\begin{equation*} [x]\left([y]+[z]\right) = [x][y] + [x][z] \end{equation*}
###### 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{,}$ let $a \MOD n$ be the unique integer $r$ in the range $0\leq r\leq n-1$ such that $a=qn+r$ for some integer $q$ (that is, $r$ is the remainder obtained when dividing $a$ by $n$). 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.