A finite algebra is a nonempty finite set with a finite list of total operations on , each of finite arity, where the list may be empty and an operation of arity zero is a constant. The congruences of a finite algebra , ordered by inclusion, form its congruence lattice . A finite nonempty lattice is representable, written , when is isomorphic to the whole congruence lattice of some finite algebra . The finite lattice representation problem asks whether every finite lattice is representable. The order table of is the table that lists, for each pair of elements of , whether the first lies below the second. A second question asks whether can be decided from the order table of .
Grätzer and Schmidt proved that every algebraic lattice is the congruence lattice of an algebra, not necessarily finite. For a subgroup of a finite group , is the interval of all subgroups with . Pálfy and Pudlák proved that every finite lattice is representable if and only if every finite lattice is isomorphic to an interval of some finite group . Pudlák and Tůma proved that every finite lattice embeds in the lattice of equivalence relations of a finite set.
For a finite lattice with least element , an -colored complete graph is a finite nonempty set with a symmetric map such that exactly when . A map is admissible for when for all . For a nonempty set of pairs of points of , is the join of the colors of the pairs . The graph on has as its edges the pairs with and admissible. The preprint proves that holds exactly when some -colored complete graph satisfies for all , contains for each in a pair with and , and, for each nonempty , joins by a path in every pair with . For each number of vertices, a finite test decides whether such a graph exists. No Turing machine, given the order table of a finite lattice , always halts and decides . In particular, the finite lattice representation problem has a negative answer.
Of these results, the Lean library Universal contains the characterization of by -colored complete graphs and its finite test, and not the undecidability. For a finite group and a subgroup , the unary algebra on the left cosets has one operation for each . The Lean library also proves that the congruence lattice of this algebra is isomorphic to . The Lean library takes as a hypothesis of its finite test that equality and order in can be decided. Each result on these pages is the Lean library’s, stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every result of the Lean library, so the Lean library is the reference, and where the preprint states a result differently, the page gives the Lean library’s statement with the preprint’s beside it. The preprint is a guide only, which gives the results their order and their names.
Universal is a Lean library: 7 items, in three groups. Each has a page written by OctoInform, listed below.
No item matches.