Skip to main content
\(\def\Z{\mathbb{Z}} \def\zn{\mathbb{Z}_n} \def\znc{\mathbb{Z}_n^\times} \def\R{\mathbb{R}} \def\Q{\mathbb{Q}} \def\C{\mathbb{C}} \def\N{\mathbb{N}} \def\M{\mathbb{M}} \def\G{\mathcal{G}} \def\0{\mathbf 0} \def\Gdot{\langle G, \cdot\,\rangle} \def\phibar{\overline{\phi}} \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\Ker}{Ker} \def\siml{\sim_L} \def\simr{\sim_R} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

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:

  1. each \(S_i\neq \emptyset\text{;}\)

  2. the \(S_i\) are mutually disjoint (that is, \(S_i\cap S_j = \emptyset\) for \(i\neq j \in I\)); and

  3. \(S=\bigcup_{i\in I}S_i\text{.}\)

The \(S_i\) are called the cells of the partition.

Example7.1.2

  1. 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.

  2. The following is a 2-celled 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{.}\) 1 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{.}\)

Remark7.1.4

If there is a conventional notation used to denote a particular relation on a set, we will usually use that notation, rather than \(R\text{,}\) to denote the relation.

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

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

  2. 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 } x-y\}\text{.}\)

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

Remark7.1.7

You can think of an equivalence relation on a set \(S\) as being a “weak version” of equality on \(S\text{.}\) Indeed, \(=\) is an equivalence relation on any set \(S\text{,}\) but it also has a very special property that most equivalence relations don't have: namely, no element of \(S\) is related to any other element of \(S\) under \(=\text{.}\)

Example7.1.8

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

  2. 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.

  3. The relation \(R\) on \(C^1\) discussed above (\(fR g\) iff \(f'=g'\)) is an equivalence relation on \(C^1\text{.}\)

  4. \(\simeq\) is an equivalence relation on any set of groups. This follows from Theorem 3.3.3.

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

Remark7.1.10

Note that, by reflexivity of \(\sim\text{,}\) \(x\in [x]\) for every \(x\in S\text{.}\)

We have now the following Very Important Lemma:

Proof
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

  1. 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 2-element set \(\{E,O\}\text{:}\) every even integer is a representative of \(E\text{,}\) while every odd integer is a representative of \(O\text{.}\)

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

  3. 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*}
Remark7.1.14

Notice that the complete set \(\{E,O\}\) of distinct equivalence classes of \(\Z\) under \(\equiv_n\) is a partition of \(\Z\text{,}\) and the complete set

\begin{equation*} \{[\emptyset],[\{a\}],[\{a,b\}],[A]\} \end{equation*}

of distinct equivalence classes of \(P(A)\) under \(\sim\) is a partition of \(P(A)\text{.}\) This is not a coincidence! It turns out that equivalence relations and partitions go hand in hand.

Proof
Example7.1.16

  1. For \(n\in \Z^+\text{,}\) the set of the equivalence classes of \(\Z\) under \(\equiv_n\) is the partition \(\{[0],[1],\ldots,[n-1]\}\) of \(\Z\text{.}\) (The partition \(\{E ,O\}\) of \(\Z\) discussed above is this partition when \(n=2\text{.}\))