Partition of a set
A partition groups elements into disjoint, non-empty subsets.
Wikipedia / Wikimedia Commons
A partition of a set splits its elements into groups, called blocks, parts, or cells. Each group must be non-empty, and every element of the original set must belong to exactly one group. More formally, a collection of subsets forms a partition if it contains no empty set, the union of all subsets equals the whole set, and any two distinct subsets have no elements in common. If an element \(a\) belongs to the set, the block containing it is often written as \([a]\).
Every partition corresponds to an equivalence relation, and vice versa. Given a partition, two elements are considered equivalent if they fall in the same block. Given an equivalence relation, its equivalence classes naturally form a partition. Because of this close link, the two concepts are often treated as interchangeable, and a set paired with either structure is sometimes called a setoid, especially in type theory and proof theory.
For example, the empty set has exactly one partition: the empty collection of subsets. Any non-empty set has at least the trivial partition consisting of the whole set itself. A singleton set has only that one partition. For a set with a proper non-empty subset, that subset and its complement together form a partition. The set \(\{1,2,3\}\) has five distinct partitions, such as \(\{\{1\},\{2\},\{3\}\}\) or \(\{\{1,2\},\{3\}\}\). Collections like \(\{\{1,2\},\{2,3\}\}\) fail as partitions because an element appears in more than one block, and \(\{\{1\},\{2\}\}\) fails for \(\{1,2,3\}\) because 3 is missing, though it is a valid partition of \(\{1,2\}\). The axiom of choice ensures that for any partition, there exists a subset containing exactly one element from each block.
- definition
- A set of non-empty subsets of X that are pairwise disjoint and whose union is X
- conditions
- No empty set; union equals X; pairwise disjoint
- blocks_called
- blocks, parts, or cells
- notation_for_cell
- [a] denotes the cell containing element a
- relation_to_equivalence
- Each partition corresponds to an equivalence relation and vice versa
- trivial_partition
- For any non-empty X, P = {X} is the trivial partition
- empty_set_partition
- The empty set has exactly one partition, namely ∅
Lore & Background
A partition of a set X is defined as a family P of non-empty subsets of X such that every element of X belongs to exactly one subset. The subsets are called blocks, parts, or cells. The notation [a] represents the cell containing element a. The family P must not contain the empty set, the union of all blocks must equal X, and any two distinct blocks must be disjoint. For example, the set {1, 2, 3} has five partitions, including { {1}, {2}, {3} } and { {1, 2, 3} }. Non-examples include families containing the empty set or overlapping blocks.
Reader's Guide
The concept of a partition is fundamental in mathematics because it is equivalent to an equivalence relation. Every equivalence relation on a set yields a partition of that set into its equivalence classes, and conversely, any partition defines an equivalence relation where two elements are related if they belong to the same block. This duality is central to many areas, including algebra, combinatorics, and logic. The set of all partitions of a given set forms a lattice under the refinement order, where one partition is finer than another if every block of the finer is a subset of a block of the coarser. This lattice is geometric and supersolvable for finite sets, and it corresponds to the lattice of flats of the graphic matroid of the complete graph. The axiom of choice guarantees the existence of a set of representatives, one from each block. The notion of a setoid in type theory and proof theory formalizes a set equipped with an equivalence relation or partition.
Did You Know?
- The empty set has exactly one partition, namely the empty set itself.
- A partition of a set is sometimes called a setoid in type theory and proof theory.
- The set {1, 2, 3} has exactly five distinct partitions.
- The meet of two partitions is formed by taking non-empty intersections of their blocks.
Frequently Asked Questions
Who is Partition of a set?
A partition is a collection of non-empty, mutually disjoint subsets of a given set X whose union recovers all of X. In plain terms, it carves X into groups—called blocks, parts, or cells—so that every element lands in exactly one group.
What are Partition of a set's powers and role?
Its core ability is grouping: it assigns each element of X to a unique cell, often written [a] for the block containing element a. It must obey three rules simultaneously—no empty cell, full coverage of X, and zero overlap between any two distinct cells.
How does Partition of a set connect to Equivalence Relation?
There is a perfect one-to-one correspondence: every partition of X defines an equivalence relation (two elements are equivalent exactly when they share a cell), and every equivalence relation on X yields a unique partition. Fans often treat them as two faces of the same underlying object.
Why is Partition of a set important in the canon?
It underpins quotient constructions, combinatorial counting (Bell numbers enumerate partitions of an n-element set), and the formalization of 'sameness' via equivalence. Without it, structures like quotient sets and lattice theory lose their natural starting point.
What is Partition of a set's simplest form?
For any non-empty set X, the trivial partition P = {X} places every element into a single block. It is the minimal partition with exactly one cell and corresponds to the universal equivalence relation.
More in Set Theory & Logic 1-19
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record