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}\u2aaf{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\u2aafQ$, and coarser than $Q$ if $Q\u2aafP$.
Proposition 1.
$\mathrm{Part}(S)$ is a complete lattice^{}
Proof.
For any set $\mathcal{P}$ of partitions ${P}_{i}$ of $S$, the intersection^{} $\bigcap \mathcal{P}$ is a partition of $S$. Take the meet of ${P}_{i}$ to be this intersection. Next, let $\mathcal{Q}$ be the set of those partitions of $S$ such that each $Q\in \mathcal{Q}$ is coarser than each ${P}_{i}$. This set is nonempty because $S\times S\in \mathcal{Q}$. 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\phantom{\rule{veryverythickmathspace}{0ex}}(modE)$ iff there is a finite sequence^{} $a={c}_{1},\mathrm{\dots},{c}_{n}=b$ such that
${c}_{k}\equiv {c}_{k+1}\phantom{\rule{veryverythickmathspace}{0ex}}(mod{E}_{i(k)})\mathit{\hspace{1em}\hspace{1em}}\text{for}k=1,\mathrm{\dots},n1.$ (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\phantom{\rule{veryverythickmathspace}{0ex}}(modE)$. Then we get a finite sequence ${c}_{k}$ as described by (1) above, so ${c}_{k}\equiv {c}_{k+1}\phantom{\rule{veryverythickmathspace}{0ex}}(modF)$ for each $k\in \{1,\mathrm{\dots},n1\}$. Hence $a\equiv b\phantom{\rule{veryverythickmathspace}{0ex}}(modF)$ also.
Title  partitions form a lattice^{} 

Canonical name  PartitionsFormALattice 
Date of creation  20130322 16:45:22 
Last modified on  20130322 16:45:22 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  6 
Author  CWoo (3771) 
Entry type  Derivation 
Classification  msc 06B20 
Defines  lattice of equivalence relations 