Congruence lattice problem: Difference between revisions

Revision as of 15:32, 8 November 2023

Latest revision as of 15:06, 27 August 2025

(4 intermediate revisions by 3 users not shown)

Line 1:

{{Short description|Important problem in lattice theory}}

In [[mathematics]], the '''congruence lattice problem''' asks whether every algebraic [[distributive lattice]] is [[isomorphic]] to the [[congruence lattice]] of some other lattice. The problem was posed by [[Robert P. Dilworth]], and for many years it was one of the most famous and long-standing open problems in [[lattice theory]]; it had a deep impact on the development of lattice theory itself. The conjecture that every distributive lattice is a congruence lattice is true for all distributive lattices with at most [[Aleph number|ℵ₁]] [[compact element]]s, but F. Wehrung provided a counterexample for distributive lattices with ℵ₂ compact elements using a construction based on [[Kuratowski's free set theorem]].

Line 7 ⟶ 8:

'''Lemma.'''

A congruence of an [[Universal algebra|algebra]] ''A'' is finitely generated [[if and only if]] it is a [[compact element]] of Con ''A''.

As every congruence of an algebra is the join of the finitely generated congruences below it (e.g., every [[Module (mathematics)|submodule]] of a [[module (mathematics)|module]] is the union of all its finitely generated submodules), we obtain the following result, first published by Birkhoff and Frink in 1948.{{sfn|Birkhoff|Frink|1948}}

Line 26 ⟶ 27:

Every finite distributive lattice is isomorphic to the congruence lattice of some finite lattice.

It is important to observe that the solution lattice found in Grätzer and Schmidt's proof is ''sectionally complemented'', that is, it has a [[Greatest element and least element|least element]] (true for any finite lattice) and for all elements ''a'' ≤ ''b'' there exists an element ''x'' with ''a'' ∨ ''x'' = ''b'' and ''a'' ∧ ''x'' = ''0''. It is also in that paper that CLP is first stated in published form, although it seems that the earliest attempts at CLP were made by Dilworth himself. Congruence lattices of finite lattices have been given an enormous amount of attention, for which a reference is Grätzer's 2005 monograph.{{sfn|Grätzer|2005}}

----

Line 65 ⟶ 66:

'''Theorem.'''

The [[functor]] Con_c, defined on all algebras of a given [[signature (logic)|signature]], to all (∨,0)-semilattices, [[Limit (category theory)|preserves direct limits]].

==Schmidt's approach via distributive join-homomorphisms==

Line 196 ⟶ 197:

By building on Wehrung's abovementioned work on dimension vector spaces, Ploščica and Tůma proved that WURP does not hold in ''G(Ω)'', for any set Ω of cardinality at least ℵ₂. Hence ''G(Ω)'' does not satisfy Schmidt's Condition. All negative representation results mentioned here always make use of some ''uniform refinement property'', including the first one about dimension vector spaces.

However, the semilattices used in these negative results are relatively complicated. The following result, proved by Ploščica, Tůma, and Wehrung in 1998, is more striking, because it shows examples of ''representable'' semilattices that do not satisfy Schmidt's Condition. We denote by F_'''V'''(Ω) the [[free lattice]] on Ω in '''V''', for any variety '''V''' of lattices.

'''Theorem (Ploščica, Tůma, and Wehrung 1998).'''{{sfn|Ploščica|Tůma|Wehrung|1998}}

Line 211 ⟶ 212:

Hence, the counterexample to CLP had been known for nearly ten years, it is just that nobody knew why it worked! All the results prior to the theorem above made use of some form of permutability of congruences. The difficulty was to find enough structure in congruence lattices of non-congruence-permutable lattices.

We shall denote by ε the `[[parity function]]' on the natural numbers, that is, ε(''n'')=''n'' mod 2, for any natural number ''n''.

We let ''L'' be an [[Universal algebra|algebra]] possessing a structure of semilattice (''L'',∨) such that every congruence of ''L'' is also a congruence for the operation ∨ . We put

Line 228 ⟶ 229:

</math>

(Observe the faint formal similarity with [[Resolution (logic)|first-order resolution]] in [[mathematical logic]]. Could this analogy be pushed further?)

The proof of the theorem above runs by setting a ''structure'' theorem for congruence lattices of semilattices—namely, the Erosion Lemma, against ''non-structure'' theorems for free distributive extensions ''G(Ω)'', the main one being called the ''Evaporation Lemma''. While the latter are technically difficult, they are, in some sense, predictable. Quite to the contrary, the proof of the Erosion Lemma is elementary and easy, so it is probably the strangeness of its statement that explains that it has been hidden for so long.

Line 499 ⟶ 500:

| pages=497–531

| doi=10.1142/S0218196798000247| s2cid=17997536

| arxiv=math/9604246

}}

* {{cite journal

Line 658 ⟶ 660:

| date=2002

| pages=439–471

| doi=10.1007/s000120200011 | doi-access=free}}| arxiv=math/0501375

}}

* {{cite journal

| last1=Tůma | first1=Jiří

Line 708 ⟶ 711:

| date=2000

| pages=419–435

| doi=10.5565/PUBLMAT_44200_03 | doi-access=free}}| arxiv=math/0501367

}}

* {{cite journal

| last1=Wehrung | first1=Friedrich

Line 737 ⟶ 741:

| pages=321–356

| doi=10.1142/S0218196708004469| s2cid=7674741

| arxiv=math/0601058

}}

* {{cite journal

Line 746 ⟶ 751:

| date=2007

| pages=610–625

| doi=10.1016/j.aim.2007.05.016 | doi-access=free}}| arxiv=math/0601059

}}

[[Category:Lattice theory]]