Section 7.3 Partitions
Theorem 7.42 and
Theorem 7.43 imply that if
\(\sim\) is an equivalence relation on a set
\(A\text{,}\) then
\(\sim\) breaks
\(A\) up into pairwise disjoint “chunks”, where each chunk is some
\([a]\) for
\(a\in A\text{.}\) As you have probably already noticed, equivalence relations are intimately related to the following concept.
Definition 7.51.
A collection \(\Omega\) of subsets of a set \(A\) is said to be a partition of \(A\) if the elements of \(\Omega\) satisfy:
Each \(X\in \Omega\) is nonempty,
For all \(X,Y\in\Omega\text{,}\) \(X\cap Y=\emptyset\) when \(X\neq Y\text{,}\) and
\(\displaystyle \bigcup_{X\in\Omega}X=A\text{.}\)
That is, the elements of \(\Omega\) are pairwise disjoint nonempty sets and their union is all of \(A\text{.}\) Each \(X\in \Omega\) is called a block of the partition.
Example 7.52.
Consider the equivalence relation
\(\sim\) on the set
\(P\) described in
Example 7.45. Recall that the equivalence classes correspond to collections of individuals with the same last name. Since each equivalence class is nonempty and each resident of the town belongs to exactly one equivalence class, the collection of equivalence classes forms a partition of
\(P\text{.}\) That is,
\(P/\mathord\sim\) is a partition of
\(P\text{,}\) where the blocks of the partition correspond to sets of residents with the same last name.
Example 7.53.
Each of the following is an example of a partition of the set given in parentheses.
Democrat, Republican, Independent, Green Party, Libertarian, etc. (set of registered voters)
Freshman, sophomore, junior, senior (set of high school students)
Evens, odds (set of integers)
Rationals, irrationals (set of real numbers)
Example 7.54.
Let \(A=\{a,b,c,d,e,f\}\) and \(\Omega=\{\{a\}, \{b,c,d\}, \{e,f\}\}\text{.}\) Since the elements of \(\Omega\) are pairwise disjoint nonempty subsets of \(A\) such that their union is all of \(A\text{,}\) \(\Omega\) is a partition of \(A\) consisting of three blocks.
Problem 7.55.
Find a partition of \(A\) consisting of four blocks.
Find a collection of subsets of \(A\) that does not form a partition. See how many ways you can prevent your collection from being a partition.
Problem 7.56.
For each of the following, find a partition of \(\mathbb{Z}\) with the given properties.
A partition of \(\mathbb{Z}\) that consists of finitely many blocks, where each of the blocks is infinite.
A partition of \(\mathbb{Z}\) that consists of infinitely many blocks, where each of the blocks is finite.
A partition of \(\mathbb{Z}\) that consists of infinitely many blocks, where each of the blocks is infinite.
Problem 7.57.
For each relation in
Problem 7.34, determine whether the corresponding collection of the sets of relatives forms a partition of the given set.
Problem 7.58.
Can we partition the empty set? If so, describe a partition. If not, explain why.
The next theorem spells out half of the close connection between partitions and equivalence relations.
Theorem 7.73 yields the other half.
Theorem 7.59.
If \(\sim\) is an equivalence relation on a set \(A\text{,}\) then \(A/\mathord\sim\) forms a partition of \(A\text{.}\)
Problem 7.60.
In the previous theorem, what is \(A/\mathord\sim\) if \(A\) is the empty set?
Problem 7.61.
Consider the equivalence relation
\begin{equation*}
\sim\ =\{(1,1),(1,2),(2,1), (2,2),(3,3),(4,4),(4,5),(5,4),(5,5),(6,6),(5,6),(6,5),(4,6),(6,4)\}
\end{equation*}
on the set \(A=\{1,2,3,4,5,6\}\text{.}\) Find \(A/\mathord\sim\) and verify that it is a partition.
It turns out that we can reverse the situation, as well. That is, given a partition, we can form an equivalence relation such that the equivalence classes correspond to the blocks of the partition. Before proving this, we need a definition.
Definition 7.62.
Let \(A\) be a set and \(\Omega\) any collection of subsets of \(A\) (not necessarily a partition). Define the relation \(\tcboxmath{R_{\Omega}}\) on \(A\) via \(aR_{\Omega}b\) if there exists \(X\in \Omega\) that contains both \(a\) and \(b\text{.}\) This relation is called the relation on \(A\) associated to \(\Omega\text{.}\)
In other words, two elements are related exactly when they are in the same subset.
Problem 7.63.
Let \(A=\{a,b,c,d,e,f\}\) and let \(\Omega=\{\{a,c\},\{b,c\},\{d,f\}\}\text{.}\) List the ordered pairs in \(R_{\Omega}\) and draw the corresponding digraph.
Problem 7.64.
Let
\(A\) and
\(\Omega\) be as in
Example 7.54. List the ordered pairs in
\(R_{\Omega}\) and draw the corresponding digraph.
Problem 7.65.
Consider
Problem 7.24. Find the relation on
\(A\) associated to
\(\Rel(R)\) and compare with what you obtained for
\(R\) in
Problem 7.24.
Problem 7.66.
Give an example of a set \(A\) and a collection \(\Omega\) from \(\mathcal{P}(A)\) such that the relation \(R_{\Omega}\) is not reflexive.
Problem 7.67.
Let \(A=\{1,2,3,4,5,6\}\) and \(\Omega=\{\{1,3,4\},\{2,4\},\{3,4\},\{6\}\}\text{.}\)
Is \(\Omega\) a partition of \(A\text{?}\)
Find \(R_{\Omega}\) by listing ordered pairs or drawing a digraph.
Is \(R_{\Omega}\) an equivalence relation?
Find \(\Rel(R_\Omega)\) (i.e., the collection of subsets of \(A\) determined by \(R_{\Omega}\)). How are \(\Omega\) and \(\Rel(R_\Omega)\) related?
Theorem 7.68.
If \(\Omega\) is a collection of subsets of a set \(A\) (not necessarily a partition) such that
\begin{equation*}
\bigcup_{X\in\Omega}X=A\text{,}
\end{equation*}
then \(R_{\Omega}\) is reflexive.
Problem 7.69.
In the previous theorem, what is \(R_{\Omega}\) if \(A\) is the empty set?
Theorem 7.70.
If \(\Omega\) is a collection of subsets of a set \(A\) (not necessarily a partition), then \(R_{\Omega}\) is symmetric.
Theorem 7.71.
If \(\Omega\) is a collection of subsets of a set \(A\) (not necessarily a partition) such that the elements of \(\Omega\) are pairwise disjoint, then \(R_{\Omega}\) is transitive.
Problem 7.72.
Let \(A=\{a,b,c\}\text{.}\) If possible, find an example of collection \(\Omega\) of nonempty subsets of \(A\) such that \(R_{\Omega}\) is an equivalence relation on \(A\) but \(\Rel(R_{\Omega})\neq \Omega\text{.}\) If such an example is impossible, explain why.
Recall that
Theorem 7.59 says that the equivalence classes for a relation on a nonempty set
\(A\) determines a partition of
\(A\text{.}\) The following theorem tells us that every partition of a set yields an equivalence relation where the equivalence classes correspond to the blocks of the partition. This result is a consequence of
Theorem 7.68,
Theorem 7.70, and
Theorem 7.71.
Theorem 7.73.
If \(\Omega\) is a partition of a set \(A\text{,}\) then \(R_{\Omega}\) is an equivalence relation.
Together,
Theorem 7.59 and
Theorem 7.73 tell us that equivalence relations and partitions are two different ways of viewing the same thing. When proving the following result, ask yourself whether the statement is true if we remove the condition “
\(a\in\rel(a)\) for all
\(a\in A\text{.}\)”
Theorem 7.74.
If \(R\) is a relation on a set \(A\) such that the collection of the set of relatives with respect to \(R\) is a partition of \(A\) and \(a\in\rel(a)\) for all \(a\in A\text{,}\) then \(R\) is an equivalence relation.
Problem 7.75.
Let \(A=\{\circ, \triangle, \blacktriangle, \square, \blacksquare, \bigstar, \odot, \nabla\}\text{.}\) Make up a partition \(\Omega\) on \(A\) and then draw the digraph corresponding to \(R_{\Omega}\text{.}\)
In the broad light of day mathematicians check their equations and their proofs, leaving no stone unturned in their search for rigour. But, at night, under the full moon, they dream, they float among the stars and wonder at the miracle of the heavens. They are inspired. Without dreams there is no art, no mathematics, no life.
―Michael Atiyah, mathematician
