9.3 Lattices and their applications

Lattices and their properties

A lattice is a poset where every pair of elements has both a unique least upper bound (join) and a unique greatest lower bound (meet). This dual guarantee gives lattices a rich algebraic structure that plain posets lack, and it's exactly what makes them show up across logic, computer science, and abstract algebra.

Fundamental concepts of lattices

The two core operations on a lattice are:

• Join ($\lor$): the least upper bound (supremum) of two elements.
• Meet ($\land$): the greatest lower bound (infimum) of two elements.

These operations satisfy four algebraic laws. For all elements $a, b, c$ in the lattice:

• Commutativity: $a \lor b = b \lor a$ and $a \land b = b \land a$
• Associativity: $(a \lor b) \lor c = a \lor (b \lor c)$ and $(a \land b) \land c = a \land (b \land c)$
• Absorption: $a \lor (a \land b) = a$ and $a \land (a \lor b) = a$
• Idempotence: $a \lor a = a$ and $a \land a = a$

Absorption is the one that trips people up most often. It captures how join and meet interact: joining $a$ with something already "below" $a$ just gives you $a$ back, and vice versa. Together, these four properties are equivalent to the order-theoretic definition of a lattice, so you can work algebraically or order-theoretically depending on what's more convenient.

Types of lattices

Bounded lattices have a greatest element ($\top$, called "top") and a least element ($\bot$, called "bottom"). The power set $\mathcal{P}(S)$ ordered by inclusion is a standard example: $\top = S$ and $\bot = \emptyset$.

Distributive lattices satisfy an extra condition linking join and meet:

• $a \lor (b \land c) = (a \lor b) \land (a \lor c)$
• $a \land (b \lor c) = (a \land b) \lor (a \land c)$

Not every lattice is distributive. A quick test: if the lattice contains a sublattice isomorphic to $M_3$ (the diamond) or $N_5$ (the pentagon), it is not distributive. The positive integers ordered by divisibility, where $a \lor b = \text{lcm}(a,b)$ and $a \land b = \gcd(a,b)$, form a classic distributive lattice.

Complemented lattices are bounded lattices where every element $a$ has a complement $a'$ satisfying:

$a \lor a' = \top \quad \text{and} \quad a \land a' = \bot$

A Boolean algebra is a lattice that is both complemented and distributive. In a Boolean algebra, complements are unique. The power set lattice $\mathcal{P}(S)$ under union and intersection is the prototypical Boolean algebra, with complement being set complement.

Least upper bounds and greatest lower bounds

Definitions and properties

• The least upper bound (LUB) of a subset $S$ in a lattice $L$ is the smallest element in $L$ that is greater than or equal to every element of $S$.
• The greatest lower bound (GLB) of a subset $S$ in $L$ is the largest element in $L$ that is less than or equal to every element of $S$.

In a lattice, every finite pair has a LUB and GLB by definition. A complete lattice goes further: every subset (including infinite ones) has a LUB and GLB. The power set $\mathcal{P}(S)$ under inclusion is complete. The real number line under the usual ordering is not a complete lattice, because unbounded subsets like $\mathbb{R}$ itself have no least upper bound within $\mathbb{R}$. The extended real line $[-\infty, +\infty]$, however, is complete.

Zorn's Lemma is a set-theoretic tool (equivalent to the Axiom of Choice) that guarantees the existence of maximal elements in a poset where every chain has an upper bound. It's used less to find LUBs directly and more to prove existence results in algebra and analysis (e.g., every vector space has a basis).

Key theorems

Knaster-Tarski Fixed-Point Theorem: Every order-preserving (monotone) function $f: L \to L$ on a complete lattice $L$ has at least one fixed point. In fact, the set of all fixed points itself forms a complete lattice.

This theorem is powerful in computer science for proving that recursive definitions have solutions. For instance, the denotational semantics of a recursive program can be defined as the least fixed point of a monotone operator on a complete lattice of partial functions.

Galois connections are pairs of order-preserving maps between two posets that generalize the relationship between LUBs and GLBs. Formally, a Galois connection between posets $P$ and $Q$ consists of maps $f: P \to Q$ and $g: Q \to P$ such that $f(p) \leq q$ if and only if $p \leq g(q)$. The classical example is the Galois connection between subgroups of a field's automorphism group and intermediate subfields, which is the foundation of Galois theory.

Lattice structure and analysis

Hasse diagrams and visual representation

A Hasse diagram is the standard way to draw a finite poset. Elements are nodes, and an edge from $a$ up to $b$ means $b$ covers $a$ (i.e., $a < b$ with nothing in between). Transitivity is implied, so you don't draw redundant edges.

To find the join and meet visually:

1. Join of $a$ and $b$: Start at both nodes and trace upward. The join is the lowest node that sits above both $a$ and $b$.
2. Meet of $a$ and $b$: Start at both nodes and trace downward. The meet is the highest node that sits below both $a$ and $b$.

If you can always find such nodes for every pair, the Hasse diagram represents a lattice.

Modular lattices satisfy a restricted form of distributivity: if $a \leq c$, then $a \lor (b \land c) = (a \lor b) \land c$. Every distributive lattice is modular, but not vice versa. The lattice of subspaces of a vector space is modular but generally not distributive (when the dimension is $\geq 3$). In a Hasse diagram, a lattice fails modularity exactly when it contains a copy of $N_5$ (the pentagon) as a sublattice.

Advanced analysis techniques

• Sublattices are subsets of a lattice that are closed under join and meet. Identifying sublattices helps you spot familiar structures inside a larger, more complex lattice.
• Lattice homomorphisms are maps $\phi: L_1 \to L_2$ preserving both operations: $\phi(a \lor b) = \phi(a) \lor \phi(b)$ and $\phi(a \land b) = \phi(a) \land \phi(b)$. These let you compare the structure of different lattices.
• Congruence relations are equivalence relations on a lattice that are compatible with join and meet. Quotienting by a congruence gives a quotient lattice, analogous to quotient groups in algebra.
• Lattice dimension (also called order dimension) is the minimum number of linear orders (chains) whose intersection recovers the original partial order. It measures how far a poset is from being a total order. For example, the Boolean lattice on 3 atoms has dimension 3.

Birkhoff's Representation Theorem gives a concrete picture of finite distributive lattices: every finite distributive lattice is isomorphic to the lattice of downsets (order ideals) of some finite poset, ordered by inclusion. This means you can always "decode" a finite distributive lattice into a simpler poset of its join-irreducible elements.

Applications of lattice theory

Logic and computer science

Propositional logic forms a Boolean algebra. Propositions are lattice elements, with AND as meet, OR as join, and NOT as complementation. Tautologies correspond to $\top$ and contradictions to $\bot$. This algebraic viewpoint simplifies circuit design and logical equivalence proofs.

Domain theory uses complete partial orders (CPOs) and continuous lattices to give meaning to recursive programs. The idea is that a program's behavior is the least fixed point of a continuous operator on a domain of "partial information," grounded in the Knaster-Tarski theorem.

Database theory uses lattices to model functional dependencies between attributes. The set of all functional dependencies that hold in a relation forms a lattice structure, and the process of normalization (decomposing tables into 2NF, 3NF, BCNF) can be understood as navigating this lattice.

Formal concept analysis (FCA) builds a concept lattice from a binary relation between objects and attributes. Each node in the lattice represents a formal concept (a maximal set of objects sharing a maximal set of attributes). FCA is used in data mining, ontology construction, and knowledge representation.

Social choice theory and cryptography

In social choice theory, preference orderings can be modeled as lattice elements. Arrow's Impossibility Theorem, which shows no voting system with $\geq 3$ candidates can satisfy a small set of fairness axioms simultaneously, has been analyzed through lattice-theoretic lenses to clarify exactly where the constraints conflict.

Lattice-based cryptography is one of the leading candidates for post-quantum cryptography. Hard problems on high-dimensional lattices, such as the Shortest Vector Problem (SVP) and the Learning With Errors (LWE) problem, appear resistant to both classical and quantum algorithms. The NIST post-quantum standards (e.g., CRYSTALS-Kyber, CRYSTALS-Dilithium) are built on these lattice problems.

Quantum logic replaces the Boolean algebra of classical logic with orthomodular lattices. In quantum mechanics, the "propositions" about a system (e.g., "the particle's spin is up") form a lattice of closed subspaces of a Hilbert space. This lattice is modular (for finite-dimensional spaces) but not distributive, which reflects the fact that quantum measurements don't combine the way classical yes/no questions do.