The small systems atlas

SOURCE CONTEXT / 01 · FAMILY 206

The saved N5 construction
and its five congruences.

For the two saved unary operations on four objects, exactly five of the 15 possible groupings are valid. Their inclusion order is N5. The separate Lean classification covers all equivalence relations for these exact operations.

Explore the saved construction ↓

Method: check every grouping, then inspect the exact Lean classification and its verification record.

01 / Follow the rules

Check which groupings both operations preserve.

Carrier: {0, 1, 2, 3}

A grouping works when any two objects in the same group still land in the same group after each rule. The output group may differ from the input group.

The two operation tables

f swaps the objects in each pair. g sends the second pair onto the first.

f0 ⇄ 12 ⇄ 3

g0 → 0   1 → 12 → 0   3 → 1

Here 0 and 1 name individual objects. Lattice labels ⊥ and ⊤ below mean entire groupings.

Try any of the 15 groupings

A bar separates groups: {0, 1} | {2} | {3} keeps 0 and 1 together.

This small check runs in your browser. It illustrates the rule; the Lean proof is linked separately.

02 / Account for every possibility

Why exactly these five?

Each listed grouping survives both rules. For example, in {0, 2} | {1, 3}, f swaps the two groups and g sends each group into itself. Inputs that were together remain together.

The order is ⊥ < a < b < ⊤ and ⊥ < c < ⊤. Neither a nor b is comparable to c.

Read the exact Lean classification ↗
1

Merge 0 with 3, or 1 with 2

f forces the other pair. Then g forces 0 with 1. Together these identifications connect all four objects, so only the one-group partition survives.

2

Otherwise, merge 0 with 2, or 1 with 3

f forces both pairs, giving {0, 2} | {1, 3}. Any further merge combines its two blocks into one.

3

Otherwise, keep the two halves separate

Only the pairs {0, 1} and {2, 3} can merge. g forces a merge of 0 with 1 whenever 2 and 3 merge. That leaves exactly ⊥, a, and b.

COMPLETENESS

We have both directions: all five displayed groupings work, and every possible valid grouping is one of them. That is what “the full congruence lattice” requires.

How the formal proof covers every relation

finite_classification checks the 64 symmetric reflexive Boolean relations on four points. Many are not transitive. relation_complete proves that every equivalence relation has such an encoding; all_relations lifts the classification to proposition-valued relations. The proof uses Lean kernel reduction with decide.

The browser lists the 15 partitions instead. Its calculation and the human explanation are distinct from that formal proof.

PROOF REUSE / TWO REGISTERED RENAMINGS

Reuse the N5 classification
under two proved renamings.

Same five groupings, justified by a mapping

A consistent renaming carries every object, rule, and grouping together. We can then reuse the original classification: exactly five groupings work, with the same inclusion order. A matching shape alone would not justify that step.

03 / Place the example in the argument

Which patterns can rules produce?

Family 206 asks which finite lattices can occur as all the congruences of a nonempty finite algebra. Finding a few valid groupings is not enough: there must be no extra ones.

The original paper defines this question in §1.1, page 4. Its Theorem 2.2, pages 7–8, gives a colored-graph criterion for representation. Open the pinned paper ↗

Turn groupings into colors

For two objects x and y, d(x,y) is the smallest valid grouping that puts them together. It is a lattice label, not a number measuring distance.

For instance, d(2,3) = b: any valid grouping that merges 2 and 3 must also merge 0 and 1. For a lattice label ℓ, recover its grouping by the rule x ~ y exactly when d(x,y) ≤ ℓ.

This is the threshold relation θℓ. At threshold b, the two groups are {0, 1} and {2, 3}; at threshold c, they are {0, 2} and {1, 3}.

What the graph criterion adds

Colors must be symmetric, equal to bottom exactly on the diagonal, obey a join-valued triangle inequality, and distinguish lattice order.

The remaining condition is about paths: choose any nonempty set of seed edges. Apply all maps that can only decrease colors. Every pair whose color is below the join of the seed colors must be connected by the resulting marked edges.

That condition makes the recovered grouping list complete. In the reverse construction the theorem uses all color-decreasing maps as unary operations. Our saved example has 12 such maps, and the two displayed rules already give exactly its five groupings.

See how the local N5 bridge proves the full predicate ↗
The exact Lean statement and its assumptions

Fintype Lat supplies finiteness; Lattice Lat supplies meets and joins; OrderBot Lat supplies a least element. Representable requires a positive carrier size and an order isomorphism onto every congruence of a finite list of total finite-arity operations. An empty operation list is permitted.

The local N5 bridge proves this for the saved two-operation algebra. The general theorem relates representability and existence of a graph witness; it does not supply a stopping rule for a search that has found no witness.

04 / Follow the evidence

Source definitions, proofs and verification records.

Select a node or use the source selector. Dashed links provide context; solid links point to proofs; dotted links identify definitions or a statement comparison. Every line names its relationship.

A curated reading map, not an automatically extracted dependency graph. “Shares definitions” does not mean the N5 proof depends on the general equivalence theorem.

The comparator contains a placeholder

The upstream comparator intentionally ends its target theorem with sorry. It tells the checker what must be proved. The completed upstream graph_criterion proof lives in a separate file. Its comparator acceptance record is also separate from the local N5 build and kernel-replay record.

Scope: these records support the selected graph criterion and exact concrete example. They do not validate the paper’s undecidability or subgroup-interval conclusions. The Turing examples belong to separate family 376; their machine checks do not validate the fluid-flow argument.

All pinned sources, proof records, and hashes

Matching hashes establish which files a record refers to. They do not prove the explanation, and this page does not rerun Lean. Consult the recorded toolchain, axioms, and checks.

05 / Return to the collection

Same groupings. Different rule tables.

The saved Lean proof is attached to the four objects and two tables on this page. The atlas entry retains its computational evidence status.

Local record: python scripts/build_n5_context.py --show. See the written walkthrough for the full explanation.