Congruence lattice problem: Difference between revisions

Revision as of 21:17, 19 January 2011

Revision as of 10:31, 9 September 2011

Line 39:

'''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.

Line 52 ⟶ 51:

==Semilattice formulation of CLP==

The congruence lattice Con ''A'' of an [[Universal algebra|algebra]] ''A'' is an [[Compact element|algebraic lattice]]. The (∨,0)-[[semilattice]] of [[Compactcompact element|compact elements]]s of Con ''A'' is denoted by Con_c ''A'', and it is sometimes called the ''congruence semilattice'' of ''A''. Then Con ''A'' is isomorphic to the [[Ideal (order theory)|ideal lattice]] of Con_c ''A''. By using the classical [[Equivalence of categories|equivalence]] between the category of all (∨,0)-semilattices and the category of all algebraic lattices (with suitable definitions of [[morphisms]]), as it is outlined [[Semilattice|here]], we obtain the following semilattice-theoretical formulation of CLP.

----

Line 107 ⟶ 106:

==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 Con_c ''L'', for some lattice ''L''. Writing ''S'' as a directed union <math>S=\bigcup(S_i\mid i\in I)</math> of finite distributive (∨,0)-subsemilattices, we are ''hoping'' to represent each ''S_i'' as the congruence lattice of a lattice ''L_i'' with lattice homomorphisms ''f_i^j : L_i→ L_j'', for ''i ≤ j'' in ''I'', such that the diagram <math>\mathcal{S}</math> of all ''S_i'' with all inclusion maps ''S_i→S_j'', for ''i ≤ j'' in ''I'', is [[Equivalence of categories|naturally equivalent]] to <math>(\mathrm{Con_c}\,L_i,\mathrm{Con_c}\,f_i^j\mid i\leq j\text{ in }I)</math>, we say that the diagram <math>(L_i,f_i^j\mid i\leq j\text{ in }I)</math> lifts <math>\mathcal{S}</math> (with respect to the Con_c functor). If this can be done, then, as we have seen that the Con_c functor preserves direct limits, the direct limit <math>L=\varinjlim_{i\in I}L_i</math> satisfies <math>{\rm Con_c}\,L\cong S</math>.

Line 119 ⟶ 117:

'''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 Con_cΦ is [[Equivalence of categories|naturally equivalent]] to the identity. Furthermore, Φ(''S'') is a finite [[Lattice (order)|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.

Line 127 ⟶ 124:

'''Theorem (Tůma and Wehrung 2006).'''

There exists a [[Diagram (category theory)|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 Con_c functor, by any diagram of lattices and lattice homomorphisms.

In particular, this implies immediately that CLP has no ''functorial'' solution.

Line 136 ⟶ 132:

'''Theorem (Bulman-Fleming and McDowell 1978).'''

Every distributive (∨,0)-semilattice is a direct limit of finite [[Boolean algebra (structure)|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.

Line 160 ⟶ 155:

'''Theorem (Wehrung 1999).'''

Let ''R'' be a von Neumann regular ring. Then the (∨,0)-semilattices Id_c ''R'' and Con_c ''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 Id_c ''R'', for some [[Refinement monoid|locally matricial]] ring ''R'' (over any given field). This result is extended to semilattices of cardinality at most ℵ₁ 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 ℵ₁ 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.

Line 171 ⟶ 165:

----

==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 [[Refinement monoid|dimension vector space]] ''G'' over the rationals with [[Monoid|order-unit]] whose positive cone ''G''⁺ is not isomorphic to ''V(R)'', for any von Neumann regular ring ''R'', and is not [[Refinement monoid|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 ℵ₂.

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.

Line 201 ⟶ 193:

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 ℵ₂. 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.

Line 209 ⟶ 200:

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

The semilattice Con_c F_'''V'''(Ω) does not satisfy WURP, for any set Ω of cardinality at least ℵ₂ and any non-distributive variety '''V''' of lattices. Consequently, Con_c F_'''V'''(Ω) does not satisfy Schmidt's Condition.

It is proved by Tůma and Wehrung in 2001 that Con_c F_'''V'''(Ω) is not isomorphic to Con_c ''L'', for any lattice ''L'' with permutable congruences. By using a slight weakening of WURP, this result is extended to arbitrary [[Universal algebra|algebras]] with permutable congruences by Růžička, Tůma, and Wehrung in 2006. Hence, for example, if Ω has at least ℵ₂ elements, then Con_c F_'''V'''(Ω) is not isomorphic to the normal subgroup lattice of any group, or the submodule lattice of any module.

Line 248 ⟶ 238:

'''Theorem (Růžička 2008).'''

The semilattice ''G(Ω)'' is not isomorphic to Con_c ''L'' for any lattice ''L'', whenever the set Ω has at least ℵ₂ 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.

Line 254 ⟶ 243:

==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 set]] 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:

Line 275 ⟶ 263:

*[[Garrett Birkhoff|G. Birkhoff]] and O. Frink, ''Representations of lattices by sets'', Trans. Amer. Math. Soc. '''64''', no. 2 (1948), 299–316.

*S. Bulman-Fleming and K. McDowell, ''Flat semilattices'', Proc. Amer. Math. Soc. '''72''', no. 2 (1978), 228–232.

*K.P. Bogart, R. Freese, and J.P.S. Kung (editors), ''The Dilworth Theorems. Selected papers of Robert P. Dilworth'', Birkhäuser Verlag, Basel - Boston - Berlin, 1990. xxvi+465 p. &nbsp;ISBN 0-8176-3434-7

*[[Hans Dobbertin|H. Dobbertin]], ''Refinement monoids, Vaught monoids, and Boolean algebras'', Math. Ann. '''265''', no. 4 (1983), 473–487.

*[[Hans Dobbertin|H. Dobbertin]], ''Vaught measures and their applications in lattice theory'', J. Pure Appl. Algebra '''43''', no. 1 (1986), 27–51.

Line 283 ⟶ 271:

*R. Freese, W.A. Lampe, and W. Taylor, ''Congruence lattices of algebras of fixed similarity type. I'', Pacific J. Math. '''82''' (1979), 59–68.

*N. Funayama and T. Nakayama, ''On the distributivity of a lattice of lattice congruences'', Proc. Imp. Acad. Tokyo '''18''' (1942), 553–554.

*K.R. Goodearl, von Neumann regular rings. Second edition. Robert E. Krieger Publishing Co., Inc., Malabar, FL, 1991. xviii+412 p. &nbsp;ISBN 0-89464-632-X

*K.R. Goodearl and D. Handelman, ''Simple self-injective rings'', Comm. Algebra '''3''', no. 9 (1975), 797–834.

*K.R. Goodearl and D. Handelman, ''Tensor products of dimension groups and K₀ of unit-regular rings'', Canad. J. Math. '''38''', no. 3 (1986), 633–658.

*K.R. Goodearl and F. Wehrung, ''Representations of distributive semilattices in ideal lattices of various algebraic structures'', Algebra Universalis '''45''', no. 1 (2001), 71–102.

*G. Grätzer, General Lattice Theory. Second edition, new appendices by the author with B.A. Davey, R. Freese, B. Ganter, M. Greferath, P. Jipsen, H.A. Priestley, H. Rose, E.T. Schmidt, S.E. Schmidt, F. Wehrung, and R. Wille. Birkhäuser Verlag, Basel, 1998. xx+663 p. &nbsp;ISBN 3-7643-5239-6

*G. Grätzer, The Congruences of a Finite Lattice: a ''Proof-by-Picture'' Approach, Birkhäuser Boston, 2005. xxiii+281 p. &nbsp;ISBN 978-0-8176-3224-3; 0-8176-3224-7

*G. Grätzer, H. Lakser, and F. Wehrung, ''Congruence amalgamation of lattices'', Acta Sci. Math. (Szeged) '''66''' (2000), 339–358.

*G. Grätzer and E.T. Schmidt, ''On congruence lattices of lattices'', Acta Math. Sci. Hungar. '''13''' (1962), 179–185.

Line 307 ⟶ 295:

*P. Růžička, ''Free trees and the optimal bound in Wehrung's theorem'', Fund. Math. '''198''' (2008), 217–228.

*P. Růžička, J. Tůma, and F. Wehrung, ''Distributive congruence lattices of congruence-permutable algebras'', J. Algebra '''311''' (2007), 96–116.

*E.T. Schmidt, ''Zur Charakterisierung der Kongruenzverbände der Verbände'', Mat. Casopis Sloven. Akad. Vied '''18''' (1968), 3–20.

*E.T. Schmidt, ''The ideal lattice of a distributive lattice with 0 is the congruence lattice of a lattice'', Acta Sci. Math. (Szeged) '''43''' (1981), 153–168.

*E.T. Schmidt, A Survey on Congruence Lattice Representations, Teubner-Texte zur Mathematik [Teubner Texts in Mathematics], '''42'''. BSB B. G. Teubner Verlagsgesellschaft, Leipzig, 1982. 115 p.

Line 317 ⟶ 305:

*J. Tůma and F. Wehrung, ''Congruence lifting of diagrams of finite Boolean semilattices requires large congruence varieties'', Internat. J. Algebra Comput. '''16''', no. 3 (2006), 541–550.

*F. Wehrung, ''Non-measurability properties of interpolation vector spaces'', Israel J. Math. '''103''' (1998), 177–206.

*F. Wehrung, ''The dimension monoid of a lattice'', Algebra Universalis '''40''', no. 3 (1998), 247–411.

*F. Wehrung, ''A uniform refinement property for congruence lattices'', Proc. Amer. Math. Soc. '''127''', no. 2 (1999), 363–370.

*F. Wehrung, ''Representation of algebraic distributive lattices with ℵ₁ compact elements as ideal lattices of regular rings'', Publ. Mat. (Barcelona) '''44''' (2000), 419–435.

Line 325 ⟶ 313:

*F. Wehrung, ''A solution to Dilworth's congruence lattice problem'', Adv. Math. '''216''', no. 2 (2007), 610–625.

[[categoryCategory:Lattice theory]]