Cyclic congruences of slim semimodular lattices and non-finite axiomatizability of some finite structures

Gábor Czédli

Archivum Mathematicum (2022)

  • Volume: 058, Issue: 1, page 15-33
  • ISSN: 0044-8753

Abstract

top
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, 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, 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.

How to cite

top

Czédli, Gábor. "Cyclic congruences of slim semimodular lattices and non-finite axiomatizability of some finite structures." Archivum Mathematicum 058.1 (2022): 15-33. <http://eudml.org/doc/297703>.

@article{Czédli2022,
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, 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, 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.},
author = {Czédli, Gábor},
journal = {Archivum Mathematicum},
keywords = {finite model theory; non-finite axiomatizability; finite axiomatizability; finite bipartite graphs; finite simple group; join-irreducible congruence; congruence lattice; slim semimodular lattice; finite propositional logic; first-order inexpressibility; first-order language},
language = {eng},
number = {1},
pages = {15-33},
publisher = {Department of Mathematics, Faculty of Science of Masaryk University, Brno},
title = {Cyclic congruences of slim semimodular lattices and non-finite axiomatizability of some finite structures},
url = {http://eudml.org/doc/297703},
volume = {058},
year = {2022},
}

TY - JOUR
AU - Czédli, Gábor
TI - Cyclic congruences of slim semimodular lattices and non-finite axiomatizability of some finite structures
JO - Archivum Mathematicum
PY - 2022
PB - Department of Mathematics, Faculty of Science of Masaryk University, Brno
VL - 058
IS - 1
SP - 15
EP - 33
AB - 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, 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, 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.
LA - eng
KW - finite model theory; non-finite axiomatizability; finite axiomatizability; finite bipartite graphs; finite simple group; join-irreducible congruence; congruence lattice; slim semimodular lattice; finite propositional logic; first-order inexpressibility; first-order language
UR - http://eudml.org/doc/297703
ER -

References

top
  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. (1981) 
  2. Czédli, G., 10.1007/s00012-014-0294-z, Algebra Universalis 72 (2014), 125–154. (2014) MR3257651DOI10.1007/s00012-014-0294-z
  3. Czédli, G., 10.14232/actasm-016-570-x, Acta Sci. Math. (Szeged) 83 (2017), 683–701. (2017) MR3728079DOI10.14232/actasm-016-570-x
  4. Czédli, G., 10.14232/actasm-018-522-2, Acta Sci. Math. (Szeged) 85 (2019), 337–353. (2019) MR3967894DOI10.14232/actasm-018-522-2
  5. Czédli, G., 10.14232/actasm-021-865-y, Acta Sci. Math. (Szeged) 87 (2021), 381–413. (2021) MR4333915DOI10.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. 
  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. (2014) MR3330596
  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. (2019) 
  9. Czédli, G., Schmidt, E.T., 10.1007/s00012-011-0144-1, Algebra Universalis 66 (2011), 69–79. (2011) MR2844921DOI10.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. (2002) MR1902334
  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., 10.4064/fm-49-2-129-141, Fund. Math. 49 (1961), 129–141. (1961) DOI10.4064/fm-49-2-129-141
  13. Fagin, R., 10.1016/0304-3975(93)90218-I, Theoret. Comput. Sci. 116 (1993), 3–31. (1993) DOI10.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. (1954) 
  15. Frayne, T., Morel, A.C., Scott, D.S., 10.4064/fm-51-3-195-228, Fund. Math. 51 (1962), 195–228. (1962) DOI10.4064/fm-51-3-195-228
  16. Grätzer, G., General lattice theory, Birkhäuser Verlag, Basel, 2003, xx+663 pp. (2003) MR2451139
  17. Grätzer, G., 10.1007/s00012-016-0394-z, Algebra Universalis 76 (2016), 139–154. (2016) MR3551218DOI10.1007/s00012-016-0394-z
  18. Grätzer, G., 10.1007/s00012-020-0641-1, Algebra Universalis 81 (2020), paper No. 15, 3 pp. (2020) MR4067804DOI10.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. (2007) MR2380059
  20. Grätzer, G., Knapp, E., Notes on planar semimodular lattices. III. Congruences of rectangular lattice, Acta Sci. Math. (Szeged) 75 (2009), 29–48. (2009) MR2533398
  21. Grätzer, G., Nation, J.B., 10.1007/s00012-011-0104-9, Algebra Universalis 64 (2010), 309–311. (2010) MR2781081DOI10.1007/s00012-011-0104-9
  22. Ham, L., Jackson, M., 10.1007/s00012-018-0515-y, Algebra Universalis 79 (2) (2018), paper No. 30, 17 pp., https://doi.org/10.1007/s00012-018-0515-y. (2018) MR3788809DOI10.1007/s00012-018-0515-y
  23. Immerman, N., Descriptive Complexity, Springer, New York, 1999. (1999) 
  24. Keisler, H.J., 10.2307/2271241, J. Symbolic Logic 32 (1967), 47–57. (1967) DOI10.2307/2271241
  25. Kurosh, A.G., The theory of groups. Volume 1, 2nd english ed., Chelsea Publishing Co., New York, 1960, 272 pp. (1960) 
  26. Libkin, L., Elements of finite model theory, Springer-Verlag, Berlin, 2004, xiv+315 pp. (2004) MR2102513
  27. Poizat, B., A course in model theory. An introduction to contemporary mathematical logic, Springer-Verlag, New York, 2000, xxxii+443 pp. (2000) 
  28. Szmielew, W., 10.4064/fm-41-2-203-271, Fund. Math. 41 (1955), 203–271. (1955) DOI10.4064/fm-41-2-203-271

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.