×

Cyclic congruences of slim semimodular lattices and non-finite axiomatizability of some finite structures. (English) Zbl 07511505

Author’s abstract: We give a new proof of the fact that finite bipartite graphs cannot be axiomatized by finitely many first-order sentences among finite graphs. (This fact is a consequence of a general theorem proved by L. Ham and M. Jackson [Algebra Univers. 79, No. 2, Paper No. 30, 17 p. (2018; Zbl 1522.08003)], and the counterpart of this fact for all bipartite graphs in the class of all graphs is a well-known consequence of the compactness theorem.) Also, to exemplify that our method is applicable in various fields of mathematics, we prove that neither finite simple groups, nor the ordered sets of join-irreducible congruences of slim semimodular lattices can be described by finitely many axioms in the class of finite structures. Since a 2007 result of G. Grätzer and E. Knapp [Acta Sci. Math. 73, No. 3–4, 445–462 (2007; Zbl 1223.06007)], slim semimodular lattices have constituted the most intensively studied part of lattice theory and they have already led to results even in group theory and geometry. In addition to the non-axiomatizability results mentioned above, we present a new property, called Decomposable Cyclic Elements Property, of the congruence lattices of slim semimodular lattices.

MSC:

03C13 Model theory of finite structures
06C10 Semimodular lattices, geometric lattices
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Burris, S.; Sankappanavar, H. P., A course in universal algebra. Graduate Texts in Mathematics, vol. 78, Springer-Verlag, New York-Berlin, 1981, 2012 update of the Millennium Edition, xvi+276 pp. ISBN: 0-387-90578-2 · Zbl 0478.08001
[2] Czédli, G., Patch extensions and trajectory colorings of slim rectangular lattices, Algebra Universalis 72 (2014), 125-154 · Zbl 1312.06005 · doi:10.1007/s00012-014-0294-z
[3] Czédli, G., Characterizing circles by a convex combinatorial property, Acta Sci. Math. (Szeged) 83 (2017), 683-701 · Zbl 1399.52002 · doi:10.14232/actasm-016-570-x
[4] Czédli, G., Circles and crossing planar compact convex sets, Acta Sci. Math. (Szeged) 85 (2019), 337-353 · Zbl 1449.52002 · doi:10.14232/actasm-018-522-2
[5] Czédli, G., Lamps in slim rectangular planar semimodular lattices, Acta Sci. Math. (Szeged) 87 (2021), 381-413 · Zbl 1499.06025 · doi:10.14232/actasm-021-865-y
[6] Czédli, G.; Grätzer, G., A new property of congruence lattices of slim planar semimodular lattices, to appear in Categ. Gen. Algebr. Struct. Appl · Zbl 1370.06004
[7] Czédli, G.; Grätzer, G., Planar semimodular lattices: structure and diagrams, Lattice Theory: special topics and applications, vol. 1, Birkhäuser-Springer, Cham, 2014, pp. 91-130 · Zbl 1390.06007
[8] Czédli, G.; Kurusa, Á., A convex combinatorial property of compact sets in the plane and its roots in lattice theory, Categ. Gen. Algebr. Struct. Appl. 11 (2019), 57-92, http://cgasa.sbu.ac.ir/article_82639_995ede57b706f33c6488407d8fdd492d.pdf · Zbl 1428.52002
[9] Czédli, G.; Schmidt, E. T., The Jordan-Hölder theorem with uniqueness for groups and semimodular lattices, Algebra Universalis 66 (2011), 69-79 · Zbl 1233.06006 · doi:10.1007/s00012-011-0144-1
[10] Davey, B. A.; Priestley, H. A., Introduction to lattices and order, 2nd ed., Cambridge University Press, New York, 2002, xii+298 pp · Zbl 1002.06001
[11] Dittmann, Ph., Ultraproducts as a tool for first-order inexpressibility in the finite and infinite, http://arxiv.org/abs/1310.3137v1
[12] Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fund. Math. 49 (1961), 129-141 · Zbl 0096.24303 · doi:10.4064/fm-49-2-129-141
[13] Fagin, R., Finite-model theory — a personal perspective, Theoret. Comput. Sci. 116 (1993), 3-31 · Zbl 0788.03037 · doi:10.1016/0304-3975(93)90218-I
[14] Fraïssé, R., Sur quelques classifications des systèmes de relations, Publications Scientifiques de l’Université d’Alger, Series A 1 (1954), 35-182 · Zbl 0068.24302
[15] Frayne, T.; Morel, A. C.; Scott, D. S., Reduced direct products, Fund. Math. 51 (1962), 195-228 · Zbl 0108.00501 · doi:10.4064/fm-51-3-195-228
[16] Grätzer, G., General lattice theory, Birkhäuser Verlag, Basel, 2003, xx+663 pp · Zbl 0385.06015
[17] Grätzer, G., Congruences of fork extensions of slim, planar, semimodular lattices, Algebra Universalis 76 (2016), 139-154 · Zbl 1370.06004 · doi:10.1007/s00012-016-0394-z
[18] Grätzer, G., Notes on planar semimodular lattices. VIII. Congruence lattices of SPS lattices, Algebra Universalis 81 (2020), paper No. 15, 3 pp · Zbl 1477.06024 · doi:10.1007/s00012-020-0641-1
[19] Grätzer, G.; Knapp, E., Notes on planar semimodular lattices. I. Construction, Acta Sci. Math. (Szeged) 73 (2007), 445-462 · Zbl 1223.06007
[20] Grätzer, G.; Knapp, E., Notes on planar semimodular lattices. III. Congruences of rectangular lattice, Acta Sci. Math. (Szeged) 75 (2009), 29-48 · Zbl 1199.06029
[21] Grätzer, G.; Nation, J. B., A new look at the Jordan-Hölder theorem for semimodular lattices, Algebra Universalis 64 (2010), 309-311 · Zbl 1216.06006 · doi:10.1007/s00012-011-0104-9
[22] Ham, L.; Jackson, M., Axiomatisability and hardness for universal Horn classes of hypergraphs, Algebra Universalis 79 (2) (2018), paper No. 30, 17 pp., https://doi.org/10.1007/s00012-018-0515-y · Zbl 1522.08003 · doi:10.1007/s00012-018-0515-y
[23] Immerman, N., Descriptive Complexity, Springer, New York, 1999 · Zbl 0918.68031
[24] Keisler, H. J., Ultraproducts of finite sets, J. Symbolic Logic 32 (1967), 47-57 · Zbl 0153.01702 · doi:10.2307/2271241
[25] Kurosh, A. G., The theory of groups. Volume 1, 2nd english ed., Chelsea Publishing Co., New York, 1960, 272 pp · Zbl 0094.24501
[26] Libkin, L., Elements of finite model theory, Springer-Verlag, Berlin, 2004, xiv+315 pp · Zbl 1060.03002
[27] Poizat, B., A course in model theory. An introduction to contemporary mathematical logic, Springer-Verlag, New York, 2000, xxxii+443 pp · Zbl 0951.03002
[28] Szmielew, W., Elementary properties of Abelian groups, Fund. Math. 41 (1955), 203-271 · Zbl 0064.00803 · doi:10.4064/fm-41-2-203-271
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.