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.

are called the blocks, parts, or cells, of the partition.

evokes the idea that the equivalence relation may be constructed from the partition.

Conversely every equivalence relation may be identified with a partition.

This notation is suggestive of the idea that the partition is the set X divided in to cells.

The notation also evokes the idea that, from the equivalence relation one may construct the partition.

[5] 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.

Informally, this means that α is a further fragmentation of ρ.

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 (their "join") and a greatest lower bound (their "meet"), so that it forms a lattice, and more specifically (for partitions of a finite set) it is a geometric and supersolvable lattice.

[6][7] The partition lattice of a 4-element set has 15 elements and is depicted in the Hasse diagram on the left.

The meet and join of partitions α and ρ are defined as follows.

Based on the equivalence between geometric lattices and matroids, this lattice of partitions of a finite set corresponds to a matroid in which the base set of the matroid consists of the atoms of the lattice, namely, the partitions with

These atomic partitions correspond one-for-one with the edges of a complete graph.

The matroid closure of a set of atomic partitions is the finest common coarsening of them all; in graph-theoretic terms, it is the partition of the vertices of the complete graph into the connected components of the subgraph formed by the given set of edges.

Another example illustrates refinement of partitions from the perspective of equivalence relations.

The 2-part partition corresponding to ~C has a refinement that yields the same-suit-as relation ~S, which has the four equivalence classes {spades}, {diamonds}, {hearts}, and {clubs}.

A partition of the set N = {1, 2, ..., n} with corresponding equivalence relation ~ is noncrossing if it has the following property: If four elements a, b, c and d of N having a < b < c < d satisfy a ~ c and b ~ d, then a ~ b ~ c ~ d. The name comes from the following equivalent definition: Imagine the elements 1, 2, ..., n of N drawn as the n vertices of a regular n-gon (in counterclockwise order).

The noncrossing partition lattice has taken on importance because of its role in free probability theory.

Bell numbers satisfy the recursion and have the exponential generating function The Bell numbers may also be computed using the Bell triangle in which the first value in each row is copied from the end of the previous row, and subsequent values are computed by adding two numbers, the number to the left and the number to the above left of the position.

The Bell numbers are repeated along both sides of this triangle.

The numbers within the triangle count partitions in which a given element is the largest singleton.