The Powerset Lattice

Our meets are precise — combining two sets of facts gives us exactly their union. But joins lose information. When two states disagree on a cell, the join simply forgets it:

a = 1 at (1,1) 2 at (1,2)

b = 1 at (1,1) 4 at (1,2)

a ⊔ b = 1 at (1,1)

Both a and b know something about cell (1,2), but since they disagree, the join throws it away entirely. We've lost the fact that (1,2) is either 2 or 4 — not 1 or 3.

What data structure would avoid losing any information?

The simplest answer: track all possible complete grids. A state of knowledge becomes a set of complete assignments Loc → {1, 2, 3, 4}.

This is the powerset lattice 𝒫(Loc → N):

Elements: Sets of complete grids
⊤: The set of all complete grids — we know nothing
⊥: ∅ — inconsistent, no grid satisfies the constraints
Meet (⊓): Intersection — combining knowledge narrows possibilities
Join (⊔): Union — agreement keeps all possibilities from both

Now joins are precise too. No information is lost.

Below we show the 288 grids that follow the rules of Sudoku. Fill in a cell and watch the compatible set shrink. Hover a thumbnail to preview it:

288 compatible grids

There is usually a most precise representation, but it is computationally too expensive.