Section7.1Partitions of and equivalence relations on sets
Definition7.1.1
Let \(S\) be a set. Then a collection of subsets \(P=\{S_i\}_{i\in I}\) (where \(I\) is some index set) is a partition of \(S\) if each \(S_i \neq \emptyset\) and each element of \(S\) is in exactly one \(S_i\text{.}\) In other words, \(P=\{S_i\}_{i\in I}\) is a partition of \(S\) if and only if:
each \(S_i\neq \emptyset\text{;}\)
the \(S_i\) are mutually disjoint (that is, \(S_i\cap S_j =
\emptyset\) for \(i\neq j \in I\)); and
\(S=\bigcup_{i\in I}S_i\text{.}\)
The \(S_i\) are called the cells of the partition.
Example7.1.2

The set \(\{1,2,3\}\) has 5 partitions: namely,
\begin{equation*}
\{\{1,2,3\}\},\{\{1,2\},\{3\}\}, \{\{1,3\},\{2\}\},\{\{2,3\},\{1\}\} \text{ and } \{\{1\},\{2\},\{3\}\}.
\end{equation*}
The first partition we've mentioned has one cell, the next three have two cells, and the last one has three cells.

The following is a 2celled partition of \(\Z\text{:}\)
\begin{equation*}
\{\{x\in \Z\,:\ x \text{
is even} \},\{x\in \Z\,:\, x\text{ is odd} \}\}.
\end{equation*}
The number of partitions of a finite set of \(n\) elements gets large very quickly as \(n\) goes to infinity. Indeed, there are 52 partitions of a set containing just 5 elements! (The total number of partitions of an \(n\)element set is the Bell number, \(B_n\text{.}\) There is no trivial way of computing \(B_n\text{,}\) in general, though the \(B_n\) do satisfy the relatively simple recurrence relation
\begin{equation*}
B_{n+1}=\sum_{k=0}^n \binom{n}{k} B_k,
\end{equation*}
for each \(n\geq 1\text{.}\)) But our goal here is not to count the number of partitions of a given set, but rather to use particular partitions of a group \(G\) to help us study that group's structure. We turn now to our next definition.
Definition7.1.3
Let \(S\) be a set. Then a relation on \(S\) is a subset \(R\) of \(S\times S\text{.}\)If \(R\) is a relation on \(S\) and \(x,y\in S\text{,}\) then we say \(x\) is related to \(y\text{,}\) and write \(x R y\text{,}\) if \((x,y)\in R\text{;}\) otherwise, we say that \(x\) is not related to \(y\text{,}\) and write \(x \not R y\text{.}\)
We are already familiar with some relations on \(\R\text{.}\) Common such relations are \(=\text{,}\) \(\neq\text{,}\) \(\lt\text{,}\) \(\leq\text{,}\) \(>\text{,}\) and \(\geq\text{;}\) they contain exactly the elements we'd expect them to contain.
Example7.1.5
\(\lt\) is a relation on \(\R\) that contains, for instance, \((3,4)\) but not \((3,3)\) or \((4,3)\text{;}\) \(\leq\) is a relation on \(\R\) that contains \((3,4)\) and \((3,3)\) but not \((4,3)\text{.}\)
Given any \(n\in \Z^+\text{,}\) congruence modulo \(n\text{,}\) denoted \(\equiv_n\text{,}\) is a relation on \(\Z\text{,}\) where \(\equiv_n\) is defined to be \(\{(x,y) \in \Z
\times \Z \,:\, n \text{ divides } xy\}\text{.}\)
We can define a relation \(R\) on \(C^1\) (the set of all differentiable functions from \(\R\) to \(\R\) whose derivatives are continuous) by declaring that \((f,g)\in C^1 \times C^1\) is in \(R\) if and only if \(f'=g'\text{.}\)
Definition7.1.6
Let \(R\) be a relation on a set \(S\text{.}\) Then \(R\) is said to be:
reflexive on \(S\) if \(xR x\) for every \(x\in S\text{;}\)
symmetric on \(S\) if whenever \(x,y\in S\) with \(xR y\) we also have \(yR x\text{;}\) and
transitive on \(S\) if whenever \(x,y,z\in S\) with \(xR y\) and \(yR z\) we also have \(xR z\text{.}\)
A relation that is reflexive, symmetric, and transitive is called an equivalence relation.
If we know, or plan to prove, that a relation is an equivalence relation, by convention we may denote the relation by \(\sim\text{,}\) rather than by \(R\text{.}\)
Example7.1.8
\(\lt\) is not an equivalence relation on \(\R\) because it is not reflexive: for instance, \(3\not\lt 3\text{.}\) \(\leq\) is also not an equivalence relation on \(\R\text{,}\) since even though it is reflexive, it's not symmetric: indeed, \(3\leq 4\) but \(4\not\leq 3\text{.}\)
Given any \(n\in \Z^+\text{,}\) \(\equiv_n\) is an equivalence relation on \(\Z\text{.}\) The proof of this is left as an exercise for the reader.
The relation \(R\) on \(C^1\) discussed above (\(fR g\) iff \(f'=g'\)) is an equivalence relation on \(C^1\text{.}\)
\(\simeq\) is an equivalence relation on any set of groups. This follows from Theorem 3.3.3.
Define relation \(R\) on \(\Z\) by \(xR y\) if and only if \(xy
\geq 0\text{.}\) Is \(R\) an equivalence relation on \(\Z\text{?}\) Well, for every \(x\in \Z\text{,}\) \(x^2\geq 0\text{,}\) so \(R\) is reflexive. Moreover, if \(x,y\in
\Z\) with \(xy \geq 0\text{,}\) then \(yx \geq 0\text{;}\) so \(R\) is symmetric. But \(R\) is not transitive: indeed, \(3,0,4\in \Z\) with \(3(0)=0
\geq 0\) and \(0(4)=0\geq 0\text{,}\) so \(3\R 0\) and \(0 R 4\text{;}\) but \(3(4)=12 \not \geq 0\text{.}\) So \(R\) isn't transitive, and hence is not an equivalence relation.
Definition7.1.9
Given an equivalence relation \(\sim\) on a set \(S\text{,}\) for each \(x\in S\) we define the equivalence class of \(x\) under \(\sim\) to be
\begin{equation*}
[x]=\{y\in S\,:\, y\sim x\}.
\end{equation*}
These sets \([x]\) (\(x\in S\)) are called the equivalence classes of \(S\) under \(\sim\).
We have now the following Very Important Lemma:
Lemma7.1.11
Let \(\sim\) be an equivalence relation on set \(S\text{.}\) Then for \(x,y\in S\text{,}\) the following are equivalent:
\(y\in [x]\text{;}\)
\([x]=[y]\text{;}\)
\(x\in [y]\text{.}\)
To prove that the first and second statements are equivalent: Let \(x, y\in S\text{.}\) If \(y\in
[x]\text{,}\) then \(y \sim x\text{,}\) so for every \(z\in [y]\) (that is, for every \(z\) in \(S\) with \(z\sim y\)), we have, by transitivity, \(z\sim x\text{,}\) so \(z\in [x]\text{.}\) On the other hand, by the symmetry of \(\sim\) we have \(x\sim y\text{;}\) so for every \(z\in [x]\text{,}\) we have, again by transitivity, that \(z\in [y]\text{.}\) Thus, \([x]=[y]\text{.}\) Conversely, if \([x]=[y]\text{,}\) then since \(y\in [y]=[x]\text{.}\)
The proof that the second and third statements are equivalent is nearly identical.
Definition7.1.12
In many cases there are many distinct elements \(x,y\in S\) with \([x]=[y]\text{;}\) thus, there are usually many different ways we could denote a particular equivalence class of \(S\) under \(\sim\text{.}\) Element \(y\in S\) is called a representative of class \(X\) if \(y\in X\text{.}\)
Example7.1.13
Consider the equivalence relation \(\equiv_2\) on \(\Z\text{.}\) Under this relation, \([0]=\{0,\pm 2, \pm 4, \ldots\}\) and \([1]=\{\ldots, 3, 1, 1, 3, \ldots\}\text{;}\) in fact, if we let \(E\) be the set of all even integers and \(O\) the set of all odd integers, then for \(x\in \Z\text{,}\) \([x]=E\) if \(x\) is even and \(O\) if \(x\) is odd. Thus, the set of all equivalence classes of \(\Z\) under \(\equiv_2\) is the 2element set \(\{E,O\}\text{:}\) every even integer is a representative of \(E\text{,}\) while every odd integer is a representative of \(O\text{.}\)
For \(f\in C^1\text{,}\) the equivalence class of \(f\) under \(R\) (defined above) is the set of all functions in \(C^1\) of the form \(g(x)=f(x)+c\text{,}\) where \(c\in \R\text{.}\)

Let \(A=\{a,b,c\}\text{,}\) and define \(\sim\) on the power set \(P(A)\) of \(A\) by \(X\sim Y\) if and only if \(X=Y\text{.}\) It is straightforward to show that \(\sim\) is an equivalence relation on \(P(A)\text{,}\) under which \(P(A)\) has exactly 4 distinct equivalence classes:
\begin{equation*}
[\emptyset]=\{\emptyset\},
\end{equation*}
\begin{equation*}
[\{a\}]=[\{b\}]=[\{c\}]=\{\{a\},\{b\}, \{c\}\},
\end{equation*}
\begin{equation*}
[\{a,b\}]=[\{a,c\}]=[\{b,c\}]=\{\{a,b\},\{a,c\},\{b,c\}\}, \text{ and }
\end{equation*}
\begin{equation*}
[A]=\{A\}.
\end{equation*}
Theorem7.1.15
Let \(S\) be a set. Then:
If \(\sim\) is an equivalence relation on \(S\text{,}\) then the set of all equivalence classes of \(S\) under \(\sim\) is a partition of \(S\text{;}\) and
If \(P\) is a partition of \(S\text{,}\) then the relation on \(S\) defined by \(x\sim y\) if and only \(x\) is in the same cell of \(P\) as \(y\) is an equivalence relation on \(S\text{.}\)
Notice that in each case, the cells of the partition are the equivalence classes of the set under the corresponding equivalence relation.
Proof
To prove the first statement: Let \(\sim\) be an equivalence relation on \(S\text{.}\) Clearly, the equivalence classes of \(S\) under \(\sim\) are nonempty sets whose union is \(S\text{.}\) Thus, it suffices to show \(X
\cap Y =\emptyset\) for each pair of equivalence classes \(X\neq
Y\) of \(S\) under \(\sim\text{.}\) Let \(X,Y\) be equivalence classes of \(S\) under \(\sim\) that are NOT disjoint. Then there exists an element \(z\in X\cap Y\text{.}\) Then by Lemma 7.1.11, \([z]=X\) and \([z]=Y\text{;}\) so \(X=Y\text{.}\) Thus, if \(X\neq Y\text{,}\) then \(X\cap Y
=\emptyset\text{.}\)
Finally, it is straightforward (almost silly!) to prove that \(\sim\) is reflexive, symmetric, and transitive.
Example7.1.16
For \(n\in \Z^+\text{,}\) the set of the equivalence classes of \(\Z\) under \(\equiv_n\) is the partition \(\{[0],[1],\ldots,[n1]\}\) of \(\Z\text{.}\) (The partition \(\{E
,O\}\) of \(\Z\) discussed above is this partition when \(n=2\text{.}\))