Skip to main content

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

Subsection 1.4.2 Facts

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

Subsection 1.4.3 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*}
  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{.}\)

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

Subsection 1.4.4 A 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.

Exercises 1.4.5 Exercises

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.