Partition (set theory)

In mathematics, a partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in one and only one of the subsets.

A partition of a set X is a set of nonempty subsets of X such that every element x in X is in exactly one of these subsets (i.e., X is a disjoint union of the subsets).

Equivalently, a family of sets P is a partition of X if and only if all of the following conditions hold:

The sets in P are called the blocks, parts or cells of the partition.

The rank of P is |X| − |P|, if X is finite.

For any equivalence relation on a set X, the set of its equivalence classes is a partition of X. Conversely, from any partition P of X, we can define an equivalence relation on X by setting x ~ y precisely when x and y are in the same part in P. Thus the notions of equivalence relation and partition are essentially equivalent.

The axiom of choice guarantees for any partition of a set X the existence of a subset of X containing exactly one element from each part of the partition. This implies that given an equivalence relation on a set one can select a canonical representative element from every equivalence class.

A partition α of a set X is a refinement of a partition ρ of X—and we say that α is finer than ρ and that ρ is coarser than α—if every element of α is a subset of some element of ρ. Informally, this means that α is a further fragmentation of ρ. In that case, it is written that α ≤ ρ.

This finer-than relation on the set of partitions of X is a partial order (so the notation "≤" is appropriate). Each set of elements has a least upper bound and a greatest lower bound, so that it forms a lattice, and more specifically (for partitions of a finite set) it is a geometric lattice. The partition lattice of a 4-element set has 15 elements and is depicted in the Hasse diagram on the left.

...
Wikipedia