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
A partition of a set \(X\) is a collection of nonempty disjoint sets whose union is \(X\text{.}\)
Subsection1.3.2Facts
Fact1.3.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 \(\sim\) on \(X\text{,}\) the collection
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{.}\)
Fact1.3.2.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.
Fact1.3.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.
Subsection1.3.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
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{.}\)
Instructor's solution for Checkpoint 1.3.4.
(reflexivity) It is clear that \(n|(x-x)\) for all \(x\in \Z\text{.}\)
(symmetry) If \(n|(x-y)\text{,}\) say \(x-y=kn\text{,}\) then \(y-x = -kn\text{,}\) so \(n|(y-x)\text{.}\)
(transitivity) If \(n|(x-y)\text{,}\) say \(x-y=kn\text{,}\) and \(n|(y-z)\text{,}\) say \(y-z=\ell n\text{,}\) then
The division algorithm 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{.}\) Thus \(x\sim_n r\text{.}\) This means that \([x]=[r]\) for some\(r\text{,}\)\(0\leq r\leq n-1\text{.}\) The uniqueness of \(r\) means that the equivalence classes \([0],[1],\ldots,[n-1]\) are distinct. We conclude that
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}\)).
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.3.5.
A path in a directed graph is a sequence of vertices \(v_0,v_1,\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_1,\ldots,v_{n}\text{.}\)
Figure1.3.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.
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{.}\)
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
Figure 1.3.6 shows a commutative diagram that goes with Fact 1.3.2. Figure 1.3.7 shows a commutative diagram that illustrates the definition of conjugate transformations.
Figure1.3.6.A commutative diagram showing the relationship \(\overline{f}\circ \pi = f\) in Fact 1.3.2.
Figure1.3.7.A commutative diagram illustrating the definition of conjugate transformations \(f,g\) given in Exercise Group 1.2.3.3–6.
Exercises1.3.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.3.3 is the same as \(\sim_n\text{.}\)
2.
Show that the operation of addition on \(\Z_n\) given by
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.3.4). Now define \(\Z_n\) to be the set
If \(\omega^s=\omega^t\text{,}\) then \(\omega^{s-t}=1\text{.}\) This means that \(\frac{s-t}{n}\) is an integer, which is the same as \(n|(s-t)\text{.}\)
Instructor's solution for Exercise 1.3.5.2.
Suppose that \(x-x'=kn\) and \(y-y'=\ell n\text{.}\) Then
so it is indeed the case that \([xy]=[x'y']\text{.}\)
Instructor's solution for Exercise 1.3.5.4.
We need to show that \(x+_n y\leftrightarrow [x]+[y]\) under the correspondence \(x\leftrightarrow [x]\text{.}\) This is the same as showing \((x+y)\MOD n = [x+y]\text{.}\) Use the division algorithm to write \(x+y=qn+r\text{.}\) Then we have \((x+y)\MOD n = r\) (by definition of \(\MOD\)) and \([x+y]=[qn+r]=[r]\) (by definition of \(\sim_n\)). A similar argument establishes \(x\cdot_n y\leftrightarrow [x][y]\text{.}\)
5.Commutative diagram examples.
Draw a commutative diagram that illustrates the results of Exercise 1.2.3.5.
Let \(\sim\) be an equivalence relation on a set \(X\text{.}\) The reflexive property of \(\sim\) implies that \(X=\bigcup_{x\in X} [x]\text{.}\) The transitive property of \(\sim\) implies that \([x]\cap [y] = \emptyset\) if \([x]\neq [y]\text{.}\) Thus the set of equivalence classes is a partition of \(X\text{.}\) Conversely, let \({\mathcal
P}\) be a partition of \(X\) with associated relation \(\sim_{\mathcal P}\text{.}\) It is clear that the reflexive, symmetric, and transitive properties hold for \(\sim_{\mathcal P}\text{.}\) (To write these out is painful. You have to write sentences like this: "If \(x\in X\) lies in \(U\in{\mathcal P}\text{,}\) then \(x\in X\) lies in \(U\in{\mathcal P}\text{,}\) so \(\sim_{\mathcal P}\) is reflexive.") It is also clear that the correspondences \(\sim \to X/\!\!\sim\) and \({\mathcal
P}\to \sim_{\mathcal P}\) are inverse to one another.
First we consider the "if" direction. Suppose \(f\colon X\to Y\) is constant on equivalence classes of the equivalence relation \(\sim\) on \(X\text{.}\) It is clear then that \(\overline{f}([x])=f(x)\) is well-defined. For the "only if" direction, suppose that \(\overline{f}\colon X\to Y\) given by \(\overline{f}([x])=f(x)\) exists. Now if \(x\sim y\text{,}\) we have \([x]=[y]\text{,}\) so \(f(x)=\overline{f}([x])=\overline{f}([y])=f(y)\text{.}\) It follows that \(f\) is constant on equivalence classes.
Let \(f\colon X\to Y\) be a function. It is clear that the associated relation \(\sim_f\) is an equivalence relation. (Again, proving the three properties would be painful because of the the obviousness. You would have to say things like "if \(f(x)=f(y)\) then \(f(y)=f(x)\text{,}\) so \(\sim_f\) is symmetric".) The equivalence classes of \(\sim_f\) are clearly the preimages \(f^{-1}(\{y\})\) of 1-point sets \(\{y\}\subseteq Y\text{.}\) The function \(X/\!\!\sim_f\to
f(X)\) given by \([x]\to f(x)\) is clearly onto. (You can justify the existence of \(f\) using Fact 1.3.2.) To see that this function is also one-to-one, just note that if \(f(x)=f(y)\) then \([x]=[y]\text{,}\) by definition of \(\sim_f\text{.}\)
