Partition (Mathematics)

Definition

Given a set $X$, a partition of $X$ is a set $C\subseteq \mathcal{P}X$ of non-empty subsets of $X$ such that:

• Disjointness: $\forall P,Q\in C.P=Q\vee P\cap Q=\varnothing$
• Covering: $\bigcup C=X$

The elements of $C$ are called the parts or blocks of the partition. Equivalently, $C$ is a partition of $X$ iff every $x\in X$ belongs to exactly one $P\in C$.

Relationship to Equivalence Relations

Partitions and equivalence relations on a set $X$ are in bijective correspondence.

Given a partition $C$ of $X$, define a relation ${\sim }_C$ on $X$ by $x{\sim }_{C}y⟺\exists P\in C.x\in P\wedge y\in P.$ This is an equivalence relation, and the blocks of $C$ are precisely its equivalence classes.

Conversely, given an equivalence relation $\sim$ on $X$, the set of equivalence classes $X/\sim =\{[x{]}_{\sim }\mid x\in X\}$ forms a partition of $X$, where $[x{]}_{\sim }=\{y\in X\mid x\sim y\}$.

These two constructions are mutually inverse, establishing a bijection between partitions of $X$ and equivalence relations on $X$.

Examples

• The trivial partition $\{X\}$ corresponds to the total relation $x\sim y$ for all $x,y$.
• The discrete partition $\{\{x\}\mid x\in X\}$ corresponds to the identity relation $x\sim y⟺x=y$.
• For $X=\mathbb{Z}$, congruence modulo $n$ partitions $\mathbb{Z}$ into $n$ residue classes.

Properties

• The set of all partitions of $X$ is partially ordered by refinement: $C\le C^{\prime }$ if every block of $C$ is contained in some block of $C^{\prime }$. Under this order, the discrete partition is the minimum and the trivial partition is the maximum.
• The quotient $X/\sim$ is the canonical partition associated to an equivalence relation $\sim$.

Related Concepts

• Equivalence Relation
• Quotient
• Set
• Subset

References

birkhoff1973-lattice-theory