Congruence lattice problem
Encyclopedia
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 ℵ1
compact element
s, but F. Wehrung provided a counterexample for distributive lattices with ℵ2 compact elements using a construction based on Kuratowski's free set theorem.
A, that is, the lattice
of all congruences
of A under inclusion.
The following is a universal-algebraic
triviality. It says that for a congruence, being finitely generated is a lattice-theoretical property.
Lemma.
A congruence of an 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 submodule
of a module
is the union of all its finitely generated submodules), we obtain the following result, first published by Birkhoff and Frink in 1948.
Theorem (Birkhoff and Frink 1948).
The congruence lattice Con A of any algebra A is an algebraic lattice
.
While congruences of lattices lose something in comparison to groups
, modules
, rings
(they cannot be identified with subset
s of the universe), they also have a property unique among all the other structures encountered yet.
Theorem (Funayama and Nakayama 1942).
The congruence lattice of any lattice is distributive
.
This says that α ∧ (β ∨ γ) = (α ∧ β) ∨ (α ∧ γ), for any congruences α, β, and γ of a given lattice. The analogue of this result fails, for instance, for modules, as
, as a rule, for submodules
A, B, C of a given module
.
Soon after this result, Dilworth
proved the following result. He did not publish the result but it appears as an exercise credited to him in Birkhoff 1948. The first published proof is in Grätzer and Schmidt 1962.
Theorem (Dilworth ≈1940, Grätzer and Schmidt 1962).
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 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.
----
The congruence lattice problem (CLP):
Is every distributive algebraic lattice isomorphic to the congruence lattice of some lattice?
----
The problem CLP has been one of the most intriguing and longest-standing open problems of lattice theory. Some related results of universal algebra are the following.
Theorem (Grätzer and Schmidt 1963).
Every algebraic lattice is isomorphic to the congruence lattice of some algebra.
The lattice Sub V of all subspaces of a vector space
V is certainly an algebraic lattice. As the next result shows, these algebraic lattices are difficult to represent.
Theorem (Freese, Lampe, and Taylor 1979).
Let V be an infinite-dimensional vector space over an uncountable field
F. Then Con A isomorphic to Sub V implies that A has at least card F operations, for any algebra A.
As V is infinite-dimensional, the largest element (unit) of Sub V is not compact. However innocuous it sounds, the compact unit assumption is essential in the statement of the result above, as demonstrated by the following result.
Theorem (Lampe 1982).
Every algebraic lattice with compact unit is isomorphic to the congruence lattice of some groupoid
.
A is an algebraic lattice
. The (∨,0)-semilattice
of compact element
s of Con A is denoted by Conc A, and it is sometimes called the congruence semilattice of A. Then Con A is isomorphic to the ideal lattice
of Conc A. By using the classical equivalence
between the category of all (∨,0)-semilattices and the category of all algebraic lattices (with suitable definitions of morphisms), as it is outlined here
, we obtain the following semilattice-theoretical formulation of CLP.
----
Semilattice-theoretical formulation of CLP:
Is every distributive
(∨,0)-semilattice isomorphic to the congruence semilattice of some lattice?
----
Say that a distributive (∨,0)-semilattice is representable, if it is isomorphic to Conc L, for some lattice L. So CLP asks whether every distributive (∨,0)-semilattice is representable.
Many investigations around this problem involve diagrams of semilattices or of algebras. A most useful folklore result about these is the following.
Theorem.
The functor Conc, defined on all algebras of a given signature
, to all (∨,0)-semilattices, preserves direct limits
.
of B. One of the deepest results about representability of (∨,0)-semilattices is the following.
Theorem (Schmidt 1968).
Any (∨,0)-semilattice satisfying Schmidt's Condition is representable.
This raised the following problem, stated in the same paper.
----
Problem 1 (Schmidt 1968).
Does any (∨,0)-semilattice satisfiy Schmidt's Condition?
----
Partial positive answers are the following.
Theorem (Schmidt 1981).
Every distributive lattice with zero satisfies Schmidt's Condition; thus it is representable.
This result has been improved further as follows, via a very long and technical proof, using forcing and Boolean-valued models.
Theorem (Wehrung 2003).
Every direct limit
of a countable sequence of distributive lattices with zero and (∨,0)-homomorphisms is representable.
Other important representability results are related to the cardinality of the semilattice. The following result was prepared for publication by Dobbertin after Huhn's passing away in 1985. The two corresponding papers were published in 1989.
Theorem (Huhn 1985). Every distributive (∨,0)-semilattice of cardinality at most ℵ1 satisfies Schmidt's Condition. Thus it is representable.
By using different methods, Dobbertin got the following result.
Theorem (Dobbertin 1986).
Every distributive (∨,0)-semilattice in which every principal ideal
is at most countable is representable.
----
Problem 2 (Dobbertin 1983). Is every conical refinement monoid measurable
?
----
Theorem (Ershov 1977, Pudlák 1985).
Every distributive (∨,0)-semilattice is the directed union of its finite distributive (∨,0)-subsemilattices.
This means that every finite subset in a distributive (∨,0)-semilattice S is contained in some finite distributive (∨,0)-subsemilattice of S. Now we are trying to represent a given distributive (∨,0)-semilattice S as Conc L, for some lattice L. Writing S as a directed union
of finite distributive (∨,0)-subsemilattices, we are hoping to represent each Si as the congruence lattice of a lattice Li with lattice homomorphisms fij : Li→ Lj, for i ≤ j in I, such that the diagram 
of all Si with all inclusion maps Si→Sj, for i ≤ j in I, is naturally equivalent
to
, we say that the diagram 
lifts 
(with respect to the Conc functor). If this can be done, then, as we have seen that the Conc functor preserves direct limits, the direct limit 
satisfies 
.
While the problem whether this could be done in general remained open for about 20 years, Pudlák could prove it for distributive lattices with zero, thus extending one of Schmidt's results by providing a functorial solution.
Theorem (Pudlák 1985).
There exists a direct limits preserving functor Φ, from the category of all distributive lattices with zero and 0-lattice embeddings to the category of all lattices with zero and 0-lattice embeddings, such that ConcΦ is naturally equivalent
to the identity. Furthermore, Φ(S) is a finite atomistic lattice
, for any finite distributive (∨,0)-semilattice S.
This result is improved further, by an even far more complex construction, to locally finite, sectionally complemented modular lattices by Růžička in 2004 and 2006.
Pudlák asked in 1985 whether his result above could be extended to the whole category of distributive (∨,0)-semilattices with (∨,0)-embeddings. The problem remained open until it was recently solved in the negative by Tůma and Wehrung.
Theorem (Tůma and Wehrung 2006).
There exists a diagram
D of finite Boolean (∨,0)-semilattices and (∨,0,1)-embeddings, indexed by a finite partially ordered set, that cannot be lifted, with respect to the Conc functor, by any diagram of lattices and lattice homomorphisms.
In particular, this implies immediately that CLP has no functorial solution.
Furthermore, it follows from deep 1998 results of universal algebra by Kearnes and Szendrei in so-called commutator theory of varieties that the result above can be extended from the variety of all lattices to any variety
such that all Con A, for 
, satisfy a fixed nontrivial identity in the signature (∨,∧) (in short, with a nontrivial congruence identity).
We should also mention that many attempts at CLP were also based on the following result, first proved by Bulman-Fleming and McDowell in 1978 by using a categorical 1974 result of Shannon, see also Goodearl and Wehrung in 2001 for a direct argument.
Theorem (Bulman-Fleming and McDowell 1978).
Every distributive (∨,0)-semilattice is a direct limit of finite Boolean (∨,0)-semilattices and (∨,0)-homomorphisms.
It should be observed that while the transition homomorphisms used in the Ershov-Pudlák Theorem are (∨,0)-embeddings, the transition homomorphisms used in the result above are not necessarily one-to-one, for example when one tries to represent the three-element chain. Practically this does not cause much trouble, and makes it possible to prove the following results.
Theorem.
Every distributive (∨,0)-semilattice of cardinality at most ℵ1 is isomorphic to
(1) Conc L, for some locally finite, relatively complemented modular lattice L (Tůma 1998 and Grätzer, Lakser, and Wehrung 2000).
(2) The semilattice of finitely generated two-sided ideals of some (not necessarily unital) von Neumann regular ring (Wehrung 2000).
(3) Conc L, for some sectionally complemented modular lattice L (Wehrung 2000).
(4) The semilattice of finitely generated normal subgroup
s of some locally finite group
(Růžička, Tůma, and Wehrung 2006).
(5) The submodule lattice of some right module over a (non-commutative) ring (Růžička, Tůma, and Wehrung 2006).
R, we denote by V(R) the (conical, commutative) monoid of isomorphism classes of finitely generated projective right R-modules, see here
for more details. Recall that if R is von Neumann regular
, then V(R) is a refinement monoid
. Denote by Idc R the (∨,0)-semilattice of finitely generated two-sided ideals
of R. We denote by L(R) the lattice of all principal right ideals of a von Neumann regular ring R. It is well-known that L(R) is a complemented
modular lattice
.
The following result was observed by Wehrung, building on earlier works mainly by Jónsson and Goodearl.
Theorem (Wehrung 1999).
Let R be a von Neumann regular ring. Then the (∨,0)-semilattices Idc R and Conc L(R) are both isomorphic to the maximal semilattice quotient
of V(R).
Bergman proves in a well-known unpublished note from 1986 that any at most countable distributive (∨,0)-semilattice is isomorphic to Idc R, for some locally matricial
ring R (over any given field). This result is extended to semilattices of cardinality at most ℵ1 in 2000 by Wehrung, by keeping only the regularity of R (the ring constructed by the proof is not locally matricial). The question whether R could be taken locally matricial in the ℵ1 case remained open for a while, until it was disproved by Wehrung in 2004. Translating back to the lattice world by using the theorem above and using a lattice-theoretical analogue of the V(R) construction, called the dimension monoid, introduced by Wehrung in 1998, yields the following result.
Theorem (Wehrung 2004).
There exists a distributive (∨,0,1)-semilattice of cardinality ℵ1 that is not isomorphic to Conc L, for any modular lattice L every finitely generated sublattice of which has finite length.
----
Problem 3 (Goodearl 1991). Is the positive cone of any dimension group
with order-unit
isomorphic to V(R), for some von Neumann regular ring R?
----
Theorem (Wehrung 1998).
There exists a dimension vector space
G over the rationals with order-unit
whose positive cone G+ is not isomorphic to V(R), for any von Neumann regular ring R, and is not measurable
in Dobbertin's sense. Furthermore, the maximal semilattice quotient
of G+ does not satisfy Schmidt's Condition. Furthermore, G can be taken of any given cardinality greater than or equal to ℵ2.
It follows from the previously mentioned works of Schmidt, Huhn, Dobbertin, Goodearl, and Handelman that the ℵ2 bound is optimal in all three negative results above.
As the ℵ2 bound suggests, infinite combinatorics are involved. The principle used is Kuratowski's Free Set Theorem, 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 ℵ2 that does not satisfy URP (which is difficult, and uses Kuratowski's Free Set Theorem).
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 ai,x, for i<2 and x in Ω, and relations a0,x+a1,x=1, a0,x ≥ 0, and a1,x ≥ 0, for any x in Ω. By using a Skolemization of the theory of dimension groups, we can embed E(Ω) functorially into a dimension vector space
F(Ω). The vector space counterexample of the theorem above is G=F(Ω), for any set Ω with at least ℵ2 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
of S. Now, for a set Ω, let L(Ω) be the (∨,0)-semilattice defined by generators 1 and ai,x, for i<2 and x in Ω, and relations a0,x ∨ a1,x=1, for any x in Ω. Finally, put G(Ω)=D(L(Ω)).
In most related works, the following uniform refinement property is used. It is a modification of the one introduced by Wehrung in 1998 and 1999.
Definition (Ploščica, Tůma, and Wehrung 1998).
Let e be an element in a (∨,0)-semilattice S. We say that the weak uniform refinement property WURP holds at e, if for all families
and 
of elements in S such that ai ∨ bi=e for all i in I, there exists a family 
of elements of S such that the relations
• ci,j ≤ ai,bj,
• ci,j ∨ aj ∨ bi=e,
• ci,k ≤ ci,j∨ cj,k
hold for all i, j, k in I. We say that S satisfies WURP, if WURP holds at every element of S.
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 ℵ2. Hence G(Ω) does not satisfy Schmidt's Condition. It is to be noted that 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 FV(Ω) the free lattice on Ω in V, for any variety V of lattices.
Theorem (Ploščica, Tůma, and Wehrung 1998).
The semilattice Conc FV(Ω) does not satisfy WURP, for any set Ω of cardinality at least ℵ2 and any non-distributive variety V of lattices. Consequently, Conc FV(Ω) does not satisfy Schmidt's Condition.
It is proved by Tůma and Wehrung in 2001 that Conc FV(Ω) is not isomorphic to Conc L, for any lattice L with permutable congruences. By using a slight weakening of WURP, this result is extended to arbitrary algebras
with permutable congruences by Růžička, Tůma, and Wehrung in 2006. Hence, for example, if Ω has at least ℵ2 elements, then Conc FV(Ω) is not isomorphic to the normal subgroup lattice of any group, or the submodule lattice of any module.
Theorem (Wehrung 2007).
The semilattice G(Ω) is not isomorphic to Conc L for any lattice L, whenever the set Ω has at least ℵω+1 elements.
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 algebra
possessing a structure of semilattice (L,∨) such that every congruence of L is also a congruence for the operation ∨ . We put
and we denote by ConcU L the (∨,0)-subsemilattice of Conc L generated by all principal congruences Θ(u,v) ( = least congruence of L that identifies u and v), where (u,v) belongs to U ×U. We put Θ+(u,v)=Θ(u ∨ v,v), for all u, v in L.br />
The Erosion Lemma (Wehrung 2007).
Let x0, x1 in L and let
, for a positive integer n, be a finite subset of L with 
. Put
Then there are congruences
, for j<2, such that
(Observe the faint formal similarity with 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.
More is, in fact, proved in the theorem above: For any algebra L with a congruence-compatible structure of join-semilattice with unit and for any set Ω with at least ℵω+1 elements, there is no weakly distributive homomorphism μ: Conc L → G(Ω) containing 1 in its range. In particular, CLP was, after all, not a problem of lattice theory, but rather of universal algebra
—even more specifically, semilattice theory
! These results can also be translated in terms of a uniform refinement property, denoted by CLR in Wehrung's paper presenting the solution of CLP, which is noticeably more complicated than WURP.
Finally, the cardinality bound ℵω+1 has been improved to the optimal bound ℵ2 by Růžička.
Theorem (Růžička 2008).
The semilattice G(Ω) is not isomorphic to Conc L for any lattice L, whenever the set Ω has at least ℵ2 elements.
Růžička's proof follows the main lines of Wehrung's proof, except that it introduces an enhancement of Kuratowski's Free Set Theorem, called there existence of free trees, which it uses in the final argument involving the Erosion Lemma.
would cause similar problems is answered by the following result.
Theorem (Wehrung 2008). For any distributive (∨,0)-semilattice S, there are a (∧,0)-semilattice P and a map μ : P × P → S such that the following conditions hold:
(1) x ≤ y implies that μ(x,y)=0, for all x, y in P.
(2) μ(x,z) ≤ μ(x,y) ∨ μ(y,z), for all x, y, z in P.
(3) For all x ≥ y in P and all α, β in S such that μ(x,y) ≤ α ∨ β, there are a positive integer n and elements x=z0 ≥ z1 ≥ ... ≥ z2n=y such that μ(zi,zi+1) ≤ α (resp., μ(zi,zi+1) ≤ β) whenever i < 2n is even (resp., odd).
(4) S is generated, as a join-semilattice, by all the elements of the form μ(x,0), for x in P.
Furthermore, if S has a largest element, then P can be assumed to be a lattice with a largest element.
It is not hard to verify that conditions (1)–(4) above imply the distributivity of S, so the result above gives a characterization of distributivity for (∨,0)-semilattices.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the congruence lattice problem asks whether every algebraic distributive lattice
Distributive lattice
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
is isomorphic to the congruence lattice of some other lattice. The problem was posed by Robert P. Dilworth
Robert P. Dilworth
Robert Palmer Dilworth was an American mathematician. His primary research area was lattice theory; his biography at the MacTutor History of Mathematics archive states "it would not be an exaggeration to say that he was one of the main factors in the subject moving from being merely a tool of...
, 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 ℵ1
Aleph number
In set theory, a discipline within mathematics, the aleph numbers are a sequence of numbers used to represent the cardinality of infinite sets. They are named after the symbol used to denote them, the Hebrew letter aleph...
compact element
Compact element
In the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element....
s, but F. Wehrung provided a counterexample for distributive lattices with ℵ2 compact elements using a construction based on Kuratowski's free set theorem.
Preliminaries
We denote by Con A the congruence lattice of an algebraUniversal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
A, that is, the lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
of all congruences
Congruence relation
In abstract algebra, a congruence relation is an equivalence relation on an algebraic structure that is compatible with the structure...
of A under inclusion.
The following is a universal-algebraic
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
triviality. It says that for a congruence, being finitely generated is a lattice-theoretical property.
Lemma.
A congruence of an algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
A is finitely generated if and only if it is a compact element
Compact element
In the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element....
of Con A.
As every congruence of an algebra is the join of the finitely generated congruences below it (e.g., every submodule
Module (mathematics)
In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, wherein the corresponding scalars are allowed to lie in an arbitrary ring...
of a module
Module (mathematics)
In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, wherein the corresponding scalars are allowed to lie in an arbitrary ring...
is the union of all its finitely generated submodules), we obtain the following result, first published by Birkhoff and Frink in 1948.
Theorem (Birkhoff and Frink 1948).
The congruence lattice Con A of any algebra A is an algebraic lattice
Compact element
In the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element....
.
While congruences of lattices lose something in comparison to groups
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
, modules
Module (mathematics)
In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, wherein the corresponding scalars are allowed to lie in an arbitrary ring...
, rings
Ring (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
(they cannot be identified with subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
s of the universe), they also have a property unique among all the other structures encountered yet.
Theorem (Funayama and Nakayama 1942).
The congruence lattice of any lattice is distributive
Distributive lattice
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
.
This says that α ∧ (β ∨ γ) = (α ∧ β) ∨ (α ∧ γ), for any congruences α, β, and γ of a given lattice. The analogue of this result fails, for instance, for modules, as
, as a rule, for submodulesModule (mathematics)
In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, wherein the corresponding scalars are allowed to lie in an arbitrary ring...
A, B, C of a given module
Module (mathematics)
In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, wherein the corresponding scalars are allowed to lie in an arbitrary ring...
.
Soon after this result, Dilworth
Robert P. Dilworth
Robert Palmer Dilworth was an American mathematician. His primary research area was lattice theory; his biography at the MacTutor History of Mathematics archive states "it would not be an exaggeration to say that he was one of the main factors in the subject moving from being merely a tool of...
proved the following result. He did not publish the result but it appears as an exercise credited to him in Birkhoff 1948. The first published proof is in Grätzer and Schmidt 1962.
Theorem (Dilworth ≈1940, Grätzer and Schmidt 1962).
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 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.
----
The congruence lattice problem (CLP):
Is every distributive algebraic lattice isomorphic to the congruence lattice of some lattice?
----
The problem CLP has been one of the most intriguing and longest-standing open problems of lattice theory. Some related results of universal algebra are the following.
Theorem (Grätzer and Schmidt 1963).
Every algebraic lattice is isomorphic to the congruence lattice of some algebra.
The lattice Sub V of all subspaces of a vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
V is certainly an algebraic lattice. As the next result shows, these algebraic lattices are difficult to represent.
Theorem (Freese, Lampe, and Taylor 1979).
Let V be an infinite-dimensional vector space over an uncountable field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
F. Then Con A isomorphic to Sub V implies that A has at least card F operations, for any algebra A.
As V is infinite-dimensional, the largest element (unit) of Sub V is not compact. However innocuous it sounds, the compact unit assumption is essential in the statement of the result above, as demonstrated by the following result.
Theorem (Lampe 1982).
Every algebraic lattice with compact unit is isomorphic to the congruence lattice of some groupoid
Magma (algebra)
In abstract algebra, a magma is a basic kind of algebraic structure. Specifically, a magma consists of a set M equipped with a single binary operation M \times M \rightarrow M....
.
Semilattice formulation of CLP
The congruence lattice Con A of an algebraUniversal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
A is an algebraic lattice
Compact element
In the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element....
. The (∨,0)-semilattice
Semilattice
In mathematics, a join-semilattice is a partially ordered set which has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset...
of compact element
Compact element
In the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element....
s of Con A is denoted by Conc A, and it is sometimes called the congruence semilattice of A. Then Con A is isomorphic to the ideal lattice
Ideal (order theory)
In mathematical order theory, an ideal is a special subset of a partially ordered set . Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion...
of Conc A. By using the classical equivalence
Equivalence of categories
In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are "essentially the same". There are numerous examples of categorical equivalences from many areas of mathematics...
between the category of all (∨,0)-semilattices and the category of all algebraic lattices (with suitable definitions of morphisms), as it is outlined here
Semilattice
In mathematics, a join-semilattice is a partially ordered set which has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset...
, we obtain the following semilattice-theoretical formulation of CLP.
----
Semilattice-theoretical formulation of CLP:
Is every distributive
Distributivity (order theory)
In the mathematical area of order theory, there are various notions of the common concept of distributivity, applied to the formation of suprema and infima...
(∨,0)-semilattice isomorphic to the congruence semilattice of some lattice?
----
Say that a distributive (∨,0)-semilattice is representable, if it is isomorphic to Conc L, for some lattice L. So CLP asks whether every distributive (∨,0)-semilattice is representable.
Many investigations around this problem involve diagrams of semilattices or of algebras. A most useful folklore result about these is the following.
Theorem.
The functor Conc, defined on all algebras of a given signature
Signature (logic)
In logic, especially mathematical logic, a signature lists and describes the non-logical symbols of a formal language. In universal algebra, a signature lists the operations that characterize an algebraic structure. In model theory, signatures are used for both purposes.Signatures play the same...
, to all (∨,0)-semilattices, preserves direct limits
Limit (category theory)
In category theory, a branch of mathematics, the abstract notion of a limit captures the essential properties of universal constructions such as products and inverse limits....
.
Schmidt's approach via distributive join-homomorphisms
We say that a (∨,0)-semilattice satisfies Schmidt's Condition, if it is isomorphic to the quotient of a generalized Boolean semilattice B under some distributive join-congruenceDistributive homomorphism
A congruence θ of a join-semilattice S is monomial, if the θ-equivalence class of any element of S has a largest element. We say that θ is distributive, if it is a join, in the congruence lattice Con S of S, of monomial join-congruences of S.The following definition originates in...
of B. One of the deepest results about representability of (∨,0)-semilattices is the following.
Theorem (Schmidt 1968).
Any (∨,0)-semilattice satisfying Schmidt's Condition is representable.
This raised the following problem, stated in the same paper.
----
Problem 1 (Schmidt 1968).
Does any (∨,0)-semilattice satisfiy Schmidt's Condition?
----
Partial positive answers are the following.
Theorem (Schmidt 1981).
Every distributive lattice with zero satisfies Schmidt's Condition; thus it is representable.
This result has been improved further as follows, via a very long and technical proof, using forcing and Boolean-valued models.
Theorem (Wehrung 2003).
Every direct limit
Direct limit
In mathematics, a direct limit is a colimit of a "directed family of objects". We will first give the definition for algebraic structures like groups and modules, and then the general definition which can be used in any category.- Algebraic objects :In this section objects are understood to be...
of a countable sequence of distributive lattices with zero and (∨,0)-homomorphisms is representable.
Other important representability results are related to the cardinality of the semilattice. The following result was prepared for publication by Dobbertin after Huhn's passing away in 1985. The two corresponding papers were published in 1989.
Theorem (Huhn 1985). Every distributive (∨,0)-semilattice of cardinality at most ℵ1 satisfies Schmidt's Condition. Thus it is representable.
By using different methods, Dobbertin got the following result.
Theorem (Dobbertin 1986).
Every distributive (∨,0)-semilattice in which every principal ideal
Ideal (order theory)
In mathematical order theory, an ideal is a special subset of a partially ordered set . Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion...
is at most countable is representable.
----
Problem 2 (Dobbertin 1983). Is every conical refinement monoid measurable
Refinement monoid
In mathematics, a refinement monoid is a commutative monoid M such that for any elements a0, a1, b0, b1 of M such that a0+a1=b0+b1, there are elements c00, c01, c10, c11 of M such that a0=c00+c01, a1=c10+c11, b0=c00+c10, and b1=c01+c11.A commutative monoid M is conical, if x+y=0 implies that x=y=0,...
?
----
Pudlák's approach; lifting diagrams of (∨,0)-semilattices
The approach of CLP suggested by Pudlák in his 1985 paper is different. It is based on the following result, Fact 4, p. 100 in Pudlák's 1985 paper, obtained earlier by Ju.L. Ershov as the main theorem in Section 3 of the Introduction of his 1977 monograph.Theorem (Ershov 1977, Pudlák 1985).
Every distributive (∨,0)-semilattice is the directed union of its finite distributive (∨,0)-subsemilattices.
This means that every finite subset in a distributive (∨,0)-semilattice S is contained in some finite distributive (∨,0)-subsemilattice of S. Now we are trying to represent a given distributive (∨,0)-semilattice S as Conc L, for some lattice L. Writing S as a directed union
of finite distributive (∨,0)-subsemilattices, we are hoping to represent each Si as the congruence lattice of a lattice Li with lattice homomorphisms fij : Li→ Lj, for i ≤ j in I, such that the diagram of all Si with all inclusion maps Si→Sj, for i ≤ j in I, is naturally equivalentEquivalence of categories
In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are "essentially the same". There are numerous examples of categorical equivalences from many areas of mathematics...
to
, we say that the diagram lifts (with respect to the Conc functor). If this can be done, then, as we have seen that the Conc functor preserves direct limits, the direct limit satisfies .While the problem whether this could be done in general remained open for about 20 years, Pudlák could prove it for distributive lattices with zero, thus extending one of Schmidt's results by providing a functorial solution.
Theorem (Pudlák 1985).
There exists a direct limits preserving functor Φ, from the category of all distributive lattices with zero and 0-lattice embeddings to the category of all lattices with zero and 0-lattice embeddings, such that ConcΦ is naturally equivalent
Equivalence of categories
In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are "essentially the same". There are numerous examples of categorical equivalences from many areas of mathematics...
to the identity. Furthermore, Φ(S) is a finite atomistic lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
, for any finite distributive (∨,0)-semilattice S.
This result is improved further, by an even far more complex construction, to locally finite, sectionally complemented modular lattices by Růžička in 2004 and 2006.
Pudlák asked in 1985 whether his result above could be extended to the whole category of distributive (∨,0)-semilattices with (∨,0)-embeddings. The problem remained open until it was recently solved in the negative by Tůma and Wehrung.
Theorem (Tůma and Wehrung 2006).
There exists a diagram
Diagram (category theory)
In category theory, a branch of mathematics, a diagram is the categorical analogue of an indexed family in set theory. The primary difference is that in the categorical setting one has morphisms. An indexed family of sets is a collection of sets, indexed by a fixed set; equivalently, a function...
D of finite Boolean (∨,0)-semilattices and (∨,0,1)-embeddings, indexed by a finite partially ordered set, that cannot be lifted, with respect to the Conc functor, by any diagram of lattices and lattice homomorphisms.
In particular, this implies immediately that CLP has no functorial solution.
Furthermore, it follows from deep 1998 results of universal algebra by Kearnes and Szendrei in so-called commutator theory of varieties that the result above can be extended from the variety of all lattices to any variety
such that all Con A, for , satisfy a fixed nontrivial identity in the signature (∨,∧) (in short, with a nontrivial congruence identity).We should also mention that many attempts at CLP were also based on the following result, first proved by Bulman-Fleming and McDowell in 1978 by using a categorical 1974 result of Shannon, see also Goodearl and Wehrung in 2001 for a direct argument.
Theorem (Bulman-Fleming and McDowell 1978).
Every distributive (∨,0)-semilattice is a direct limit of finite Boolean (∨,0)-semilattices and (∨,0)-homomorphisms.
It should be observed that while the transition homomorphisms used in the Ershov-Pudlák Theorem are (∨,0)-embeddings, the transition homomorphisms used in the result above are not necessarily one-to-one, for example when one tries to represent the three-element chain. Practically this does not cause much trouble, and makes it possible to prove the following results.
Theorem.
Every distributive (∨,0)-semilattice of cardinality at most ℵ1 is isomorphic to
(1) Conc L, for some locally finite, relatively complemented modular lattice L (Tůma 1998 and Grätzer, Lakser, and Wehrung 2000).
(2) The semilattice of finitely generated two-sided ideals of some (not necessarily unital) von Neumann regular ring (Wehrung 2000).
(3) Conc L, for some sectionally complemented modular lattice L (Wehrung 2000).
(4) The semilattice of finitely generated normal subgroup
Normal subgroup
In abstract algebra, a normal subgroup is a subgroup which is invariant under conjugation by members of the group. Normal subgroups can be used to construct quotient groups from a given group....
s of some locally finite group
Locally finite group
In mathematics, in the field of group theory, a locally finite group is a type of group that can be studied in ways analogous to a finite group. Sylow subgroups, Carter subgroups, and abelian subgroups of locally finite groups have been studied....
(Růžička, Tůma, and Wehrung 2006).
(5) The submodule lattice of some right module over a (non-commutative) ring (Růžička, Tůma, and Wehrung 2006).
Congruence lattices of lattices and nonstable K-theory of von Neumann regular rings
We recall that for a (unital, associative) ringRing (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
R, we denote by V(R) the (conical, commutative) monoid of isomorphism classes of finitely generated projective right R-modules, see here
Refinement monoid
In mathematics, a refinement monoid is a commutative monoid M such that for any elements a0, a1, b0, b1 of M such that a0+a1=b0+b1, there are elements c00, c01, c10, c11 of M such that a0=c00+c01, a1=c10+c11, b0=c00+c10, and b1=c01+c11.A commutative monoid M is conical, if x+y=0 implies that x=y=0,...
for more details. Recall that if R is von Neumann regular
Von Neumann regular ring
In mathematics, a von Neumann regular ring is a ring R such that for every a in R there exists an x in R withOne may think of x as a "weak inverse" of a...
, then V(R) is a refinement monoid
Refinement monoid
In mathematics, a refinement monoid is a commutative monoid M such that for any elements a0, a1, b0, b1 of M such that a0+a1=b0+b1, there are elements c00, c01, c10, c11 of M such that a0=c00+c01, a1=c10+c11, b0=c00+c10, and b1=c01+c11.A commutative monoid M is conical, if x+y=0 implies that x=y=0,...
. Denote by Idc R the (∨,0)-semilattice of finitely generated two-sided ideals
Ideal (ring theory)
In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring. The ideal concept allows the generalization in an appropriate way of some important properties of integers like "even number" or "multiple of 3"....
of R. We denote by L(R) the lattice of all principal right ideals of a von Neumann regular ring R. It is well-known that L(R) is a complemented
Complemented lattice
In the mathematical discipline of order theory, a complemented lattice is a bounded lattice in which every element a has a complement, i.e. an element b satisfying a ∨ b = 1 and a ∧ b = 0....
modular lattice
Modular lattice
In the branch of mathematics called order theory, a modular lattice is a lattice that satisfies the following self-dual condition:Modular law: x ≤ b implies x ∨ = ∧ b,where ≤ is the partial order, and ∨ and ∧ are...
.
The following result was observed by Wehrung, building on earlier works mainly by Jónsson and Goodearl.
Theorem (Wehrung 1999).
Let R be a von Neumann regular ring. Then the (∨,0)-semilattices Idc R and Conc L(R) are both isomorphic to the maximal semilattice quotient
Maximal semilattice quotient
In abstract algebra, a branch of mathematics, a maximal semilattice quotient is a commutative monoid derived from another commutative monoid by making certain elements equivalent to each other....
of V(R).
Bergman proves in a well-known unpublished note from 1986 that any at most countable distributive (∨,0)-semilattice is isomorphic to Idc R, for some locally matricial
Refinement monoid
In mathematics, a refinement monoid is a commutative monoid M such that for any elements a0, a1, b0, b1 of M such that a0+a1=b0+b1, there are elements c00, c01, c10, c11 of M such that a0=c00+c01, a1=c10+c11, b0=c00+c10, and b1=c01+c11.A commutative monoid M is conical, if x+y=0 implies that x=y=0,...
ring R (over any given field). This result is extended to semilattices of cardinality at most ℵ1 in 2000 by Wehrung, by keeping only the regularity of R (the ring constructed by the proof is not locally matricial). The question whether R could be taken locally matricial in the ℵ1 case remained open for a while, until it was disproved by Wehrung in 2004. Translating back to the lattice world by using the theorem above and using a lattice-theoretical analogue of the V(R) construction, called the dimension monoid, introduced by Wehrung in 1998, yields the following result.
Theorem (Wehrung 2004).
There exists a distributive (∨,0,1)-semilattice of cardinality ℵ1 that is not isomorphic to Conc L, for any modular lattice L every finitely generated sublattice of which has finite length.
----
Problem 3 (Goodearl 1991). Is the positive cone of any dimension group
Refinement monoid
In mathematics, a refinement monoid is a commutative monoid M such that for any elements a0, a1, b0, b1 of M such that a0+a1=b0+b1, there are elements c00, c01, c10, c11 of M such that a0=c00+c01, a1=c10+c11, b0=c00+c10, and b1=c01+c11.A commutative monoid M is conical, if x+y=0 implies that x=y=0,...
with order-unit
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
isomorphic to V(R), for some von Neumann regular ring R?
----
A first application of Kuratowski's Free Set Theorem
The abovementioned Problem 1 (Schmidt), Problem 2 (Dobbertin), and Problem 3 (Goodearl) were solved simultaneously in the negative in 1998.Theorem (Wehrung 1998).
There exists a dimension vector space
Refinement monoid
In mathematics, a refinement monoid is a commutative monoid M such that for any elements a0, a1, b0, b1 of M such that a0+a1=b0+b1, there are elements c00, c01, c10, c11 of M such that a0=c00+c01, a1=c10+c11, b0=c00+c10, and b1=c01+c11.A commutative monoid M is conical, if x+y=0 implies that x=y=0,...
G over the rationals with order-unit
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
whose positive cone G+ is not isomorphic to V(R), for any von Neumann regular ring R, and is not measurable
Refinement monoid
In mathematics, a refinement monoid is a commutative monoid M such that for any elements a0, a1, b0, b1 of M such that a0+a1=b0+b1, there are elements c00, c01, c10, c11 of M such that a0=c00+c01, a1=c10+c11, b0=c00+c10, and b1=c01+c11.A commutative monoid M is conical, if x+y=0 implies that x=y=0,...
in Dobbertin's sense. Furthermore, the maximal semilattice quotient
Maximal semilattice quotient
In abstract algebra, a branch of mathematics, a maximal semilattice quotient is a commutative monoid derived from another commutative monoid by making certain elements equivalent to each other....
of G+ does not satisfy Schmidt's Condition. Furthermore, G can be taken of any given cardinality greater than or equal to ℵ2.
It follows from the previously mentioned works of Schmidt, Huhn, Dobbertin, Goodearl, and Handelman that the ℵ2 bound is optimal in all three negative results above.
As the ℵ2 bound suggests, infinite combinatorics are involved. The principle used is Kuratowski's Free Set Theorem, 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 ℵ2 that does not satisfy URP (which is difficult, and uses Kuratowski's Free Set Theorem).
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 ai,x, for i<2 and x in Ω, and relations a0,x+a1,x=1, a0,x ≥ 0, and a1,x ≥ 0, for any x in Ω. By using a Skolemization of the theory of dimension groups, we can embed E(Ω) functorially into a dimension vector space
Refinement monoid
In mathematics, a refinement monoid is a commutative monoid M such that for any elements a0, a1, b0, b1 of M such that a0+a1=b0+b1, there are elements c00, c01, c10, c11 of M such that a0=c00+c01, a1=c10+c11, b0=c00+c10, and b1=c01+c11.A commutative monoid M is conical, if x+y=0 implies that x=y=0,...
F(Ω). The vector space counterexample of the theorem above is G=F(Ω), for any set Ω with at least ℵ2 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
of S. Now, for a set Ω, let L(Ω) be the (∨,0)-semilattice defined by generators 1 and ai,x, for i<2 and x in Ω, and relations a0,x ∨ a1,x=1, for any x in Ω. Finally, put G(Ω)=D(L(Ω)).In most related works, the following uniform refinement property is used. It is a modification of the one introduced by Wehrung in 1998 and 1999.
Definition (Ploščica, Tůma, and Wehrung 1998).
Let e be an element in a (∨,0)-semilattice S. We say that the weak uniform refinement property WURP holds at e, if for all families
and of elements in S such that ai ∨ bi=e for all i in I, there exists a family of elements of S such that the relations• ci,j ≤ ai,bj,
• ci,j ∨ aj ∨ bi=e,
• ci,k ≤ ci,j∨ cj,k
hold for all i, j, k in I. We say that S satisfies WURP, if WURP holds at every element of S.
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 ℵ2. Hence G(Ω) does not satisfy Schmidt's Condition. It is to be noted that 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 FV(Ω) the free lattice on Ω in V, for any variety V of lattices.
Theorem (Ploščica, Tůma, and Wehrung 1998).
The semilattice Conc FV(Ω) does not satisfy WURP, for any set Ω of cardinality at least ℵ2 and any non-distributive variety V of lattices. Consequently, Conc FV(Ω) does not satisfy Schmidt's Condition.
It is proved by Tůma and Wehrung in 2001 that Conc FV(Ω) is not isomorphic to Conc L, for any lattice L with permutable congruences. By using a slight weakening of WURP, this result is extended to arbitrary algebras
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
with permutable congruences by Růžička, Tůma, and Wehrung in 2006. Hence, for example, if Ω has at least ℵ2 elements, then Conc FV(Ω) is not isomorphic to the normal subgroup lattice of any group, or the submodule lattice of any module.
Solving CLP: the Erosion Lemma
The following recent theorem solves CLP.Theorem (Wehrung 2007).
The semilattice G(Ω) is not isomorphic to Conc L for any lattice L, whenever the set Ω has at least ℵω+1 elements.
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 algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
possessing a structure of semilattice (L,∨) such that every congruence of L is also a congruence for the operation ∨ . We put
and we denote by ConcU L the (∨,0)-subsemilattice of Conc L generated by all principal congruences Θ(u,v) ( = least congruence of L that identifies u and v), where (u,v) belongs to U ×U. We put Θ+(u,v)=Θ(u ∨ v,v), for all u, v in L.br />
The Erosion Lemma (Wehrung 2007).
Let x0, x1 in L and let
, for a positive integer n, be a finite subset of L with . PutThen there are congruences
, for j<2, such that(Observe the faint formal similarity with first-order resolution
Resolution (logic)
In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation theorem-proving technique for sentences in propositional logic and first-order logic...
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.
More is, in fact, proved in the theorem above: For any algebra L with a congruence-compatible structure of join-semilattice with unit and for any set Ω with at least ℵω+1 elements, there is no weakly distributive homomorphism μ: Conc L → G(Ω) containing 1 in its range. In particular, CLP was, after all, not a problem of lattice theory, but rather of universal algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
—even more specifically, semilattice theory
Semilattice
In mathematics, a join-semilattice is a partially ordered set which has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset...
! These results can also be translated in terms of a uniform refinement property, denoted by CLR in Wehrung's paper presenting the solution of CLP, which is noticeably more complicated than WURP.
Finally, the cardinality bound ℵω+1 has been improved to the optimal bound ℵ2 by Růžička.
Theorem (Růžička 2008).
The semilattice G(Ω) is not isomorphic to Conc L for any lattice L, whenever the set Ω has at least ℵ2 elements.
Růžička's proof follows the main lines of Wehrung's proof, except that it introduces an enhancement of Kuratowski's Free Set Theorem, called there existence of free trees, which it uses in the final argument involving the Erosion Lemma.
A positive representation result for distributive semilattices
The proof of the negative solution for CLP shows that the problem of representing distributive semilattices by compact congruences of lattices already appears for congruence lattices of semilattices. The question whether the structure of partially ordered setPartially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
would cause similar problems is answered by the following result.
Theorem (Wehrung 2008). For any distributive (∨,0)-semilattice S, there are a (∧,0)-semilattice P and a map μ : P × P → S such that the following conditions hold:
(1) x ≤ y implies that μ(x,y)=0, for all x, y in P.
(2) μ(x,z) ≤ μ(x,y) ∨ μ(y,z), for all x, y, z in P.
(3) For all x ≥ y in P and all α, β in S such that μ(x,y) ≤ α ∨ β, there are a positive integer n and elements x=z0 ≥ z1 ≥ ... ≥ z2n=y such that μ(zi,zi+1) ≤ α (resp., μ(zi,zi+1) ≤ β) whenever i < 2n is even (resp., odd).
(4) S is generated, as a join-semilattice, by all the elements of the form μ(x,0), for x in P.
Furthermore, if S has a largest element, then P can be assumed to be a lattice with a largest element.
It is not hard to verify that conditions (1)–(4) above imply the distributivity of S, so the result above gives a characterization of distributivity for (∨,0)-semilattices.