Lattice

Definition

A lattice is a partially ordered set $(L,\le )$ in which every pair of elements has both a least upper bound (called the join or supremum) and a greatest lower bound (called the meet or infimum).

For any $a,b\in L$:

• The join $a\vee b$ is the smallest element $c$ such that $a\le c$ and $b\le c$
• The meet $a\wedge b$ is the largest element $d$ such that $d\le a$ and $d\le b$

Properties

A lattice satisfies the following axioms for all $a,b,c\in L$:

Commutativity: $a\vee b=b\vee a\text{and}a\wedge b=b\wedge a$

Associativity: $a\vee (b\vee c)=(a\vee b)\vee c\text{and}a\wedge (b\wedge c)=(a\wedge b)\wedge c$

Idempotency: $a\vee a=a\text{and}a\wedge a=a$

Absorption: $a\vee (a\wedge b)=a\text{and}a\wedge (a\vee b)=a$

Complete Lattice

A complete lattice is a partially ordered set in which every subset has both a supremum and an infimum. Every finite lattice is complete.

Examples

• The power set $\mathcal{P}(S)$ of any set $S$ with inclusion $\subseteq$ forms a complete lattice where join is union and meet is intersection
• The set of natural numbers $\mathbb{N}$ with divisibility relation forms a lattice where join is least common multiple and meet is greatest common divisor
• Any totally ordered set forms a lattice where $a\vee b=\max (a,b)$ and $a\wedge b=\min (a,b)$

Related Concepts

• Boolean Algebra
• Heyting Algebra
• Partial Order