| Title:
|
Cyclic congruences of slim semimodular lattices and non-finite axiomatizability of some finite structures (English) |
| Author:
|
Czédli, Gábor |
| Language:
|
English |
| Journal:
|
Archivum Mathematicum |
| ISSN:
|
0044-8753 (print) |
| ISSN:
|
1212-5059 (online) |
| Volume:
|
58 |
| Issue:
|
1 |
| Year:
|
2022 |
| Pages:
|
15-33 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
finite model theory |
| Keyword:
|
non-finite axiomatizability |
| Keyword:
|
finite axiomatizability |
| Keyword:
|
finite bipartite graphs |
| Keyword:
|
finite simple group |
| Keyword:
|
join-irreducible congruence |
| Keyword:
|
congruence lattice |
| Keyword:
|
slim semimodular lattice |
| Keyword:
|
finite propositional logic |
| Keyword:
|
first-order inexpressibility |
| Keyword:
|
first-order language |
| MSC:
|
03C13 |
| MSC:
|
06C10 |
| idZBL:
|
Zbl 07511505 |
| idMR:
|
MR4412964 |
| DOI:
|
10.5817/AM2022-1-15 |
| . |
| Date available:
|
2022-02-23T12:09:11Z |
| Last updated:
|
2022-06-23 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/149444 |
| . |
| Reference:
|
[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. |
| Reference:
|
[2] Czédli, G.: Patch extensions and trajectory colorings of slim rectangular lattices.Algebra Universalis 72 (2014), 125–154. MR 3257651, 10.1007/s00012-014-0294-z |
| Reference:
|
[3] Czédli, G.: Characterizing circles by a convex combinatorial property.Acta Sci. Math. (Szeged) 83 (2017), 683–701. MR 3728079, 10.14232/actasm-016-570-x |
| Reference:
|
[4] Czédli, G.: Circles and crossing planar compact convex sets.Acta Sci. Math. (Szeged) 85 (2019), 337–353. MR 3967894, 10.14232/actasm-018-522-2 |
| Reference:
|
[5] Czédli, G.: Lamps in slim rectangular planar semimodular lattices.Acta Sci. Math. (Szeged) 87 (2021), 381–413. MR 4333915, 10.14232/actasm-021-865-y |
| Reference:
|
[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. |
| Reference:
|
[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. MR 3330596 |
| Reference:
|
[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. |
| Reference:
|
[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. MR 2844921, 10.1007/s00012-011-0144-1 |
| Reference:
|
[10] Davey, B.A., Priestley, H.A.: Introduction to lattices and order.2nd ed., Cambridge University Press, New York, 2002, xii+298 pp. MR 1902334 |
| Reference:
|
[11] Dittmann, Ph.: Ultraproducts as a tool for first-order inexpressibility in the finite and infinite.http://arxiv.org/abs/1310.3137v1. |
| Reference:
|
[12] Ehrenfeucht, A.: An application of games to the completeness problem for formalized theories.Fund. Math. 49 (1961), 129–141. 10.4064/fm-49-2-129-141 |
| Reference:
|
[13] Fagin, R.: Finite-model theory — a personal perspective.Theoret. Comput. Sci. 116 (1993), 3–31. 10.1016/0304-3975(93)90218-I |
| Reference:
|
[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. |
| Reference:
|
[15] Frayne, T., Morel, A.C., Scott, D.S.: Reduced direct products.Fund. Math. 51 (1962), 195–228. 10.4064/fm-51-3-195-228 |
| Reference:
|
[16] Grätzer, G.: General lattice theory.Birkhäuser Verlag, Basel, 2003, xx+663 pp. MR 2451139 |
| Reference:
|
[17] Grätzer, G.: Congruences of fork extensions of slim, planar, semimodular lattices.Algebra Universalis 76 (2016), 139–154. MR 3551218, 10.1007/s00012-016-0394-z |
| Reference:
|
[18] Grätzer, G.: Notes on planar semimodular lattices. VIII. Congruence lattices of SPS lattices.Algebra Universalis 81 (2020), paper No. 15, 3 pp. MR 4067804, 10.1007/s00012-020-0641-1 |
| Reference:
|
[19] Grätzer, G., Knapp, E.: Notes on planar semimodular lattices. I. Construction.Acta Sci. Math. (Szeged) 73 (2007), 445–462. MR 2380059 |
| Reference:
|
[20] Grätzer, G., Knapp, E.: Notes on planar semimodular lattices. III. Congruences of rectangular lattice.Acta Sci. Math. (Szeged) 75 (2009), 29–48. MR 2533398 |
| Reference:
|
[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. MR 2781081, 10.1007/s00012-011-0104-9 |
| Reference:
|
[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. MR 3788809, 10.1007/s00012-018-0515-y |
| Reference:
|
[23] Immerman, N.: Descriptive Complexity.Springer, New York, 1999. |
| Reference:
|
[24] Keisler, H.J.: Ultraproducts of finite sets.J. Symbolic Logic 32 (1967), 47–57. 10.2307/2271241 |
| Reference:
|
[25] Kurosh, A.G.: The theory of groups. Volume 1.2nd english ed., Chelsea Publishing Co., New York, 1960, 272 pp. |
| Reference:
|
[26] Libkin, L.: Elements of finite model theory.Springer-Verlag, Berlin, 2004, xiv+315 pp. MR 2102513 |
| Reference:
|
[27] Poizat, B.: A course in model theory. An introduction to contemporary mathematical logic.Springer-Verlag, New York, 2000, xxxii+443 pp. |
| Reference:
|
[28] Szmielew, W.: Elementary properties of Abelian groups.Fund. Math. 41 (1955), 203–271. 10.4064/fm-41-2-203-271 |
| . |
