1.4: Equivalence Relations

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∼y if \(\)R is understood by context, to denote that \(\).(x,y)∈R. A relation is reflexive if \(\)x∼x for every \(\)x in \(\).X. 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\},\label{equivalenceclass}\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\}.\label{setofequivclasses}\tag{1.4.2}
\]

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

Facts

Fact 1.4.1. Equivalence relations and partitions.

Let \(X\) be a set. Equivalence relations on \(X\) and partitions of \(X\) are in one-to-one correspondence, as follows. Given an equivalence relation \(∼\) on \(X\text{,}\) the collection

\[
X/\!\!\sim \; = \{[x]\colon x\in X\}
\nonumber \]

is a partition of \(X\text{.}\) Conversely, given a partition \({\mathcal P}\) of \(X\text{,}\) the relation \(\sim_{\mathcal P}\) defined by

\[
x\sim_{\mathcal P} y \Leftrightarrow x,y \text{ lie in the same element of } {\mathcal P}
\nonumber \]

is an equivalence relation. These correspondences are inverse to one another. That is, \(\sim = \sim_{(X/\sim)}\) and \(X/(\sim_{\mathcal P}) = {\mathcal P}\text{.}\)

Fact 1.4.2. Construction of functions on sets of equivalence classes.

Let \(∼\) be an equivalence relation on a set \(X\text{,}\) let \(\pi\colon X\to X/\!\!\sim\) denote the map given by \(x\to [x]\text{,}\) and let \(f\colon X\to Y\) be a function. There exists a map \(\overline{f}\colon X/\!\!\sim \to Y\) such that \((\overline{f}\circ \pi)(x)=f(x)\) for all \(x\in X\) if and only if \(f\) is constant on equivalence classes (that is, if and only if \([x\sim y\Rightarrow f(x)=f(y)]\text{.}\)

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

Fact 1.4.3. Construction of equivalence relations and partitions from functions.

Given a function \(f\colon X\to Y\text{,}\) there is a natural equivalence relation \(\sim_f\) on \(X\) given by \(x\sim_f y\) if and only if \(f(x)=f(y)\text{.}\) The corresponding set of equivalence classes is \(X/\!\!\sim_f \; = \{f^{-1}(y)\colon y\in f(X)\}\text{.}\) Furthermore, the function \(X/\!\!\sim_f \; \to f(X)\) given by \([x]\to f(x)\) is a one-to-one correspondence.

Important example: the integers modulo an integer n

Let \(n\) be a positive integer. Let \(\sim_n\) be the relation on the integers \(\mathbb{Z}\) given by

\[
x\sim_n y \Leftrightarrow n|(x-y)
\nonumber \]

(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

\[
Z/\!\!\sim_n = \{[0],[1],[2],\ldots,[n-1]\}.
\nonumber \]

Checkpoint 1.4.4.

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

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 \(1\leq i\leq m\text{,}\) for \(1\leq i\leq m\text{,}\) then

   \[
   f_n\circ f_{n-1}\circ\cdots\circ f_1=g_m\circ
   g_{m-1}\circ\cdots\circ g_1.
   \nonumber \]

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

The integers modulo \(n\text{.}\) Let n be a positive integer.

Exercise 1

Let ω be the complex number \(\omega=e^{2\pi i/n}\text{,}\) and let \(f\colon \mathbb{Z}\to \mathbb{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{.}\)

Exercise 2

Show that the operation of addition on \(\mathbb{Z}_n\) given by

\[
[x]+[y] := [x+y]
\nonumber \]

is well-defined. This means showing that if \([x]=[x']\) and \([y]=[y']\text{,}\) then \([x+y]=[x'+y']\text{.}\)

Exercise 3

Show that the operation of multiplication on \(\mathbb{Z}_n\) given by

\[
[x]\cdot [y] := [xy]
\nonumber \]

is well-defined.

Exercise 4

Alternative construction of \(\mathbb{Z}_n\) Another standard definition of the set \(\mathbb{Z}_n\), 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 \(\mathbb{Z}_n\) to be the set

\[
\mathbb{Z}_n=\{0,1,2,\ldots,n-1\},
\nonumber \]

define the addition operation \(+_n\) on \(\mathbb{Z}_n\) by

\[
x+_n y= (x+y)MOD n
\nonumber \]

and define the multiplication operation \(\cdot_n\) on \(\mathbb{Z}_n\) by

\[
x\cdot_n y = (xy) MOD n.
\nonumber \]

Show that this version of \(\mathbb{Z}_n\) is equivalent to the version developed in Exercise 1.4.5.2 and Exercise 1.4.5.3.

Exercise 5

Commutative diagram examples.

1. Draw a commutative diagram that illustrates the results of Exercise 1.3.3.5.
2. The distributive law for \(\mathbb{Z}_n\) says that

   \[
   [x]\left([y]+[z]\right) = [x][y] +
   [x][z]
   \nonumber \]

   for all \([x],[y],[z]\in \mathbb{Z}_n\text{.}\) Label the maps in the commutative diagram below to express the distributive law.

   

   Figure 1.4.8.

Exercise 6

Prove Fact 1.4.1.

Exercise 7

Prove Fact 1.4.2.

Exercise 8

Prove Fact 1.4.3.