7.3: Partitions

Theorems 7.42 and 7.43 imply that if \(\sim\) is an equivalence relation on a set \(A\), then \(\sim\) breaks \(A\) up into pairwise disjoint “chunks", where each chunk is some \([a]\) for \(a\in A\). 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:

1. Each \(X\in \Omega\) is nonempty,
2. For all \(X,Y\in\Omega\), \(X\cap Y=\emptyset\) when \(X\neq Y\), and
3. \(\displaystyle \bigcup_{X\in\Omega}X=A\).

That is, the elements of \(\Omega\) are pairwise disjoint nonempty sets and their union is all of \(A\). 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\). That is, \(P/\mathord\sim\) is a partition of \(P\), 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.

1. Democrat, Republican, Independent, Green Party, Libertarian, etc. (set of registered voters)
2. Freshman, sophomore, junior, senior (set of high school students)
3. Evens, odds (set of integers)
4. 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\}\}\). Since the elements of \(\Omega\) are pairwise disjoint nonempty subsets of \(A\) such that their union is all of \(A\), \(\Omega\) is a partition of \(A\) consisting of three blocks.

Problem 7.55. Consider the set \(A\) from Example 7.54.

1. Find a partition of \(A\) consisting of four blocks.
2. 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.

1. A partition of \(\mathbb{Z}\) that consists of finitely many blocks, where each of the blocks is infinite.
2. A partition of \(\mathbb{Z}\) that consists of infinitely many blocks, where each of the blocks is finite.
3. 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.

Problem 7.59. If \(\sim\) is an equivalence relation on a nonempty set \(A\), then \(A/\mathord\sim\) forms a partition of \(A\).

Problem 7.60. In the previous theorem, why did we require \(A\) to be nonempty?

Problem 7.61. Consider the equivalence relation \[\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)\}\] on the set \(A=\{1,2,3,4,5,6\}\). Find the partition determined by \(Rel(\sim)\).

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 \(R_{\Omega}\) on \(A\) via \(aR_{\Omega}b\) if there exists \(X\in \Omega\) that contains both \(a\) and \(b\). This relation is called the relation on \(A\) associated to \(\Omega\).

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

1. Is \(\Omega\) a partition of \(A\)?
2. Find \(R_{\Omega}\) by listing ordered pairs or drawing a digraph.
3. Is \(R_{\Omega}\) an equivalence relation?
4. 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 nonempty set \(A\) (not necessarily a partition) such that \[\bigcup_{X\in\Omega}X=A,\] then \(R_{\Omega}\) is reflexive.

Problem 7.69. Is it necessary to require \(A\) to be nonempty in Theorem 7.68?

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. Why didn’t we require \(A\) to be nonempty in Theorems 7.70 and 7.71?

Recall that Theorem 7.59 says that the equivalence classes for a relation on a nonempty set \(A\) determines a partition of \(A\). 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 Theorems 7.68, 7.70, and 7.71.

Theorem 7.73. If \(\Omega\) is a partition of a set \(A\), then \(R_{\Omega}\) is an equivalence relation.

Together, Theorems 7.59 and 7.73 tell us that equivalence relations and partitions are two different ways of viewing the same thing.

Corollary 7.74. If \(R\) is a relation on a nonempty set \(A\) such that the collection of the set of relatives with respect to \(R\) is a partition of \(A\), then \(R\) is an equivalence relation.

Problem 7.75. Let \(A=\{\circ, \triangle, \blacktriangle, \square, \blacksquare, \bigstar \}\). Make up a partition \(\Omega\) on \(A\) and then draw the digraph corresponding to \(R_{\Omega}\).