Trying to prove that the poset of partitions ordered by refinement is a lattice

Question

I am brand new to lattices/partitions. Given that the set of all partitions of a finite set is a poset ordered by refinement, how does one prove that it is a lattice? I know you have to prove that the join and meet exist, but how does one construct them in this case? In other words, what are the join and meet of two partitions?

Answer 1

The meet of two partitions will be their largest common refinement. For instance,

$$\{\{a,d\},\{b,c\}\}\wedge\{\{a\},\{b,c,d\}\}=\{\{a\},\{b,c\},\{d\}\}.$$

In more precise terms, given two partitions $P_1$ and $P_2$, we may characterize the blocks of $P_1\wedge P_2$ as the nonempty intersections of blocks $a_i$ from $P_1$ and $b_i$ from $P_2$. Note that these resultant blocks include everything that is still allowed to be together under both sets of separation.

To see that this is indeed the meet we must check that two conditions are satisfied. Let us call $z=P_1\wedge P_2$.

1. We must have $z\le P_1$ and $z\le P_2$.
2. For any $w$ such that $w\le P_1$ and $w\le P_2$ we must have $w\le z$.

The first is perfectly clear as we constructed $z$ by refining $P_1$. So, we only check the second.

Suppose that we have such a $w$. Then consider a block $\pi$ of $w$, we show that this block is a subset of $\phi\cap\rho$ where $\phi$ and $\rho$ are blocks of $P_1$ and $P_2$. We suppose that $|\pi|>1$ as otherwise there is nothing to show. First pick any $a,b\in \pi$. We claim that $a,b$ appear in the same block in $P_1$ and in the same block $P_2$. If $a$ and $b$ fell into different blocks then $w$ would fail to be a refinement of $P_1$ or $P_2$. Thus there exist blocks $\phi_1\in P_1$ and $\phi_2\in P_2$ each containing $a$ and $b$. Then note that these blocks contain every element of $\pi$, and thus $\pi\subseteq \phi_1\cap \phi_2$. Thus we see that $w\le z$.

We can make a similar construction for the join of two partitions where the blocks of the join are the smallest subsets that are exactly the union of blocks from each partition, however, this is not necessary. We can note that the lattice contains a greatest element $\{\{a,b,c,...,n\}\}=1$ for which we have $1\wedge a=a$ for all $a$ in the lattice. Now we see that we have a finite meet-semilattice with $1$, which is a lattice. (This is the case because we can define the set $S=\{u\in L: u\ge s, u\ge t\}$ and then see that we have $s\vee t=\bigwedge_{u\in S} u$. This is proposition 3.3.1 in Stanley's Enumerative Combinatorics, Volume 1.)