Partition of a set

In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset.

Every equivalence relation on a set defines a partition of this set, and every partition defines an equivalence relation. A set equipped with an equivalence relation or a partition is sometimes called a setoid, typically in type theory and proof theory.

A partition of a set X is a set of non-empty subsets of X such that every element x in X is in exactly one of these subsets (i.e., the subsets are nonempty mutually disjoint sets).

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

The sets in ${\displaystyle P}$ are called the blocks, parts, or cells, of the partition. If ${\displaystyle a\in X}$ then we represent the cell containing ${\displaystyle a}$ by ${\displaystyle [a]}$. That is to say, ${\displaystyle [a]}$ is notation for the cell in ${\displaystyle P}$ which contains ${\displaystyle a}$.

Every partition ${\displaystyle P}$ may be identified with an equivalence relation on ${\displaystyle X}$, namely the relation ${\displaystyle \sim _{\!P}}$ such that for any ${\displaystyle a,b\in X}$ we have ${\displaystyle a\sim _{\!P}b}$ if and only if ${\displaystyle a\in [b]}$ (equivalently, if and only if ${\displaystyle b\in [a]}$). The notation ${\displaystyle \sim _{\!P}}$ evokes the idea that the equivalence relation may be constructed from the partition. Conversely every equivalence relation may be identified with a partition. This is why it is sometimes said informally that "an equivalence relation is the same as a partition". If P is the partition identified with a given equivalence relation ${\displaystyle \sim }$, then some authors write ${\displaystyle P=X/{\sim }}$. This notation is suggestive of the idea that the partition is the set X divided into cells. The notation also evokes the idea that, from the equivalence relation one may construct the partition.

The rank of ${\displaystyle P}$ is ${\displaystyle |X|-|P|}$, if ${\displaystyle 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.