FLRP.Certificates.SmallLatticeReps.SLR02¶
A machine-checked representation: Con(B2) ≅ manuscript L2 (M3)¶
This is the FLRP.Certificates.SmallLatticeReps.SLR02 module of the Agda Universal Algebra Library.
This module was emitted by scripts/python/flrp/emit_agda.py from
scripts/python/flrp/inputs/slr/slr02.json. Do not edit it by hand; rerun the emitter instead.
B2/L2 in the numbering of the DeMeo–Freese–Jipsen manuscript Representing Finite Lattices as Congruence Lattices of Finite Algebras (§ 6 of the 2016-06-10 draft, docs/papers/fin-lat-rep/SmallLatticeReps.tex). The dictionary between the manuscript's lattice numbering and this library's names is docs/notes/flrp-slr-naming.md.
It re-verifies, end-to-end through the WP-6 certificate pipeline (#457), the
claim that the congruence lattice of the algebra "B2" — carrier size
3, unary operations f — is isomorphic to the lattice
"manuscript L2 (M3)" (5 elements). The engine's output below (normal-form
parent vectors, Freese traces, and pointer tables) is certificate data only:
the search-free checkers of Setoid.Congruences.Certificates re-verify all
of it during type-checking, and the FLRP.Certificates assembly turns the
checked certificate into the headline theorems — a
Representableᵈ witness for the target lattice and a
FiniteCongruencesᵈ instance for the algebra. Nothing is
believed on the engine's authority: a wrong table or trace would make a
decidable check compute to no and break
compilation.
The algebra, from its operation tables¶
Row f of opTables is the value table of the f-th unary
operation; Classical.Structures.Unary turns the table into the algebra
and its finiteness witnesses.
opTables : Vec (Vec (Fin 3) 3) 1 opTables = (0F ∷ 1F ∷ 2F ∷ []) ∷ [] 𝑨 : Algebra {𝑆 = Sig-Unary (Fin 1)} 0ℓ 0ℓ 𝑨 = tablesToUnaryAlgebra 3 1 opTables 𝑭 : FiniteAlgebra 𝑨 𝑭 = tablesToUnaryAlgebra-FiniteAlgebra 3 1 opTables 𝑺 : FiniteSignature (Sig-Unary (Fin 1)) 𝑺 = Sig-Unary-Fin-FiniteSignature 1
The target lattice, from its Cayley tables¶
The claimed congruence lattice "manuscript L2 (M3)", presented exactly as the worked lattice examples are (Examples.Classical.Lattices.L7): meet and join tables, every law discharged by decision over the finite carrier.
∧-table ∨-table : Table 5 ∧-table = (0F ∷ 0F ∷ 0F ∷ 0F ∷ 0F ∷ []) ∷ (0F ∷ 1F ∷ 0F ∷ 0F ∷ 1F ∷ []) ∷ (0F ∷ 0F ∷ 2F ∷ 0F ∷ 2F ∷ []) ∷ (0F ∷ 0F ∷ 0F ∷ 3F ∷ 3F ∷ []) ∷ (0F ∷ 1F ∷ 2F ∷ 3F ∷ 4F ∷ []) ∷ [] ∨-table = (0F ∷ 1F ∷ 2F ∷ 3F ∷ 4F ∷ []) ∷ (1F ∷ 1F ∷ 4F ∷ 4F ∷ 4F ∷ []) ∷ (2F ∷ 4F ∷ 2F ∷ 4F ∷ 4F ∷ []) ∷ (3F ∷ 4F ∷ 4F ∷ 3F ∷ 4F ∷ []) ∷ (4F ∷ 4F ∷ 4F ∷ 4F ∷ 4F ∷ []) ∷ [] open FiniteLattice 𝑳 : FiniteLattice 𝑳 .size = 4 𝑳 ._∧_ = ⟦ ∧-table ⟧ 𝑳 ._∨_ = ⟦ ∨-table ⟧ 𝑳 .∧-assoc = from-yes (Associative? ⟦ ∧-table ⟧) 𝑳 .∧-comm = from-yes (Commutative? ⟦ ∧-table ⟧) 𝑳 .∧-idem = from-yes (Idempotent? ⟦ ∧-table ⟧) 𝑳 .∨-assoc = from-yes (Associative? ⟦ ∨-table ⟧) 𝑳 .∨-comm = from-yes (Commutative? ⟦ ∨-table ⟧) 𝑳 .∨-idem = from-yes (Idempotent? ⟦ ∨-table ⟧) 𝑳 .absorbˡ = from-yes (Absorbsˡ? ⟦ ∧-table ⟧ ⟦ ∨-table ⟧) 𝑳 .absorbʳ = from-yes (Absorbsʳ? ⟦ ∧-table ⟧ ⟦ ∨-table ⟧)
The certificate¶
The engine's whole-lattice certificate (design note § 4): the congruence
list as normal-form parent vectors, indexed by the lattice's carrier; the
principal-congruence pointer table with one Freese trace per carrier pair;
and the join traces, seeded by forest edges. The meet and join tables are
the target's own tables, which is what MeetMatches pins.
open CertCheck 𝑭 𝑺 using ( arOf ) cert : LatticeCert 3 1 arOf 5 cert = mkLatticeCert partsᵛ 0F prinᵛ prinTrᵛ ∧-table ∨-table joinTrᵛ where partsᵛ : Vec (ParentVec 3) 5 partsᵛ = (0F ∷ 1F ∷ 2F ∷ []) ∷ (0F ∷ 0F ∷ 2F ∷ []) ∷ (0F ∷ 1F ∷ 0F ∷ []) ∷ (0F ∷ 1F ∷ 1F ∷ []) ∷ (0F ∷ 0F ∷ 0F ∷ []) ∷ [] prinᵛ : Vec (Vec (Fin 5) 3) 3 prinᵛ = (0F ∷ 1F ∷ 2F ∷ []) ∷ (1F ∷ 0F ∷ 3F ∷ []) ∷ (2F ∷ 3F ∷ 0F ∷ []) ∷ [] prinTrᵛ : Vec (Vec (Trace 3 1 arOf) 3) 3 prinTrᵛ = ( [] ∷ (mkMerge 0F 1F (seed 0) ∷ []) ∷ (mkMerge 0F 2F (seed 0) ∷ []) ∷ [] ) ∷ ( (mkMerge 1F 0F (seed 0) ∷ []) ∷ [] ∷ (mkMerge 1F 2F (seed 0) ∷ []) ∷ [] ) ∷ ( (mkMerge 2F 0F (seed 0) ∷ []) ∷ (mkMerge 2F 1F (seed 0) ∷ []) ∷ [] ∷ [] ) ∷ [] joinTrᵛ : Vec (Vec (Trace 3 1 arOf) 5) 5 joinTrᵛ = ( [] ∷ (mkMerge 1F 0F (seed 0) ∷ []) ∷ (mkMerge 2F 0F (seed 0) ∷ []) ∷ (mkMerge 2F 1F (seed 0) ∷ []) ∷ ( mkMerge 1F 0F (seed 0) ∷ mkMerge 2F 0F (seed 1) ∷ [] ) ∷ [] ) ∷ ( (mkMerge 1F 0F (seed 0) ∷ []) ∷ (mkMerge 1F 0F (seed 0) ∷ []) ∷ ( mkMerge 1F 0F (seed 0) ∷ mkMerge 2F 0F (seed 1) ∷ [] ) ∷ ( mkMerge 1F 0F (seed 0) ∷ mkMerge 2F 1F (seed 1) ∷ [] ) ∷ ( mkMerge 1F 0F (seed 0) ∷ mkMerge 2F 0F (seed 2) ∷ [] ) ∷ [] ) ∷ ( (mkMerge 2F 0F (seed 0) ∷ []) ∷ ( mkMerge 2F 0F (seed 0) ∷ mkMerge 1F 0F (seed 1) ∷ [] ) ∷ (mkMerge 2F 0F (seed 0) ∷ []) ∷ ( mkMerge 2F 0F (seed 0) ∷ mkMerge 2F 1F (seed 1) ∷ [] ) ∷ ( mkMerge 2F 0F (seed 0) ∷ mkMerge 1F 0F (seed 1) ∷ [] ) ∷ [] ) ∷ ( (mkMerge 2F 1F (seed 0) ∷ []) ∷ ( mkMerge 2F 1F (seed 0) ∷ mkMerge 1F 0F (seed 1) ∷ [] ) ∷ ( mkMerge 2F 1F (seed 0) ∷ mkMerge 2F 0F (seed 1) ∷ [] ) ∷ (mkMerge 2F 1F (seed 0) ∷ []) ∷ ( mkMerge 2F 1F (seed 0) ∷ mkMerge 1F 0F (seed 1) ∷ [] ) ∷ [] ) ∷ ( ( mkMerge 1F 0F (seed 0) ∷ mkMerge 2F 0F (seed 1) ∷ [] ) ∷ ( mkMerge 1F 0F (seed 0) ∷ mkMerge 2F 0F (seed 1) ∷ [] ) ∷ ( mkMerge 1F 0F (seed 0) ∷ mkMerge 2F 0F (seed 1) ∷ [] ) ∷ ( mkMerge 1F 0F (seed 0) ∷ mkMerge 2F 0F (seed 1) ∷ [] ) ∷ ( mkMerge 1F 0F (seed 0) ∷ mkMerge 2F 0F (seed 1) ∷ [] ) ∷ [] ) ∷ []
The verification¶
One decision for the whole certificate, one for the meet-table match; both
compute to yes — that computation is the
re-verification of every engine claim above.
open LatticeCheck 𝑭 𝑺 certOK : LatticeCertOK cert certOK = from-yes (latticeCertOK? cert) certMeet : MeetMatches 𝑭 𝑺 𝑳 cert certMeet = from-yes (meetMatches? 𝑭 𝑺 𝑳 cert)
The headline theorems¶
The target lattice is decidably representable, witnessed by this algebra; and the certificate's congruence list is a complete Layer-D enumeration of the algebra's decidable congruences.
SLR02-Representableᵈ : Representableᵈ (toLattice 𝑳) SLR02-Representableᵈ = certRepresentableᵈ 𝑭 𝑺 𝑳 cert certOK certMeet SLR02-FiniteCongruencesᵈ : FiniteCongruencesᵈ 𝑨 SLR02-FiniteCongruencesᵈ = certFiniteCongruencesᵈ cert certOK