lattice

A lattice is a partially ordered set in which any two elements have both a single best lower bound and a single best upper bound. The everyday model is sets under inclusion: given two sets, their intersection is the largest set contained in both, and their union is the smallest set containing both. Abstracting these to ‘meet’ and ‘join’ gives a structure that sits at the crossroads of order theory and algebra.

Formally there are two equivalent definitions. Order-theoretically, a lattice is a poset (L, ≤) in which every pair {a, b} has a greatest lower bound a ∧ b (the meet, or infimum) and a least upper bound a ∨ b (the join, or supremum). Algebraically, a lattice is a set with two binary operations ∧ and ∨ that are each commutative, associative, idempotent and satisfy the absorption laws a ∧ (a ∨ b) = a and a ∨ (a ∧ b) = a. The two descriptions coincide via a ≤ b iff a ∧ b = a, making lattices a genuine variety of algebras.

Because lattices are equationally defined, all of universal algebra applies: there are sublattices, lattice congruences, lattice homomorphisms (maps preserving ∧ and ∨) and free lattices. Important special cases include distributive lattices, modular lattices, complete lattices and Boolean algebras. Lattices arise everywhere — the subgroups of a group, the ideals of a ring, the subspaces of a vector space, and the congruences of any algebra all form lattices under inclusion.