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.