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 elements, 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 algebra 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 subsets 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.
Semilattice formulation of CLP The congruence lattice Con A of an algebra A is an algebraic lattice. The (∨,0)-semilattice of compact elements 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.
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-congruence 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 satisfy 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 death 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?
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 Yuri 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 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 subgroups of some locally finite group (Růžička, Tůma, and Wehrung 2007).
(5) The submodule lattice of some right module over a (non-commutative) ring (Růžička, Tůma, and Wehrung 2007).
Congruence lattices of lattices and nonstable K-theory of von Neumann regular rings We recall that for a (unital, associative) ring 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).