7.6: Partitions

It often happens that someone divides up a set into several disjoint subsets. This is called a “partition” of the set.

Figure \(7A\). A partition of \(A\) into subsets \(A_{1}, \ldots, A_{5}\). (Each element of \(A\) is in one and only one of the subsets.)

Example \(7.6.1\).

Mary is leaving for university, and does not want her childhood toys any more, so she will divide them up among her younger siblings: Alice, Bob, and Cindy. Let

• \(T\) be the set of all of Mary’s toys, and
• \(A\), \(B\), and \(C\) be the set of toys that she will give to Alice, to Bob, and to Cindy, respectively.

Then

Solution

\(A\), \(B\), and \(C\) are subsets of \(T\), and they should be chosen so that:

1. the union of \(A\), \(B\) and \(C\) is \(T\) (that is, \(A \cup B \cup C=T\)), so all of the toys are given away, and
2. the sets \(A\), \(B\), and \(C\) are pairwise disjoint (that is, \(A \cap B=\varnothing\), \(A \cap C=\varnothing\), and \(B \cap C=\varnothing\)), so there will not be any confusion about who is the new owner of each toy.

Thus, we see that Mary should partition T into three disjoint subsets.

Definition \(7.6.2\).

A partition of a set \(A\) is a collection of nonempty subsets of \(A\), such that each element of \(A\) is in exactly one of the subsets. In other words:

1. the union of the subsets in the collection is all of \(A\), and
2. the subsets in the collection are pairwise disjoint.

Example \(7.6.3\).

In Example \(7.6.1\), the collection \(\{A, B, C\}\) is a partition of \(T\).*

Example \(7.6.4\).

In Example \(7.3.3\), the equivalence classes are \(\{1, 3, 4\}\) and \(\{2, 5\}\). Since 1, 2, 3, 4, 5 each belong to exactly one of these sets, we see that the set \[\{\{1,3,4\},\{2,5\}\}\]

of equivalence classes is a partition of \(\{1, 2, 3, 4, 5\}\).

The following result is an immediate consequence of Theorem \(7.3.5\). It says that equivalence classes always provide a partition.

Corollary \(7.6.5\).

Suppose \(\sim\) is an equivalence relation on a set \(A\). Then \[\{[a] \mid a \in A\}\]

is a partition of \(A\).

Proof

From parts (2), (3), and (5) of Theorem \(7.3.5\), we know that the equivalence classes are nonempty, that their union is A, and that they are pairwise disjoint.

Remark \(7.6.6\).

Corollary \(7.6.5\) tells us that every equivalence relation gives us a partition. Conversely, the following result shows that any partition comes from an equivalence relation. Thus, equivalence relations and partitions are just two different ways of looking at the same thing.

Exercise \(7.6.7\).

Suppose \(\mathcal{P}\) is a partition of a set \(A\). Define a binary relation \(\sim\) on \(A\) by \[a \sim b \quad \text { iff } \quad \exists C \in \mathcal{P},(a \in C \text { and } b \in C) \text {. }\]

Show that:

1. \(\sim\) is an equivalence relation on \(A\), and
2. the set of equivalence classes is the partition \(\mathcal{P}\).

Recall that \(\mathbb{Z}_{n}\) replaces integers \(a\) and \(b\) that are congruent modulo \(n\) with objects \(\bar{a}\) and \(\bar{b}\) that are exactly equal to each other. This was achieved by letting \(\mathbb{Z}_{n}\) be the set of all equivalence classes. The set \(\mathbb{Z}_{n}\) applies only to congruence modulo \(n\), but the same thing can be done for any equivalence relation:

Definition \(7.6.8.\)

Suppose \(\sim\) is an equivalence relation on a set \(A\). The set of all equivalence classes is called A modulo \(\sim\). It is denoted \(A / \sim\).

Example \(7.6.9\).

Suppose we define an equivalence relation \(\sim\) on \(\mathbb{Z}\) by \(a \sim b\) iff \(a \equiv b(\bmod n)\). Then

Solution

\(\mathbb{Z} / \sim\) is simply another name for \(\mathbb{Z}_{n}\).

__________________
*Actually, this may not be correct, because, for a partition, we require the sets \(A\), \(B\), and \(C\) to be nonempty, but it is possible that one (or more) of Mary’s siblings will not be given any toys.