Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
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
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
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.
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.
[2] Czédli, G.: Patch extensions and trajectory colorings of slim rectangular lattices. Algebra Universalis 72 (2014), 125–154. DOI 10.1007/s00012-014-0294-z | MR 3257651
[3] Czédli, G.: Characterizing circles by a convex combinatorial property. Acta Sci. Math. (Szeged) 83 (2017), 683–701. DOI 10.14232/actasm-016-570-x | MR 3728079
[4] Czédli, G.: Circles and crossing planar compact convex sets. Acta Sci. Math. (Szeged) 85 (2019), 337–353. DOI 10.14232/actasm-018-522-2 | MR 3967894
[5] Czédli, G.: Lamps in slim rectangular planar semimodular lattices. Acta Sci. Math. (Szeged) 87 (2021), 381–413. DOI 10.14232/actasm-021-865-y | MR 4333915
[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. MR 3330596
[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
[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. DOI 10.1007/s00012-011-0144-1 | MR 2844921
[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
[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. DOI 10.4064/fm-49-2-129-141
[13] Fagin, R.: Finite-model theory — a personal perspective. Theoret. Comput. Sci. 116 (1993), 3–31. 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.
[15] Frayne, T., Morel, A.C., Scott, D.S.: Reduced direct products. Fund. Math. 51 (1962), 195–228. DOI 10.4064/fm-51-3-195-228
[16] Grätzer, G.: General lattice theory. Birkhäuser Verlag, Basel, 2003, xx+663 pp. MR 2451139
[17] Grätzer, G.: Congruences of fork extensions of slim, planar, semimodular lattices. Algebra Universalis 76 (2016), 139–154. DOI 10.1007/s00012-016-0394-z | MR 3551218
[18] Grätzer, G.: Notes on planar semimodular lattices. VIII. Congruence lattices of SPS lattices. Algebra Universalis 81 (2020), paper No. 15, 3 pp. DOI 10.1007/s00012-020-0641-1 | MR 4067804
[19] Grätzer, G., Knapp, E.: Notes on planar semimodular lattices. I. Construction. Acta Sci. Math. (Szeged) 73 (2007), 445–462. MR 2380059
[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
[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. DOI 10.1007/s00012-011-0104-9 | MR 2781081
[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 DOI 10.1007/s00012-018-0515-y | MR 3788809
[23] Immerman, N.: Descriptive Complexity. Springer, New York, 1999.
[24] Keisler, H.J.: Ultraproducts of finite sets. J. Symbolic Logic 32 (1967), 47–57. 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.
[26] Libkin, L.: Elements of finite model theory. Springer-Verlag, Berlin, 2004, xiv+315 pp. MR 2102513
[27] Poizat, B.: A course in model theory. An introduction to contemporary mathematical logic. Springer-Verlag, New York, 2000, xxxii+443 pp.
[28] Szmielew, W.: Elementary properties of Abelian groups. Fund. Math. 41 (1955), 203–271. DOI 10.4064/fm-41-2-203-271
Search
Partner of
