- Verify that the relation \(\sim_n\) is indeed an equivalence relation.
- 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{.}\)
- Draw a sketch that shows how \(\Z\) is partitioned by the mod \(n\) equivalence classes.
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\},\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\}.\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 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*}
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}\)).
Checkpoint 1.4.1.
Subsection 1.4.3 Facts
Fact 1.4.2. 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 \(\sim\) on \(X\text{,}\) the collection
\begin{equation*}
X/\!\!\sim \; = \{[x]\colon x\in X\}
\end{equation*}
is a partition of \(X\text{.}\) Conversely, given a partition \({\mathcal P}\) of \(X\text{,}\) the relation \(\sim_{\mathcal P}\) defined by
\begin{equation*}
x\sim_{\mathcal P} y \Leftrightarrow x,y \text{ lie in the same element of } {\mathcal P}
\end{equation*}
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{.}\)
Checkpoint 1.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{.}\)
Fact 1.4.4. Construction of functions on sets of equivalence classes.
Let \(\sim\) 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.5. 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
\begin{equation*}
x\sim_f y \Leftrightarrow f(x)=f(y).
\end{equation*}
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.
Exercises 1.4.4 Exercises
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{.}\)
- Show that \(\sim\) is reflexive, symmetric, and transitive.
- Draw a sketch of \(X\) showing the partition \(\{[(m,n)]\colon (m,n)\in X\}\text{.}\)
- Is the map \(\overline{f}\colon X/\!\!\sim \to \Z\) given by \(\overline{f}([(m,n)])=f(m,n)\) well-defined? Explain.
- Draw a sketch of \(X\) that shows the equivalence classes \(X/\!\!\sim_f\text{.}\)
- Is the map \(\overline{g}\colon X/\!\!\sim \to \Q\) given by \(\overline{g}([(m,n)])=g(m,n)\) well-defined? Explain.
- Draw a sketch of \(X\) that shows the equivalence classes \(X/\!\!\sim_g\text{.}\)
- 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.
