The Setting
Take a finite lattice and ask whether it is isomorphic to the congruence lattice of a finite algebra.
Algebras and Congruences
An algebra on a set is a finite list of operations on , each a map of some arity ; constants () and the empty list () are allowed.✦ A finite algebra is an algebra on the set for some .
An equivalence relation on is compatible with when, for each operation of arity and all , (1)✦ A congruence of is an equivalence relation on compatible with .✦ The congruence lattice of is the set of all congruences of , ordered by inclusion.✦
A partially ordered set is representable, written , when there are a finite algebra and an order isomorphism of onto .✦
Graph Witnesses
Let be a lattice with least element . An -coloring of a set of vertices is a map , with the color of the edge ; loops count as edges. A self-map of is admissible for when (2)✦
Fix a finite set of ordered pairs of vertices, the seed edges, and put . The marked graph is the graph on whose edges, the marked edges, are the pairs with and admissible for .✦ Vertices and are connected in when they lie in one class of the equivalence relation on generated by the marked edges.✦
An -coloring of is a graph witness for when the following hold:✦
for all vertices ;
exactly when ;
for all vertices ;
for all with there are vertices with and ;
for every nonempty finite set of seed edges, any two vertices with are connected in .
The lattice has a graph witness on vertices when some -coloring of is a graph witness for , and it has a graph witness when it has one on vertices for some .✦
The Claim
Theorem 1. Let be a finite lattice with least element . Then (3)✦ If, moreover, equality and order in are decidable, then for every natural number it is decidable whether (4)✦
In the paper, the result reads: (i) a finite nonempty lattice is representable exactly when it satisfies the finite colored-graph criterion of Theorem 2.2, and for each candidate graph size the criterion is decidable by a finite test; (ii) there is no deterministic Turing machine that, given the order table of a finite nonempty lattice , always halts and decides ; (iii) there is a nonrepresentable finite lattice of minimum cardinality, specified by the finite formulas of §17, every finite lattice of smaller cardinality is representable, and ; (iv) given the order table of a finite nonempty lattice , it is undecidable whether, for some finite group and subgroup , , the interval of subgroups with . The theorem above is part (i), with the graph witness as the criterion of Theorem 2.2.
What Is Checked
The claim is stated over finite lattices with a least element, over finite algebras, their congruences (1) and representability, and over graph witnesses with the admissible self-maps (2), marked graphs and connectivity they are built from.
Beside the claim, the library gives a decision procedure for graph witnesses: for a finite lattice with least element and decidable equality and order, and an -coloring of a finite set of vertices with decidable equality, it is decidable whether the coloring is a graph witness for .✦