Partial Orderings as Partial Information
Imagine you're solving a Sudoku — a small one, 4×4, with digits 1–4. You start with a few givens. Everything else is unknown.
| 1 | 3 | ||
| 4 | |||
| 2 | |||
| 1 | 3 |
Your starting state of knowledge — call it a0 — is a list of facts:
By applying the rules, we can deduce new facts. Row 4 needs 2 and 4. Column 3 already has a 2, so (4,3) must be 4:
| 1 | 3 | ||
| 4 | |||
| 2 | |||
| 1 | 4 | 3 |
Each deduction gives a new state — a1, a2, and so on — each containing everything the previous one did, plus more.
We can order these states by how much they know. Write a ⊑ b when every fact in b is also in a — that is, a knows at least as much as b. As we learn more, we descend:
Try it yourself:
| 1 | 3 | ||
| 4 | |||
| 2 | |||
| 1 | 3 |
But not all states are comparable. One person might know one fact while another knows a different one — each knows something the other doesn't.
Neither a ⊑ b nor b ⊑ a.
This is a partial order: reflexive, antisymmetric, transitive — but not every pair of elements is comparable.