Lattice (Order Theory)

Lemma 1: Let $P$ be a poset, $S\subseteq P$, and $p\in P$. If both $\bigvee S$ and $(\bigvee S)\vee p$ exist then $\bigvee (S\cup \{p\left\}\right)$ exists as well, and $(\bigvee S)\vee p=\bigvee (S\cup \{p\left\}\right)$.

Proof: See the Join fu exercise in Join and meet: Exercises.

Associativity

Let $L$ be a lattice and $p,q,r,s\in L$ such that $s=p\vee (q\vee r)$. We apply the above lemma, along with commutativity and closure of lattices under binary joins, to get $$p\vee (q\vee r)=(q\vee r)\vee p=(\bigvee \{q,r\left\}\right)\vee p=\bigvee \left(\right\{q,r\}\cup \{p\left\}\right)=$$ $$\bigvee \{q,r,p\}=\bigvee \left(\right\{p,q\}\cup \{r\left\}\right)=(\bigvee \{p,q\left\}\right)\vee r=(p\vee q)\vee r.$$

By duality, we also have the associativity of binary meets.

Commutativity

Let $L$ be a lattice and $p,q\in L$. Then $p\vee q=\bigvee \{p,q\}=q\vee p$. Binary joins are therefore commutative. By duality, binary meets are also commutative.

Idempotency

Let $L$ be a lattice and $p\in L$. Then $p\vee p=\bigvee \left\{p\right\}=p$. The property that for all $p\in L$, $p\vee p=p$ is called idempotency. By duality, we also have the idempotency of meets: for all $p\in L$, $p\wedge p=p$.

Absorption

Since $p\wedge q$ is the greatest lower bound of $\{p,q\}$, $p\wedge q\le p$. Because $p\le p$ and $(p\wedge q)\le p$, $p$ is an upper bound of $\{p,p\wedge q\}$, and so $p\vee (p\wedge q)\le p$. On the other hand, $p\vee (p\wedge q)$ is the least upper bound of $\{p,p\wedge q\}$, and so $p\le p\vee (p\wedge q)$. By anti-symmetry, $p=p\vee (p\wedge q)$.

Here again, we will need Lemma 1, stated in the proofs of the four lattice properties.

Our proof proceeds by induction on the cardinality of $S$.

The base case is $\bigvee \left\{s_1\right\}=s_1\in L$. For the inductive step, we suppose that $\bigvee \{s_1,...,s_i\}$ exists. Then, applying lemma 1, we have $\bigvee \{s_1,...,s_{i+1}\}=\bigvee \{s_1,...,s_i\}\vee s_{i+1}$. Applying our inductive hypothesis and closure under binary joins, we have $\bigvee \{s_1,...,s_i\}\vee s_{i+1}$ exists. Lattices are therefore closed under all finite joins, not just binary ones. Dually, lattices are closed under all finite meets.

We prove $p\vee q=p\iff q\le p$; the other part follows from duality. If $p\vee q=p$, then $p$ is an upper bound of both $p$ and $q$, and so $q\le p$. Going the other direction, suppose $q\le p$. Since $p$ is and upper bound of itself by reflexivity, it then follows that $p$ is an upper bound of $\{p,q\}$. There cannot be a lesser upper bound of $\{p,q\}$ because it would not be an upper bound of $p$. Hence, $p\vee q=p$.