Congruence lattice problem: Difference between revisions

Revision as of 19:32, 6 February 2022

Latest revision as of 15:06, 27 August 2025

(9 intermediate revisions by 7 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 165 ⟶ 166:

----

==A first application of Kuratowski's Freefree Setset Theoremtheorem==

The abovementioned Problem 1 (Schmidt), Problem 2 (Dobbertin), and Problem 3 (Goodearl) were solved simultaneously in the negative in 1998.

Line 173 ⟶ 174:

It follows from the previously mentioned works of Schmidt, Huhn, Dobbertin, Goodearl, and Handelman that the ℵ₂ bound is optimal in all three negative results above.

As the ℵ₂ bound suggests, infinite combinatorics are involved. The principle used is [[Kuratowski's Freefree Setset Theoremtheorem]], first published in 1951. Only the case ''n=2'' is used here.

The semilattice part of the result above is achieved ''via'' an infinitary semilattice-theoretical statement URP (''Uniform Refinement Property''). If we want to disprove Schmidt's problem, the idea is (1) to prove that any generalized Boolean semilattice satisfies URP (which is easy), (2) that URP is preserved under homomorphic image under a weakly distributive homomorphism (which is also easy), and (3) that there exists a distributive (∨,0)-semilattice of cardinality ℵ₂ that does not satisfy URP (which is difficult, and uses Kuratowski's Freefree Setset Theoremtheorem).

Schematically, the construction in the theorem above can be described as follows. For a set Ω, we consider the partially ordered vector space ''E(Ω)'' defined by generators 1 and ''a_i,x'', for ''i<2'' and ''x'' in Ω, and relations ''a_0,x+a_1,x=1'', ''a_0,x ≥ 0'', and ''a_1,x ≥ 0'', for any ''x'' in Ω. By using a [[Skolemization]] of the theory of dimension groups, we can embed ''E(Ω)'' functorially into a [[Refinement monoid|dimension vector space]] ''F(Ω)''. The vector space counterexample of the theorem above is ''G=F(Ω)'', for any set Ω with at least ℵ₂ elements.

This counterexample has been modified subsequently by Ploščica and Tůma to a direct semilattice construction. For a (∨,0)-semilattice, the larger semilattice ''R(S)'' is the (∨,0)-semilattice freely generated by new elements ''t(a,b,c)'', for ''a, b, c'' in ''S'' such that ''c ≤ a ∨ b'', subjected to the only relations ''c=t(a,b,c) ∨ t(b,a,c)'' and ''t(a,b,c) ≤ a''. Iterating this construction gives the ''free distributive extension'' <math>D(S)=\bigcup(R^n(S)\mid n<\omega)</math> of ''S''. Now, for a set Ω, let ''L(Ω)'' be the (∨,0)-semilattice defined by generators 1 and ''a_i,x'', for ''i<2'' and ''x'' in Ω, and relations ''a_0,x ∨ a_1,x=1'', for any ''x'' in Ω. Finally, put ''G(Ω)=D(L(Ω))''.

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 265 ⟶ 266:

| last1=Bergman | first1=George M.

| title=Von Neumann regular rings with tailor-made ideal lattices

| journal=Unpublished noteNote

| date=26 October 1986

| url=https://math.berkeley.edu/~gbergman/papers/unpub/138.vNlat.pdf}}

Line 406 ⟶ 407:

| date=2001

| pages=71–102

| doi=10.1007/s000120050203 | doi-access=free}}| arxiv=math/0011083

}}

* {{cite book

| last1=Grätzer | first1=George

Line 421 ⟶ 423:

| isbn=978-0-8176-3224-3

| doi=10.1007/978-3-319-38798-7 | doi-access=free}}

* {{cite articlejournal

| last1=Grätzer | first1=George

| last2=Lakser | first2=Harry

Line 436 ⟶ 438:

| last2=Schmidt | first2=E. Tamás

| title=On congruence lattices of lattices

| journal=[[Acta Mathematica Hungarica|Acta Mathematica Academiae Scientiarum HungaricaHungaricae]]

| volume=13

| date=1962

| issue=1–2

| pages=179–185

| doi=10.1007/BF02033636 | doi-access=free}}

Line 496 ⟶ 499:

| date=1998

| pages=497–531

| doi=10.1142/S0218196798000247}}| s2cid=17997536

| arxiv=math/9604246

}}

* {{cite journal

| last1=Kuratowski | first1=Casimir | authorlink1=Kazimierz Kuratowski

| title=Sur une caractérisation des alephs

| journal=FundamentFundamenta Mathematicae

| volume=38

| date=1951

Line 522 ⟶ 527:

| date=December 1936

| pages=707–713

| doi=10.1073/pnas.22.12.707 | pmid=16577757 | pmc=1076849 | bibcode=1936PNAS...22..707V | doi-access=free}}

* {{cite conference

| last1=Ploščica | first1=Miroslav

Line 643 ⟶ 648:

| date=2001

| pages=217–246

| doi=10.1142/S0218196701000516}}| arxiv=math/0501417

| s2cid=15648638

}}

* {{cite journal

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

Line 653 ⟶ 660:

| date=2002

| pages=439–471

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

}}

* {{cite journal

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

Line 663 ⟶ 671:

| date=2006

| pages=541–550

| doi=10.1142/S0218196706003049}}| arxiv=math/0410576

| s2cid=735797

}}

* {{cite journal

| last1=Wehrung | first1=Friedrich

Line 680 ⟶ 690:

| date=1998b

| pages=247–411

| doi=10.1007/s000120050091 | doi-access=free}}| arxiv=math/0501437

}}

* {{cite journal

| last1=Wehrung | first1=Friedrich

Line 689 ⟶ 700:

| date=1999

| pages=363–370

| doi=10.1090/S0002-9939-99-04558-X

| s2cid=85539753

| url=https://www.ams.org/journals/proc/1999-127-02/S0002-9939-99-04558-X/S0002-9939-99-04558-X.pdf}}

* {{cite journal

Line 698 ⟶ 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 707 ⟶ 721:

| date=2003

| pages=127–193

| doi=10.1016/S0021-8693(03)00015-2 | doi-access=free}}| arxiv=math/0501378

}}

* {{cite journal

| last1=Wehrung | first1=Friedrich

Line 725 ⟶ 740:

| date=2008

| pages=321–356

| doi=10.1142/S0218196708004469}}| s2cid=7674741

| arxiv=math/0601058

}}

* {{cite journal

| last1=Wehrung | first1=Friedrich

Line 734 ⟶ 751:

| date=2007

| pages=610–625

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

}}

[[Category:Lattice theory]]