mleku on Nostr: Every lattice can be represented as a DAG, but not every DAG is a lattice. The ...

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.