Editing Partition of a set (section)

== Refinement of partitions ==
[[File:Set partitions 4; Hasse; circles.svg|thumb|left|300px|Partitions of a 4-element set ordered by refinement]]
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 [[partially ordered set|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 (order)|lattice]], and more specifically (for partitions of a finite set) it is a [[geometric lattice|geometric]] and [[supersolvable lattice|supersolvable]] lattice.<ref>{{citation|title=Lattice Theory|volume=25|series=Colloquium Publications|publisher=American Mathematical Society|first=Garrett|last=Birkhoff|author-link=Garrett Birkhoff|edition=3rd|year=1995|isbn=9780821810255|page=95|url=https://books.google.com/books?id=0Y8d-MdtVwkC&pg=PA95}}.</ref><ref>*{{citation | last=Stern | first=Manfred | title=Semimodular Lattices. Theory and Applications | publisher=Cambridge University Press | year=1999 | volume=73 | series=Encyclopedia of Mathematics and its Applications | doi=10.1017/CBO9780511665578 | isbn=0-521-46105-7}}</ref> 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.  The '''meet''' <math>\alpha \wedge \rho</math> is the partition whose blocks are the intersections of a block of ''α'' and a block of ''ρ'', except for the empty set.  In other words, a block of <math>\alpha \wedge \rho</math> is the intersection of a block of ''α'' and a block of ''ρ'' that are not disjoint from each other.  To define the '''join''' <math>\alpha \vee \rho</math>, form a relation on the blocks ''A'' of ''α'' and the blocks ''B'' of ''ρ'' by ''A'' ~ ''B'' if ''A'' and ''B'' are not disjoint. Then <math>\alpha \vee \rho</math> is the partition in which each block ''C'' is the union of a family of blocks connected by this relation.

Based on the equivalence between geometric lattices and [[matroid]]s, this lattice of partitions of a finite set corresponds to a matroid in which the base set of the matroid consists of the [[Atom (order theory)|atoms]] of the lattice, namely, the partitions with <math>n-2</math> singleton sets and one two-element set. These atomic partitions correspond one-for-one with the edges of a [[complete graph]]. The [[Matroid#Closure operators|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 [[Vertex (graph theory)|vertices]] of the complete graph into the [[Connected component (graph theory)|connected components]] of the subgraph formed by the given set of edges. In this way, the lattice of partitions corresponds to the lattice of flats of the [[graphic matroid]] of the complete graph.

Another example illustrates refinement of partitions from the perspective of equivalence relations. If ''D'' is the set of cards in a standard 52-card deck, the ''same-color-as'' relation on ''D'' – which can be denoted ~<sub>C</sub> – has two equivalence classes: the sets {red cards} and {black cards}.  The 2-part partition corresponding to ~<sub>C</sub> has a refinement that yields the ''same-suit-as'' relation ~<sub>S</sub>, which has the four equivalence classes {spades}, {diamonds}, {hearts}, and {clubs}.