Breaking a Set into Blocks
In “Equivalence Classes,” an equivalence relation was used to group elements that are related to one another. The equivalence classes cover the underlying set, and any two classes are equal or disjoint. A partition describes exactly this arrangement in terms of sets: it is a collection of blocks that covers a set, with no element left out and no element placed in two distinct blocks.
Let \(A\) be a set. A collection \(\mathcal P\) of subsets of \(A\) is itself a set whose members are sets. Its members are called blocks. The following definition makes precise what it means for those blocks to divide \(A\).
Definition (Partition). A partition of a set \(A\) is a collection \(\mathcal P\) of subsets of \(A\) satisfying:
- Every block is nonempty: \(P\ne\varnothing\) for every \(P\in\mathcal P\).
- The blocks cover \(A\): \(\displaystyle \bigcup_{P\in\mathcal P}P=A\).
- Distinct blocks are disjoint: if \(P,Q\in\mathcal P\) and \(P\ne Q\), then \(P\cap Q=\varnothing\).
The word “distinct” in the third condition matters. A collection is a set, so it cannot contain the same block twice. The condition says that two different blocks have no common element. Together with the covering condition, this means that every element of \(A\) belongs to exactly one block.
Reading the Definition in Practice
The union condition can also be read element by element: for each \(a\in A\), there is at least one block \(P\in\mathcal P\) such that \(a\in P\). The disjointness condition ensures that there is at most one such block. For if \(a\) belonged to two distinct blocks \(P\) and \(Q\), then \(a\in P\cap Q\), contradicting \(P\cap Q=\varnothing\). Thus, every element is assigned to one and only one block.
Worked Example: A Partition of a Five-Element Set
Let \(A=\{a,b,c,d,e\}\), where the five displayed elements are distinct, and let $$ \mathcal P=\bigl\{\{a,c\},\{b,e\},\{d\}\bigr\}. $$ Each block is nonempty and is a subset of \(A\). The union is $$ \{a,c\}\cup\{b,e\}\cup\{d\}=\{a,b,c,d,e\}=A, $$ so the blocks cover \(A\). To check disjointness, the three blocks have no elements in common: \(\{a,c\}\cap\{b,e\}=\varnothing\), \(\{a,c\}\cap\{d\}=\varnothing\), and \(\{b,e\}\cap\{d\}=\varnothing\). Therefore \(\mathcal P\) is a partition of \(A\). For example, \(c\) belongs to the block \(\{a,c\}\), and it belongs to no other block.
Worked Example: A Collection with a Gap
Let \(A=\{1,2,3,4,5,6\}\), and consider $$ \mathcal Q=\bigl\{\{1,2\},\{3,4\}\bigr\}. $$ The two blocks are nonempty and disjoint, but their union is \(\{1,2,3,4\}\), not \(A\). In particular, neither \(5\) nor \(6\) belongs to any block. Thus \(\mathcal Q\) is not a partition of \(A\). It is not enough for the displayed blocks to be mutually disjoint; they must also cover the whole underlying set.
Worked Example: A Collection with an Overlap
Again take \(A=\{1,2,3,4,5,6\}\), but now consider $$ \mathcal R=\bigl\{\{1,2,3\},\{3,4,5,6\}\bigr\}. $$ Both blocks are nonempty subsets of \(A\), and their union is \(A\). However, the blocks are distinct and $$ \{1,2,3\}\cap\{3,4,5,6\}=\{3\}\ne\varnothing. $$ Element \(3\) belongs to both blocks, so the disjointness requirement fails. Consequently, \(\mathcal R\) is not a partition of \(A\), even though it covers \(A\).
Equivalence Classes Form a Partition
The result that equivalence classes are equal or disjoint is the key fact that turns them into the blocks of a partition. The classes also cover the set because every element is equivalent to itself. In the following theorem, \(\{[a]:a\in A\}\) means the collection of all classes, not a list that keeps repeated copies when different representatives give the same class.
Theorem (Equivalence Classes Form a Partition). Let \(\sim\) be an equivalence relation on a set \(A\). Then the collection $$ \mathcal P_{\sim}=\{[a]:a\in A\} $$ is a partition of \(A\).
Proof. We verify the three conditions in the definition of a partition. First, let \([a]\in\mathcal P_{\sim}\). Then \(a\in A\), and reflexivity gives \(a\sim a\). By the definition of an equivalence class, \(a\in[a]\). Thus \([a]\ne\varnothing\), so every member of \(\mathcal P_{\sim}\) is nonempty.
Next, each class \([a]\) is a subset of \(A\) by its definition. Hence \(\bigcup_{a\in A}[a]\subseteq A\). For the reverse inclusion, let \(x\in A\). Reflexivity gives \(x\sim x\), so \(x\in[x]\). Since \(x\in A\), the class \([x]\) belongs to \(\mathcal P_{\sim}\), and therefore \(x\in\bigcup_{a\in A}[a]\). This proves that the classes cover \(A\).
Finally, take two distinct members \([a]\) and \([b]\) of \(\mathcal P_{\sim}\). The theorem “Equivalent Classes Are Equal or Disjoint” says that either \([a]=[b]\) or \([a]\cap[b]=\varnothing\). Since the classes under consideration are distinct, the equality alternative is false. It follows that \([a]\cap[b]=\varnothing\). Thus distinct classes are disjoint, and all three requirements hold. Therefore \(\mathcal P_{\sim}\) is a partition of \(A\). \(\square\)
The proof uses the earlier theorem about classes rather than repeating its proof. The roles of the equivalence relation’s properties are visible in the established facts: reflexivity ensures each class is nonempty and that the classes cover \(A\), while symmetry and transitivity were used in proving that classes are equal or disjoint.
A Partition Defines an Equivalence Relation
The connection goes in the other direction too. Suppose a partition is already given. Two elements can be declared equivalent when they belong to the same block. This rule is meaningful because every element belongs to exactly one block. The resulting relation groups elements according to the blocks of the partition.
Theorem (A Partition Determines an Equivalence Relation). Let \(\mathcal P\) be a partition of \(A\). For \(x,y\in A\), define $$ x\sim_{\mathcal P}y \quad\Longleftrightarrow\quad \text{there exists }P\in\mathcal P\text{ such that }x\in P\text{ and }y\in P. $$ Then \(\sim_{\mathcal P}\) is an equivalence relation on \(A\).
Proof. We check reflexivity, symmetry, and transitivity. Let \(x\in A\). Since the blocks cover \(A\), there is a \(P\in\mathcal P\) with \(x\in P\). Thus \(x\) and \(x\) belong to the same block, so \(x\sim_{\mathcal P}x\). This proves reflexivity.
Now let \(x,y\in A\) and suppose \(x\sim_{\mathcal P}y\). By definition, there is a block \(P\in\mathcal P\) such that \(x\in P\) and \(y\in P\). The same block contains \(y\) and \(x\), so \(y\sim_{\mathcal P}x\). This proves symmetry.
Finally, let \(x,y,z\in A\) and suppose \(x\sim_{\mathcal P}y\) and \(y\sim_{\mathcal P}z\). There are blocks \(P,Q\in\mathcal P\) such that \(x,y\in P\) and \(y,z\in Q\). In particular, \(y\in P\cap Q\), so this intersection is nonempty. By the partition’s disjointness condition, two blocks with nonempty intersection cannot be distinct; hence \(P=Q\). Since \(x\in P\) and \(z\in Q=P\), both \(x\) and \(z\) belong to the same block. Therefore \(x\sim_{\mathcal P}z\), proving transitivity. The relation is reflexive, symmetric, and transitive, so it is an equivalence relation. \(\square\)
Worked Example: Grouping Positive Integers by Divisibility by \(3\)
Let \(\mathbb Z_{>0}\) be the set of positive integers. Define $$ M=\{3k:k\in\mathbb Z_{>0}\}, \qquad N=\{n\in\mathbb Z_{>0}:n\text{ is not divisible by }3\}. $$ Both sets are nonempty: \(3\in M\) and \(1\in N\). Every positive integer is either divisible by \(3\) or not divisible by \(3\), so \(M\cup N=\mathbb Z_{>0}\). No integer can both be divisible and not divisible by \(3\), so \(M\cap N=\varnothing\). Consequently \(\{M,N\}\) is a partition of \(\mathbb Z_{>0}\). The relation of belonging to the same block is an equivalence relation: two positive integers are related exactly when either both are divisible by \(3\), or both are not divisible by \(3\). For instance, \(6\) and \(12\) are related because they both lie in \(M\), while \(6\) and \(8\) are not related because \(6\in M\) and \(8\in N\).
The Exact Link Between Blocks and Classes
The two constructions recover one another. Starting with a partition and defining the relation of “belonging to the same block,” the equivalence class of an element is exactly the unique block that contains it. To see why, let \(a\in A\), and let \(P\) be its unique block. If \(x\in[a]\), then \(x\sim_{\mathcal P}a\), so \(x\) and \(a\) lie in some common block \(Q\). Since \(a\in P\cap Q\), the partition condition forces \(P=Q\), and hence \(x\in P\). Conversely, if \(x\in P\), then \(x\) and \(a\) belong to \(P\), so \(x\sim_{\mathcal P}a\) and \(x\in[a]\). Therefore \([a]=P\).
This correspondence gives two ways to describe the same grouping. A partition names the blocks directly. An equivalence relation specifies which pairs of elements count as equivalent, and its classes become the blocks. The choice of description depends on the task: if the blocks are easy to list, a partition may be simplest; if a rule relating pairs of elements is natural, an equivalence relation may be more convenient.
| Starting point | Construction | What results |
|---|---|---|
| Equivalence relation on \(A\) | Collect all elements equivalent to each representative | A partition into equivalence classes |
| Partition of \(A\) | Relate elements that lie in the same block | An equivalence relation on \(A\) |
Check Your Understanding
- State the three requirements for a collection \(\mathcal P\) to be a partition of \(A\).
- A collection of nonempty, disjoint subsets of \(A\) leaves one element of \(A\) uncovered. Which partition requirement fails?
- Why do the equivalence classes of an equivalence relation cover the underlying set?
- In the proof that a partition defines a transitive relation, why must the blocks \(P\) and \(Q\) be equal when they both contain \(y\)?
- For a partition \(\mathcal P\), how are \(x\) and \(y\) related under \(\sim_{\mathcal P}\)?