7.1: Partitions of and Equivalence Relations on Sets

Definition: Partition and Cells

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.

Example \(\PageIndex{1}\)

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 \(\mathbb{Z}\text{:}\)

\begin{equation*} \{\{x\in \mathbb{Z}\,:\ x \text{ is even} \},\{x\in \mathbb{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.

Definition: Relation

Let \(S\) be a set. Then a relation on \(S\) is a subset \(R\) of \(S\times S\text{.}\)¹More generally, if \(S\) and \(T\) are sets, a relation between \(S\) and \(T\) is a subset of \(S \times T\text{.}\) We will not, however, in our class consider the cases in which \(S\) and \(T\) are different sets.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{.}\)

Remark

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 \(\mathbb{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.

Example \(\PageIndex{2}\)

1. \(\lt\) is a relation on \(\mathbb{R}\) that contains, for instance, \((3,4)\) but not \((3,3)\) or \((4,3)\text{;}\) \(\leq\) is a relation on \(\mathbb{R}\) that contains \((3,4)\) and \((3,3)\) but not \((4,3)\text{.}\)
2. Given any \(n\in \mathbb{Z}^+\text{,}\) congruence modulo \(n\text{,}\) denoted \(\equiv_n\text{,}\) is a relation on \(\mathbb{Z}\text{,}\) where \(\equiv_n\) is defined to be \(\{(x,y) \in \mathbb{Z} \times \mathbb{Z} \,:\, n \text{ divides } x-y\}\text{.}\)
3. We can define a relation \(R\) on \(C^1\) (the set of all differentiable functions from \(\mathbb{R}\) to \(\mathbb{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{.}\)

Definition: Equivalence Relation

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

Remark

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

Example \(\PageIndex{3}\)

1. \(\lt\) is not an equivalence relation on \(\mathbb{R}\) because it is not reflexive: for instance, \(3\not\lt 3\text{.}\) \(\leq\) is also not an equivalence relation on \(\mathbb{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 \mathbb{Z}^+\text{,}\) \(\equiv_n\) is an equivalence relation on \(\mathbb{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.1\).
5. Define relation \(R\) on \(\mathbb{Z}\) by \(xR y\) if and only if \(xy \geq 0\text{.}\) Is \(R\) an equivalence relation on \(\mathbb{Z}\text{?}\) Well, for every \(x\in \mathbb{Z}\text{,}\) \(x^2\geq 0\text{,}\) so \(R\) is reflexive. Moreover, if \(x,y\in \mathbb{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 \mathbb{Z}\) with \(3(0)=0 \geq 0\) and \(0(-4)=0\geq 0\text{,}\) so \(3\mathbb{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.

Definition: Equivalence Class of x under ~

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

Remark

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

We have now the following Very Important Lemma:

Lemma \(\PageIndex{1}\)

Let \(\sim\) be an equivalence relation on set \(S\text{.}\) Then for \(x,y\in S\text{,}\) the following are equivalent:

1. \(y\in [x]\text{;}\)
2. \([x]=[y]\text{;}\)
3. \(x\in [y]\text{.}\)

Proof

To prove that the first and second statements are equivalent: Let \(x,y∈S\). If \(y∈[x]\), then \(y\sim x\), so for every \(z∈[y]\) (that is, for every \(z\) in \(S\) with \(z\sim y\)), we have, by transitivity, \(z\sim x\), so \(z∈[x]\). On the other hand, by the symmetry of \(\sim\) we have \(x\sim y\); so for every \(z∈[x]\), we have, again by transitivity, that \(z∈[y]\). Thus, \([x]=[y]\). Conversely, if \([x]=[y]\), then since \(y∈[y]=[x]\).

The proof that the second and third statements are equivalent is nearly identical.

Definition: Representative

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

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.

Example \(\PageIndex{4}\)

1. Consider the equivalence relation \(\equiv_2\) on \(\mathbb{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 \mathbb{Z}\text{,}\) \([x]=E\) if \(x\) is even and \(O\) if \(x\) is odd. Thus, the set of all equivalence classes of \(\mathbb{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 \mathbb{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*}

Remark

Notice that the complete set \(\{E,O\}\) of distinct equivalence classes of \(\mathbb{Z}\) under \(\equiv_n\) is a partition of \(\mathbb{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.

Theorem \(\PageIndex{1}\)

Let \(S\) be a set. Then:

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

2. 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\). Clearly, the equivalence classes of \(S\) under \(\sim\) are nonempty sets whose union is \(S\). Thus, it suffices to show \(X∩Y=∅\) for each pair of equivalence classes \(X≠Y\) of \(S\) under \(\sim\). Let \(X,Y\) be equivalence classes of \(S\) under \(\sim\) that are NOT disjoint. Then there exists an element \(z∈X∩Y\). Then by Lemma \(7.1.1\), \([z]=X\) and \([z]=Y\); so \(X=Y\). Thus, if \(X≠Y\), then \(X∩Y=∅\).

Finally, it is straightforward (almost silly!) to prove that \(\sim\) is reflexive, symmetric, and transitive.

Example \(\PageIndex{5}\)

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

Notes

1. More generally, if \(S\) and \(T\) are sets, a relation between \(S\) and \(T\) is a subset of \(S×T\). We will not, however, in our class consider the cases in which \(S\) and \(T\) are different sets.