Partition of a set

In mathematics, a partition of a set is a way to group its elements into non‑empty subsets so that each element belongs to exactly one of those subsets. Every equivalence relation on a set gives rise to a partition, and every partition defines an equivalence relation. A set together with an equivalence relation or a partition is sometimes called a setoid, especially in type theory and proof theory.

A partition of a set X is a collection of non‑empty subsets of X with three properties: none of the subsets is the empty set; the union of all the subsets equals X (so the subsets cover X); and any two distinct subsets have an empty intersection (they are pairwise disjoint). The subsets in a partition are called blocks, parts, or cells. If a belongs to X, the cell containing a is often written [a].

Every partition can be identified with an equivalence relation on X: two elements are equivalent exactly when they lie in the same block. Conversely, any equivalence relation yields a partition formed by its equivalence classes. Because of this, it is sometimes said informally that an equivalence relation is the same as a partition.

For the empty set, there is exactly one partition: the empty collection of subsets. For any non‑empty set X, the collection {X} itself is a partition, called the trivial partition.

A singleton set {x} has exactly one partition, namely {{x}}. For any non‑empty proper subset A of a set U, the pair {A, U \ A} forms a partition of U. The set {1, 2, 3} has five partitions: {{1}, {2}, {3}} (written 1|2|3); {{1, 2}, {3}} (12|3); {{1, 3}, {2}} (13|2); {{1}, {2, 3}} (1|23); and {{1, 2, 3}} (123). Some collections are not partitions: one containing the empty set fails; one where an element appears in more than one block fails; and one that omits an element of the set fails to be a partition of that set (though it may be a partition of a smaller set).

Partitions and equivalence relations

The axiom of choice guarantees that for any partition of X there exists a subset of X containing exactly one element from each block. This allows the selection of a canonical representative from each equivalence class.

Refinement of partitions

A partition α is a refinement of a partition ρ (and α is finer than ρ, while ρ is coarser than α) if every block of α is a subset of some block of ρ. This “finer‑than” relation is a partial order on the set of all partitions of X. The set of partitions forms a lattice: the meet of two partitions α and ρ is the partition whose blocks are the non‑empty intersections of a block from α with a block from ρ; the join is formed by taking the union of blocks that are linked through a chain of non‑empty intersections. For a finite set, this lattice is geometric and supersolvable.

The partition lattice of a 4‑element set has 15 elements. The atoms of this lattice—partitions with one two‑element block and the rest singletons—correspond one‑for‑one with the edges of a complete graph. The matroid closure of a set of these atomic partitions is the finest common coarsening of them.