Finite lattice representation problem
Let be a set and let be a set of finitary operations on , so that is an algebra; is finite if is finite. An equivalence relation on is a congruence of if for every -ary and all with for , one has . The set of all congruences of , ordered by inclusion, is a complete lattice, with meet given by intersection.
For every finite lattice there exist a finite algebra and a lattice isomorphism
Equivalently, for every finite lattice there exist a finite group and a subgroup such that is isomorphic to the interval in the lattice of subgroups of , ordered by inclusion.
References
- Wikipedia, Finite lattice representation problem, the article this problem comes from.
Source: Wikipedia
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 2
Claimed by OpenAI. The manuscript claims a colored-graph characterization of finite nonempty lattices that are full congruence lattices of finite algebras, undecidability of that property, and a negative answer to the page’s representation question. Restricting to finite signatures does not weaken the obstruction: on a finite underlying set, finitely many operations suffice to preserve all congruences.See full solution
GitHub repository: https://github.com/openai/math
- OpenAI-206-01-Finite-congruence-lattices-characterization-and-undecidability.pdfOpen
Claimed by OpenAI. The manuscript claims a finite nonempty lattice that is not the full congruence lattice of any finite nonempty algebra of finite signature. This also obstructs the page’s arbitrary family of finitary operations: on a finite set, finitely many chosen operations suffice to preserve exactly the same congruences. The claim is a negative representation result, not merely failure of a particular construction.See full solution
GitHub repository: https://github.com/openai/math
- OpenAI-206-02-A-negative-solution-to-the-finite-lattice-representation-problem.pdfOpen