partitions form a lattice

Let $S$ be a set. Let $\mathrm{Part}(S)$ be the set of all partitions on $S$. Since each partition is a cover of $S$, $\mathrm{Part}(S)$ is partially ordered by covering refinement relation, so that $P_1⪯P_2$ if for every $a\in P_1$, there is a $b\in P_2$ such that $a\subseteq b$. We say that a partition $P$ is finer than a partition $Q$ if $P⪯Q$, and coarser than $Q$ if $Q⪯P$.

Proposition 1.

$\mathrm{Part}(S)$ is a complete lattice

Proof.

For any set $𝒫$ of partitions $P_i$ of $S$, the intersection $\bigcap 𝒫$ is a partition of $S$. Take the meet of $P_i$ to be this intersection. Next, let $𝒬$ be the set of those partitions of $S$ such that each $Q\in 𝒬$ is coarser than each $P_i$. This set is non-empty because $S\times S\in 𝒬$. Take the meet $P^{\prime }$ of all these partitions which is again coarser than all partitions $P_i$. Define the join of $P_i$ to be $P^{\prime }$ and the proof is complete.∎

Remarks.

• The top element of $\mathrm{Part}(S)$ is $S\times S$ and the bottom is the diagonal relation on $S$.

• Correspondingly, the partition lattice of $S$ also defines the lattice of equivalence relations $\mathrm{\Delta }$ on $S$.

• Given a family $\{E_i\mid i\in I\}$ of equvialence relations on $S$, we can explicitly describe the join $E:=\bigvee E_i$ of $E_i$, as follows: $a\equiv b(modE)$ iff there is a finite sequence $a=c_1,\mathrm{\dots },c_n=b$ such that

  $c_k\equiv c_{k+1}(mod{E}_{i(k)})\mathit{\hspace{1em}\hspace{1em}}\text{ for }k=1,\mathrm{\dots },n-1.$(1)

  It is easy to see this definition makes $E$ an equivalence relation. To see that $E$ is the supremum of the $E_i$, first note that each $E_i\le E$. Suppose now $F$ is an equivalence relation on $S$ such that $E_i\le F$ and $a\equiv b(modE)$. Then we get a finite sequence $c_k$ as described by (1) above, so $c_k\equiv c_{k+1}(modF)$ for each $k\in \{1,\mathrm{\dots },n-1\}$. Hence $a\equiv b(modF)$ also.