×

Join-semidistributive lattices and convex geometries. (English) Zbl 1059.06003

Convex geometries are defined by the authors as closure spaces satisfying the anti-exchange axiom. In the finite (resp. atomistic) case, the associated lattices of closed sets are join-semidistributive (with respect to atoms) and lower semimodular. The paper focuses on the representation of join-semidistributive lattices within appropriate convex geometries having a join-semidistributive lattice of closed sets, and on developing a geometric framework for the latter. The most remarkable results are the following. Each finite join-semidistributive lattice can be embedded into a convex geometry on the set of join irreducibles as well as into the lattice of algebraic subsets of a lattice which is both algebraic and dually algebraic. The quasivariety of join-semidistibutive lattices is generated by each of the following classes: its finite members; the lattices of closed subsets of finite atomistic convex geometries; the lattices of quasivarieties. In the third section, the authors study examples of convex geometries having a join-semidistributive lattice. The most important are: those associated with partial orders resp. graphs; the lattices of convex compact subsets of Euclidean space; the lattices of finitely generated meet-subsemilattices. Finally, the following representation theorems for infinite join-semidistributive lattices are obtained: each can be embedded into the lattice of a convex geometry which is atomistic, algebraic, and biatomic; in the finitely presented case there is a representation within an dually algebraic, dually spatial, and join-semidistributive lattice. The paper is completed with 5 problems which gave direction for much of the present research.

MSC:

06B05 Structure theory of lattices
06B15 Representation theory of lattices
06C10 Semimodular lattices, geometric lattices
52A37 Other problems of combinatorial convexity
08C15 Quasivarieties
06B23 Complete lattices, completions
Full Text: DOI

References:

[1] Adaricheva, K. V., Semidistributive and co-algebraic lattices of subsemilattices, Algebra and Logic, 27, 385-395 (1988), (translated from Algebra i Logika 27(6) (1988) 625-640) · Zbl 0716.06001
[2] Adaricheva, K. V., The structure of finite lattices of subsemilattices, Algebra and Logic, 30, 249-264 (1990), (translated from Algebra i Logika 30 (1990) 385-404) · Zbl 0773.06009
[3] Adaricheva, K. V., Two embedding theorems for lower bounded lattices, Algebra Universalis, 36, 425-430 (1996) · Zbl 0901.06005
[4] Adaricheva, K. V.; Dziobiak, W.; Gorbunov, V. A., Finite atomistic lattices that can be represented as lattices of quasivarieties, Fund. Math., 142, 19-43 (1993) · Zbl 0806.06005
[5] Adaricheva, K. V.; Dziobiak, W.; Gorbunov, V. A., Algebraic atomistic lattices of quasivarieties, Algebra and Logic, 36, 213-225 (1997), (translated from Algebra i Logika 36 (1997) 363-386) · Zbl 0937.06002
[6] Adaricheva, K. V.; Gorbunov, V. A., On lower bounded lattices, Algebra Universalis, 46, 203-213 (2001) · Zbl 1060.06008
[7] Bennett, M. K., Lattices of convex sets, Trans. Amer. Math. Soc., 234, 279-288 (1977) · Zbl 0367.06011
[8] Bennett, M. K., Convex closure operators, Algebra Universalis, 10, 345-354 (1980) · Zbl 0471.52002
[9] Bennett, M. K., Biatomic lattices, Algebra Universalis, 24, 60-73 (1987) · Zbl 0643.06003
[10] Birkhoff, G.; Bennett, M. K., The convexity lattice of a poset, Order, 2, 223-242 (1985) · Zbl 0591.06009
[11] Bredikhin, D. A.; Schein, B. M., Representation of ordered semigroups and lattices by binary relations, Colloq. Math., 39, 1-12 (1978) · Zbl 0389.06013
[12] Budkin, A. I.; Gorbunov, V. A., On the theory of quasivarieties of algebraic systems, Algebra and Logic, 14, 73-84 (1975), (translated from Algebra i Logika 14 (1975) 123-142) · Zbl 0328.08006
[13] P. Crawley, R.P. Dilworth, Algebraic Theory of Lattices, Prentice-Hall, Englewood Cliffs, NJ, 1973, vi+201 pp.; P. Crawley, R.P. Dilworth, Algebraic Theory of Lattices, Prentice-Hall, Englewood Cliffs, NJ, 1973, vi+201 pp. · Zbl 0494.06001
[14] Dean, R. A.; Keller, G., Natural partial orders, Canad. J. Math., 20, 535-554 (1968) · Zbl 0174.29701
[15] Dietrich, B., Matroids and antimatroids—survey, Discrete Math., 78, 223-237 (1989) · Zbl 0723.05025
[16] Dilworth, R. P., (Bogart, K. P.; Freese, R.; Kung, J. P.S., The Dilworth theorems. Selected Papers of Robert P. Dilworth, Contemporary Mathematicians (1990), Birkhäuser: Birkhäuser Boston, MA), 465pp · Zbl 0907.06001
[17] Dilworth, R. P., Lattices with unique irreducible decompositions, Ann. of Math. (2), 41, 771-777 (1940) · Zbl 0025.10202
[18] Dilworth, R. P.; Hall, M., The embedding problem for modular lattices, Ann. of Math. (2), 45, 450-456 (1944) · Zbl 0060.06102
[19] Duquenne, V., On the core of finite lattices, Discrete Math., 88, 133-147 (1991) · Zbl 0736.06012
[20] Edelman, P. H., Meet-distributive lattices and the antiexchange closure, Algebra Universalis, 10, 290-299 (1980) · Zbl 0442.06004
[21] Edelman, P. H.; Jamison, R., The theory of convex geometries, Geom. Dedicata, 19, 247-274 (1985) · Zbl 0577.52001
[22] H.G. Eggleston, Convexity, Cambridge Tracts in Mathematics and Mathematical Physics, vol. 47, Cambridge University Press, Cambridge, 1958, viii+136pp.; H.G. Eggleston, Convexity, Cambridge Tracts in Mathematics and Mathematical Physics, vol. 47, Cambridge University Press, Cambridge, 1958, viii+136pp. · Zbl 0086.15302
[23] Faigle, U., Frink’s theorem for modular lattices, Arch. Math., 36, 179-182 (1981) · Zbl 0438.06004
[24] Faigle, U.; Herrmann, C., Projective geometry on partially ordered sets, Trans. Amer. Math. Soc., 266, 319-332 (1981) · Zbl 0466.51001
[25] Freese, R., The variety of modular lattices is not generated by its finite members, Trans. Amer. Math. Soc., 255, 277-300 (1979) · Zbl 0421.06010
[26] Freese, R., Free modular lattices, Trans. Amer. Math. Soc., 261, 81-91 (1980) · Zbl 0437.06006
[27] R. Freese, J. Ježek, J.B. Nation, Free Lattices, Mathematical Surveys and Monographs, Vol. 42, American Mathematical Society, Providence, RI, 1995, viii+293pp.; R. Freese, J. Ježek, J.B. Nation, Free Lattices, Mathematical Surveys and Monographs, Vol. 42, American Mathematical Society, Providence, RI, 1995, viii+293pp. · Zbl 0839.06005
[28] R. Freese, K. Kearnes, J.B. Nation, Congruence lattices of congruence semidistributive algebras, in: K.A. Baker, R. Wille (Eds.), Lattice theory and its applications, Celebration of Garrett Birkhoff’s 80th birthday, Heldermann Verlag, 1995, pp. 63-78.; R. Freese, K. Kearnes, J.B. Nation, Congruence lattices of congruence semidistributive algebras, in: K.A. Baker, R. Wille (Eds.), Lattice theory and its applications, Celebration of Garrett Birkhoff’s 80th birthday, Heldermann Verlag, 1995, pp. 63-78. · Zbl 0837.08003
[29] Frink, O., Complemented modular lattices and projective spaces of infinite dimension, Trans. Amer. Math. Soc., 60, 452-467 (1946) · Zbl 0060.05811
[30] G. Gierz, K.H. Hofmann, K. Keimel, J.D. Lawson, M. Mislove, D.S. Scott, A Compendium of Continuous Lattices, Springer, Berlin, New York, 1980, xx+371pp.; G. Gierz, K.H. Hofmann, K. Keimel, J.D. Lawson, M. Mislove, D.S. Scott, A Compendium of Continuous Lattices, Springer, Berlin, New York, 1980, xx+371pp. · Zbl 0452.06001
[31] Gorbunov, V. A., Lattices of quasivarieties, Algebra and Logic, 15, 275-288 (1976), (translated from Algebra i Logika 15 (1976) 436-457) · Zbl 0369.06004
[32] Gorbunov, V. A., Canonical decompositions in complete lattices, Algebra and Logic, 17, 323-332 (1978), (translated from Algebra i Logika 17 (1978) 495-511) · Zbl 0429.06001
[33] Gorbunov, V. A., The structure of lattices of quasivarieties, Algebra Universalis, 32, 493-530 (1994) · Zbl 0815.08006
[34] V.A. Gorbunov, Algebraic theory of quasivarieties (Algebraicheskaya teoriya kvazimnogoobrazij) (Russian) Sibirskaya Shkola Algebry i Logiki, 5, Nauchnaya Kniga, Novosibirsk, 1999, xii+368pp. (English translation by Plenum, New York, 1998, xii+298pp.); V.A. Gorbunov, Algebraic theory of quasivarieties (Algebraicheskaya teoriya kvazimnogoobrazij) (Russian) Sibirskaya Shkola Algebry i Logiki, 5, Nauchnaya Kniga, Novosibirsk, 1999, xii+368pp. (English translation by Plenum, New York, 1998, xii+298pp.)
[35] Gorbunov, V. A.; Tumanov, V. I., A class of lattices of quasivarieties, Algebra and Logic, 19, 38-52 (1980), (translated from Algebra i Logika 19 (1980) 59-80) · Zbl 0472.08011
[36] V.A. Gorbunov, V.I. Tumanov, The structure of lattices of quasivarieties, Proceedings of the Institute of Mathematics, Siberian Branch of USSR Academy of Science, Vol. 2, 1982, pp. 12-44.; V.A. Gorbunov, V.I. Tumanov, The structure of lattices of quasivarieties, Proceedings of the Institute of Mathematics, Siberian Branch of USSR Academy of Science, Vol. 2, 1982, pp. 12-44. · Zbl 0523.08008
[37] G. Grätzer, General Lattice Theory, 2nd Edition, Birkhäuser Verlag, Basel, 1998, xix+663pp.; G. Grätzer, General Lattice Theory, 2nd Edition, Birkhäuser Verlag, Basel, 1998, xix+663pp. · Zbl 0909.06002
[38] P.M. Gruber, The space of convex bodies, in: P.M. Gruber, J.M. Wills (Eds.), Handbook of Convex Geometry, Vol. A, North-Holland, Amsterdam, 1993, pp. 301-318.; P.M. Gruber, The space of convex bodies, in: P.M. Gruber, J.M. Wills (Eds.), Handbook of Convex Geometry, Vol. A, North-Holland, Amsterdam, 1993, pp. 301-318. · Zbl 0791.52004
[39] Herrmann, C., On the word problem for the modular lattice with four generators, Math. Ann., 265, 513-527 (1983) · Zbl 0506.06004
[40] Herrmann, C.; Huhn, A. P., Zum Begriff der Charakteristik modularer Verbände, Math. Z., 144, 185-194 (1975) · Zbl 0316.06006
[41] Herrmann, C.; Pickering, D.; Roddy, M., A geometric description of modular lattices, Algebra Universalis, 31, 3, 365-396 (1994) · Zbl 0816.06008
[42] D. Hobby, R.N. McKenzie, The structure of finite algebras, Contemporary Mathematics, Vol. 76, American Mathematical Society, Providence, RI, 1988, xi+203pp.; D. Hobby, R.N. McKenzie, The structure of finite algebras, Contemporary Mathematics, Vol. 76, American Mathematical Society, Providence, RI, 1988, xi+203pp. · Zbl 0721.08001
[43] R.E. Jamison, A development of axiomatic convexity, Technical Report 48, Clemson Univ. Math., pp. 15-20.; R.E. Jamison, A development of axiomatic convexity, Technical Report 48, Clemson Univ. Math., pp. 15-20.
[44] P. Jipsen, H. Rose, Varieties of Lattices, Lecture Notes in Mathematics, Vol. 1533, Springer, Berlin, Heidelberg, 1992, x+162pp.; P. Jipsen, H. Rose, Varieties of Lattices, Lecture Notes in Mathematics, Vol. 1533, Springer, Berlin, Heidelberg, 1992, x+162pp. · Zbl 0779.06005
[45] Jónsson, B., On the representation of lattices, Math. Scand., 1, 193-206 (1953) · Zbl 0053.21304
[46] Jónsson, B., Sublattices of a free lattice, Canad. J. Math., 13, 256-264 (1961) · Zbl 0132.26201
[47] Jónsson, B.; Kiefer, J., Finite sublattices of a free lattice, Canad. J. Math., 14, 487-497 (1962) · Zbl 0107.25202
[48] Jónsson, B.; Rival, I., Lattice varieties covering the smallest non-modular variety, Pacific J. Math., 82, 463-478 (1979) · Zbl 0424.06004
[49] Korte, B.; Lovász, L., Shelling structures, convexity and a happy end, (Bollóbas, B., Graph Theory and Combinatorics (1984), Academic Press), 219-232 · Zbl 0553.05030
[50] B. Korte, L. Lovász, R. Schrader, Greedoids, Algorithms and Combinatorics, Vol. 4, Springer, Berlin, 1991, viii+211pp.; B. Korte, L. Lovász, R. Schrader, Greedoids, Algorithms and Combinatorics, Vol. 4, Springer, Berlin, 1991, viii+211pp. · Zbl 0733.05023
[51] Libkin, L., Direct decompositions of atomistic algebraic lattices, Algebra Universalis, 33, 127-135 (1995) · Zbl 0818.06004
[52] A.I. Mal’cev, Algebraic systems, Algebraic Systems (Algebraicheskie sistemy) (Russian) Sovremennaja Algebra, Verlag “Nauka”, Moskau, Hauptredaktion für physikalisch-mathematische Literatur, 1970, p. 392 (English translation: Die Grundlehren der mathematischen Wissenschaften. Band, 192, Springer, Berlin, Heidelberg, New York, Akademie-Verlag, Berlin, 1973, xii+317pp.; A.I. Mal’cev, Algebraic systems, Algebraic Systems (Algebraicheskie sistemy) (Russian) Sovremennaja Algebra, Verlag “Nauka”, Moskau, Hauptredaktion für physikalisch-mathematische Literatur, 1970, p. 392 (English translation: Die Grundlehren der mathematischen Wissenschaften. Band, 192, Springer, Berlin, Heidelberg, New York, Akademie-Verlag, Berlin, 1973, xii+317pp.
[53] McKinsey, J. C.C., The decision problem for some classes of sentences without quantifiers, J. Symbolic Logic, 8, 61-76 (1943) · Zbl 0063.03864
[54] McKenzie, R. N., Equational bases and non-modular lattice varieties, Trans. Amer. Math. Soc., 174, 1-43 (1972) · Zbl 0265.08006
[55] Monjardet, B., A use for frequently rediscovering a concept, Order, 1, 415-417 (1985) · Zbl 0558.06010
[56] B. Monjardet, The consequences of Dilworth’s work on lattices with unique irreducible decompositions, in: K.P. Bogart, R. Freese, J.P.S. Kung (Eds.), The Dilworth theorems. Selected Papers of Robert P. Dilworth, Contemporary Mathematicians, Birkhäuser, Boston, MA, 1990, pp. 192-199.; B. Monjardet, The consequences of Dilworth’s work on lattices with unique irreducible decompositions, in: K.P. Bogart, R. Freese, J.P.S. Kung (Eds.), The Dilworth theorems. Selected Papers of Robert P. Dilworth, Contemporary Mathematicians, Birkhäuser, Boston, MA, 1990, pp. 192-199.
[57] Nation, J. B., Some varieties of semidistributive lattices, (Comer, S., Universal Algebra and Lattice Theory. Universal Algebra and Lattice Theory, Lecture Notes in Mathematics, Vol. 1149 (1985), Springer: Springer New York), 198-223 · Zbl 0572.06006
[58] Pfaltz, J., Convexity in directed graphs, J. Combin. Theory Ser. B, 10, 143-162 (1971) · Zbl 0174.26803
[59] Prenowitz, W., Total lattices of convex sets and of linear spaces, Ann. Math., 49, 2, 659-688 (1948) · Zbl 0037.21601
[60] Pudlák, P.; Tu̇ma, J., Every finite lattice can be embedded in a finite partition lattice, Algebra Universalis, 10, 74-95 (1980) · Zbl 0433.06009
[61] Repnitskiı̌, V. B., On finite lattices which are embeddable in subsemigroup lattices, Semigroup Forum, 46, 388-397 (1993) · Zbl 0797.20052
[62] Semenova, M. V., Lattices of suborders, Siberian Math. J., 40, 577-584 (1999) · Zbl 0924.06009
[63] Sivak, B., Representation of finite lattices by orders on finite sets, Math. Slovaca, 28, 203-215 (1978) · Zbl 0395.06002
[64] M. Tischendorf, The representation problem for algebraic distributive lattices, Ph.D. Thesis, Darmstadt, 1992.; M. Tischendorf, The representation problem for algebraic distributive lattices, Ph.D. Thesis, Darmstadt, 1992.
[65] V.I. Tumanov, Embedding theorems for join-semidistributive lattices, Proceedings of the Sixth All-Union Conference on Mathematics Logic, Tbilisi, 1982, p. 188.; V.I. Tumanov, Embedding theorems for join-semidistributive lattices, Proceedings of the Sixth All-Union Conference on Mathematics Logic, Tbilisi, 1982, p. 188.
[66] F. Wehrung, Direct decompositions of non-algebraic complete lattices, Discrete Math. (in press).; F. Wehrung, Direct decompositions of non-algebraic complete lattices, Discrete Math. (in press). · Zbl 1023.06006
[67] D.J.A. Welsh, Matroid theory, L.M.S. Monographs 8, Academic Press, London, New York, San Francisco, a subsidiary of Harcourt Brace Jovanovich, Publishers, 1976, xi+433pp.; D.J.A. Welsh, Matroid theory, L.M.S. Monographs 8, Academic Press, London, New York, San Francisco, a subsidiary of Harcourt Brace Jovanovich, Publishers, 1976, xi+433pp. · Zbl 0343.05002
[68] M. Wild, On some lattice problems of Jamison, Kamara and Rota, Tech. Hochschule Darmstadt, preprint no. 1694, 1994.; M. Wild, On some lattice problems of Jamison, Kamara and Rota, Tech. Hochschule Darmstadt, preprint no. 1694, 1994.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.