---
tag: 9RP82GD0Q4
kind: example
name: Lattice of partitions
msc: [06B05, 05A18]
instance_of: [WH4SFAACAS, VDF7CGPC0P]
uses: [08QMKTWF9T, 0SPZ1H3N9V, 0TKP3TDD02, JQ6FJH2TP8]
sources:
  - url: https://en.wikipedia.org/wiki/Partition_of_a_set
---

## Example

Let $n \ge 1$ and let $\Pi_n$ be the set of all [[partitions|08QMKTWF9T]] of $\set{1, \ldots, n}$.
Order $\Pi_n$ by [[refinement|0SPZ1H3N9V]]: $\sigma \le \tau$ when each block of $\sigma$ lies inside some block of $\tau$.
This is a partial order, and $\Pi_n$ is a [[lattice|WH4SFAACAS]].
The meet $\sigma \wedge \tau$ has as blocks the nonempty intersections $B \cap C$ of a block $B$ of $\sigma$ and a block $C$ of $\tau$.
The join $\sigma \vee \tau$ is the finest partition coarser than both.
In it, two points share a block when a chain of blocks of $\sigma$ and $\tau$, each meeting the next, connects them.
The least element is the partition into singletons, and the greatest element is the partition with one block.
The number of elements of $\Pi_n$ is the [[Bell number|0TKP3TDD02]] $B_n$.

Check for $n = 3$.
The five partitions are $1|2|3$, $12|3$, $13|2$, $23|1$ and $123$.
The three partitions with one pair lie strictly between the bottom and the top, and no two of them are comparable.
The meet of any two of them is $1|2|3$ and their join is $123$, so $\Pi_3$ is the [[diamond lattice|JQ6FJH2TP8]] $M_3$.

## Remarks

The lattice $\Pi_n$ is graded: the rank of a partition with $k$ blocks is $n - k$.
It is a [[geometric lattice|VDF7CGPC0P]], but for $n \ge 3$ it is not distributive, since it contains $M_3$.
The Möbius function of $\Pi_n$ from the bottom to the top equals $(-1)^{n-1} (n-1)!$.

## Explanations

### L1 human

Think of ways to split a group of $n$ people into teams.
One splitting is below another when you get the second by merging some teams of the first.
Any two splittings have a best common refinement and a coarsest common merge, so the splittings form a lattice.
For three people there are five splittings, and the three ways to form one pair sit side by side in the middle.