Lattice

A lattice is a partially ordered set in which every pair of elements has both a least upper bound (called the join, written a ∨ b) and a greatest lower bound (called the meet, written a ∧ b). This deceptively simple definition generates a rich algebraic structure that appears across mathematics and computer science: the lattice of subsets of a set, the lattice of subgroups of a group, the lattice of open sets in a topological space, and the lattice of propositions in logic.

A lattice is complete if every subset — not merely every pair — has a join and a meet. Complete lattices are the natural setting for fixed-point theorems, including the Knaster-Tarski theorem that guarantees every order-preserving map on a complete lattice has a least fixed point. This result is foundational for denotational semantics, where the meaning of a recursive program is defined as the least fixed point of a transformation on a lattice of partial computations.

Lattices can be characterized purely algebraically by the identities satisfied by join and meet: associativity, commutativity, absorption, and idempotence. A lattice that satisfies the distributive law a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) is called a distributive lattice. Boolean algebras are the complemented distributive lattices, and the lattice of projections in quantum mechanics is orthomodular — distributivity fails in a way that encodes the structure of quantum measurement.

The ubiquity of lattice structure suggests that ordering is not a property of individual domains but a universal organizational principle. Wherever parts compose into wholes, the operations of combination and decomposition generate a lattice. The lattice is not imposed upon the system; it is the shadow cast by the system's own compositional structure.