Mathwords logoReference LibraryMathwords

Partition of a Set

Partition of a Set

A collection of disjoint subsets of a given set. The union of the subsets must equal the entire original set.

For example, one possible partition of {1, 2, 3, 4, 5, 6} is {1, 3}, {2}, {4, 5, 6}.

Key Formula

A collection {A1,A2,…,Ak} is a partition of S if:\text{A collection } \{A_1, A_2, \ldots, A_k\} \text{ is a partition of } S \text{ if:} 1. Ai≠∅ for all i1.\ A_i \neq \emptyset \text{ for all } i 2. Ai∩Aj=∅ for all i≠j2.\ A_i \cap A_j = \emptyset \text{ for all } i \neq j 3. A1∪A2∪⋯∪Ak=S3.\ A_1 \cup A_2 \cup \cdots \cup A_k = S
Where:
  • SS = The original set being partitioned
  • A1,A2,…,AkA_1, A_2, \ldots, A_k = The subsets (blocks or parts) that form the partition
  • ∅\emptyset = The empty set

Worked Example

Problem: Determine whether each of the following collections is a valid partition of S = {1, 2, 3, 4, 5}.
Collection A: Consider {1, 2}, {3, 4}, {5}. Every element of S appears in exactly one subset. No subset is empty. The subsets don't overlap. Their union is the full set.
{1,2}∪{3,4}∪{5}={1,2,3,4,5}=S✓\{1,2\} \cup \{3,4\} \cup \{5\} = \{1,2,3,4,5\} = S \quad \checkmark
Collection B: Consider {1, 2, 3}, {3, 4, 5}. The element 3 appears in both subsets, so these subsets are not disjoint. This violates condition 2.
{1,2,3}∩{3,4,5}={3}≠∅×\{1,2,3\} \cap \{3,4,5\} = \{3\} \neq \emptyset \quad \times
Collection C: Consider {1, 2}, {4, 5}. Although the subsets are non-empty and disjoint, their union is {1, 2, 4, 5}, which misses 3. This violates condition 3.
{1,2}∪{4,5}={1,2,4,5}≠S×\{1,2\} \cup \{4,5\} = \{1,2,4,5\} \neq S \quad \times
Collection D: Consider {1, 2, 3, 4, 5}, ∅. One of the subsets is the empty set. This violates condition 1, so it is not a valid partition.
A2=∅×A_2 = \emptyset \quad \times
Answer: Only Collection A — {1, 2}, {3, 4}, {5} — is a valid partition of S.

Another Example

Problem: List all possible partitions of the set {a, b, c}.
One block: The entire set as a single part.
{{a,b,c}}\{\{a, b, c\}\}
Two blocks (3 ways): Separate one element from the other two. There are three ways to choose which element stands alone.
{{a},{b,c}},{{b},{a,c}},{{c},{a,b}}\{\{a\}, \{b, c\}\}, \quad \{\{b\}, \{a, c\}\}, \quad \{\{c\}, \{a, b\}\}
Three blocks: Each element in its own singleton subset.
{{a},{b},{c}}\{\{a\}, \{b\}, \{c\}\}
Answer: The set {a, b, c} has exactly 5 partitions. The total number of partitions of an n-element set is given by the Bell number B(n); here B(3) = 5.

Frequently Asked Questions

Can the empty set be one of the parts in a partition?
No. Every block in a partition must be non-empty. If you allowed an empty subset, condition 1 of the definition would be violated. Each part must contain at least one element of the original set.
How many partitions does a set with n elements have?
The number of partitions of an n-element set is the Bell number B(n). The first few values are B(1) = 1, B(2) = 2, B(3) = 5, B(4) = 15, and B(5) = 52. Bell numbers grow rapidly and have no simple closed-form formula, but they can be computed using the Bell triangle.

Partition of a set vs. Subset of a set

A subset is any collection of elements chosen from a set — it can overlap with other subsets and need not cover the whole set. A partition is a specific collection of subsets that together cover the entire set with no overlaps. Every block of a partition is a subset, but an arbitrary group of subsets is not necessarily a partition.

Why It Matters

Partitions appear throughout mathematics. In probability, partitioning a sample space into mutually exclusive events lets you apply the law of total probability. In equivalence relations, every equivalence relation on a set produces a unique partition (the equivalence classes), and every partition defines an equivalence relation — this correspondence is one of the most important ideas in abstract algebra and discrete mathematics.

Common Mistakes

Mistake: Including overlapping subsets and calling them a partition.
Correction: The subsets in a partition must be pairwise disjoint — no element can appear in more than one block. If two subsets share any element, the collection is not a partition.
Mistake: Leaving out elements of the original set.
Correction: The union of all blocks must equal the entire original set. Every element must be accounted for in exactly one block. A collection of subsets that misses even one element is not a partition.

Related Terms