# 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:

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

##### 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{.}$)