Every lattice can be represented as a DAG, but not every DAG is a lattice. The relationship is one of containment: lattices are a strict subset of DAGs with additional algebraic structure.
DAG → Partial Order → Lattice (increasingly constrained)
## DAGs and Partial Orders
DAGs represent partial orders. Any finite partial order (a set with a reflexive, antisymmetric, transitive relation) can be drawn as a DAG via its Hasse diagram — edges represent the covering relation (direct "less than" with nothing in between), and transitivity is implicit through paths.
## Lattices Require Additional Structure
A lattice is a partial order where every pair of elements has both a least upper bound (join/supremum) and a greatest lower bound (meet/infimum). This is strictly stronger than being a DAG.
A DAG only requires acyclicity and directed edges — it imposes no constraints on the existence of joins or meets.
## Key Distinctions
A DAG can have elements with no common ancestor or no common descendant. A lattice cannot — every pair must have a meet and a join.
A semilattice is the intermediate case: every pair has a join (join-semilattice) or a meet (meet-semilattice), but not necessarily both. The Hasse diagram of any finite lattice is a connected DAG where the top element (greatest element) and bottom element (least element) always exist.
## Practical Example
In a version control system, the commit history forms a DAG. But it's generally not a lattice — two branches may not have a unique least common ancestor (merge base).
Git's octopus merges and criss-cross merges are cases where the DAG structure lacks the clean algebraic properties a lattice guarantees.
## Where This Matters in CS
- Type systems (subtype lattices)
- Static analysis (abstract interpretation uses lattices for fixpoint computation)
- Distributed systems (vector clocks form a lattice; CRDTs rely on join-semilattice structure)
- Compiler optimization (dominance trees in CFGs relate to lattice-theoretic concepts)
In short: a lattice is a DAG with enough structure that you can always combine any two elements upward (join) or downward (meet) and get a unique result.
