Partitions of a Set
You'll learn: How partitions divide a set into non-overlapping pieces that together form the whole set.
The Core Idea
A partition of a set is a way of breaking it into smaller, non-empty subsets such that:
- Every element belongs to exactly one subset (the subsets are disjoint)
- The union of all subsets gives back the original set (they're exhaustive)
Think of it like slicing a pizza: every slice is separate (no overlap), every part of the pizza belongs to exactly one slice, and together all the slices make the complete pizza.
Formal Definition
Let A be a set. A collection of subsets {A₁, A₂, ..., Aₙ} is a partition of A if:
- Each
Aᵢis non-empty Aᵢ ∩ Aⱼ = ∅for alli ≠ j(pairwise disjoint)A₁ ∪ A₂ ∪ ... ∪ Aₙ = A(union equals the whole set)
Example
Let A = {1, 2, 3, 4}.
Valid partition: {{1, 2}, {3}, {4}}
- Disjoint? ✓ No element appears in multiple subsets
- Exhaustive? ✓ Union gives {1, 2, 3, 4}
Not a partition: {{1, 2}, {2, 3}, {4}}
- Element 2 appears in two subsets (not disjoint!)
Connection to Equivalence Relations
Here's the beautiful link: every equivalence relation creates a partition (via equivalence classes), and every partition defines an equivalence relation (by saying elements are related if they're in the same subset). This deep connection makes partitions fundamental to understanding structure in discrete mathematics.
Key Takeaway: A partition divides a set into non-empty, disjoint subsets whose union recovers the entire original set—it's a complete, non-overlapping way to organize elements.