Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

How many varieties of cylindric algebras are there


Authors: H. Andréka and I. Németi
Journal: Trans. Amer. Math. Soc. 369 (2017), 8903-8937
MSC (2010): Primary 03B10, 03G15, 08B15, 03Gxx; Secondary 03C40, 03A10
DOI: https://doi.org/10.1090/tran/7083
Published electronically: August 22, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Cylindric algebras, or concept algebras as another name, form an interface between algebra, geometry and logic; they were invented by Alfred Tarski around 1947. We prove that there are $ 2^{\vert\alpha \vert}$ many varieties of geometric (i.e., representable) $ \alpha $-dimensional cylindric algebras, which means that $ 2^{\vert\alpha \vert}$ properties of definable relations of (possibly infinitary) models of first order theories can be expressed by formula schemes using $ \alpha $ variables, where $ \alpha $ is infinite. This solves Problem 4.2 in the 1985 Henkin-Monk-Tarski monograph [Cylindric algebras. Part II, Studies in Logic and the Foundations of Mathematics, vol. 115, North-Holland, Amsterdam, 1985]; the problem is restated by Németi [On varieties of cylindric algebras with applications to logic, Ann. Pure Appl. Logic 36 (1987), no. 3, 235-277] and Andréka, Monk, and Németi [Algebraic logic, Colloq. Math. Soc. János Bolyai, Vol. 54, North-Holland, Amsterdam, 1991]. For solving this problem, we devise a new construction, which we then use to solve Problem 2.13 of the 1971 Henkin-Monk-Tarski monograph [Cylindric algebras. Part I, Studies in Logic and the Foundations of Mathematics, vol. 64, North-Holland, Amsterdam, 1971] which concerns the structural description of geometric cylindric algebras. There are fewer varieties generated by locally finite-dimensional cylindric algebras, and we get a characterization of these among all the $ 2^{\vert\alpha \vert}$ varieties. As a by-product, we get a simple recursive enumeration of all the equations true of geometric cylindric algebras, and this can serve as a solution to Problem 4.1 of the 1985 Henkin-Monk-Tarski monograph. All of this has logical content and implications concerning ordinary first order logic with a countable number of variables.


References [Enhancements On Off] (What's this?)

  • [1] H. Andréka, S. D. Comer, J. X. Madarász, I. Németi, and T. Sayed Ahmed, Epimorphisms in cylindric algebras and definability in finite variable logic, Algebra Universalis 61 (2009), no. 3-4, 261-282. MR 2565854, https://doi.org/10.1007/s00012-009-0022-2
  • [2] Hajnal Andréka, Miklós Ferenczi, and István Németi (eds.), Cylindric-like algebras and algebraic logic, Bolyai Society Mathematical Studies, vol. 22, János Bolyai Mathematical Society, Budapest; Springer, Berlin, 2012. MR 3137681
  • [3] Hajnal Andréka, Steven Givant, and István Németi, The lattice of varieties of representable relation algebras, J. Symbolic Logic 59 (1994), no. 2, 631-661. MR 1276639, https://doi.org/10.2307/2275414
  • [4] H. Andréka, J. D. Monk, and I. Németi (eds.), Algebraic logic, Colloquia Mathematica Societatis János Bolyai, vol. 54, North-Holland Publishing Co., Amsterdam, 1991. Papers from the colloquium held in Budapest, August 8-14, 1988. MR 1153415
  • [5] Hajnal Andréka and István Németi, Comparing theories: the dynamics of changing vocabulary, Johan van Benthem on logic and information dynamics, Outst. Contrib. Log., vol. 5, Springer, Cham, 2014, pp. 143-172. MR 3329289, https://doi.org/10.1007/978-3-319-06025-5_6
  • [6] H. Andréka and R. J. Thompson, A Stone-type representation theorem for algebras of relations of higher rank, Trans. Amer. Math. Soc. 309 (1988), no. 2, 671-682. MR 961607, https://doi.org/10.2307/2000932
  • [7] M. Assem, T. Sayed-Ahmed, G. Sági, and D. Sziráki, The number of countable models via agebraic logic, Manuscript 2013. http://real.mtak.hu/id/eprint/16985
  • [8] Thomas William Barrett and Hans Halvorson, Morita equivalence, Rev. Symb. Log. 9 (2016), no. 3, 556-582. MR 3569170, https://doi.org/10.1017/S1755020316000186
  • [9] Nick Bezhanishvili, Varieties of two-dimensional cylindric algebras, Cylindric-like algebras and algebraic logic, Bolyai Soc. Math. Stud., vol. 22, János Bolyai Math. Soc., Budapest, 2012, pp. 37-59. MR 3156394, https://doi.org/10.1007/978-3-642-35025-2_3
  • [10] W. J. Blok, Varieties of interior algebras, PhD Dissertation, University of Amsterdam, 1976.
  • [11] W. J. Blok, The lattice of modal logics: an algebraic investigation, J. Symbolic Logic 45 (1980), no. 2, 221-236. MR 569394, https://doi.org/10.2307/2273184
  • [12] William Craig, Logic in algebraic form: Three languages and theories, Studies in Logic and the Foundations of Mathematics, Vol. 72, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1974. MR 0411962
  • [13] Miklós Ferenczi, The polyadic generalization of the Boolean axiomatization of fields of sets, Trans. Amer. Math. Soc. 364 (2012), no. 2, 867-886. MR 2846356, https://doi.org/10.1090/S0002-9947-2011-05332-8
  • [14] D. M. Gabbay, A. Kurucz, F. Wolter, and M. Zakharyaschev, Many-dimensional modal logics: theory and applications, Studies in Logic and the Foundations of Mathematics, vol. 148, North-Holland Publishing Co., Amsterdam, 2003. MR 2011128
  • [15] S. R. Givant, Relation algebras, vol. I: Arithmetic and algebra; vol. II: Complete extensions, representations, varieties, and atom structures, Springer-Verlag, to appear.
  • [16] Robert Goldblatt, Varieties of complex algebras, Ann. Pure Appl. Logic 44 (1989), no. 3, 173-242. MR 1020344, https://doi.org/10.1016/0168-0072(89)90032-8
  • [17] Paul R. Halmos, Algebraic logic, Chelsea Publishing Co., New York, 1962. MR 0131961
  • [18] Leon Henkin, J. Donald Monk, and Alfred Tarski, Cylindric algebras. Part I, Studies in Logic and the Foundations of Mathematics, vol. 64, North-Holland Publishing Co., Amsterdam, 1985. Reprint of the 1971 original. MR 781929
  • [19] Leon Henkin, J. Donald Monk, and Alfred Tarski, Cylindric algebras. Part II, Studies in Logic and the Foundations of Mathematics, vol. 115, North-Holland Publishing Co., Amsterdam, 1985. MR 781930
  • [20] Leon Henkin, J. Donald Monk, Alfred Tarski, Hajnal Andréka, and István Németi, Cylindric set algebras, Lecture Notes in Mathematics, vol. 883, Springer-Verlag, Berlin-New York, 1981. MR 639151
  • [21] Robin Hirsch and Ian Hodkinson, Step by step--building representations in algebraic logic, J. Symbolic Logic 62 (1997), no. 1, 225-279. MR 1450522, https://doi.org/10.2307/2275740
  • [22] Robin Hirsch and Ian Hodkinson, Axiomatising various classes of relation and cylindric algebras, Log. J. IGPL 5 (1997), no. 2, 209-229. MR 1433257, https://doi.org/10.1093/jigpal/5.2.209
  • [23] Robin Hirsch and Ian Hodkinson, Relation algebras by games, Studies in Logic and the Foundations of Mathematics, vol. 147, North-Holland Publishing Co., Amsterdam, 2002. MR 1935083
  • [24] Peter Jipsen and Henry Rose, Varieties of lattices, Lecture Notes in Mathematics, vol. 1533, Springer-Verlag, Berlin, 1992. MR 1223545
  • [25] Bjarni Jónsson, Varieties of relation algebras, Algebra Universalis 15 (1982), no. 3, 273-298. MR 689767, https://doi.org/10.1007/BF02483728
  • [26] K. Lefever and G. Székely, Interpretation of special relativity in the language of Newtonian kinematics, Logic, Relativity and Beyond, 2nd International Conference, August 9-13, 2015, Budapest, talk in the Symposium of Equivalences of Theories part. http://www.renyi.hu/conferences/lrb15/slides/LRB15-Lefever-Szekely.pdf
  • [27] J. X. Madarász, Logic and relativity (in the light of definability theory), PhD Dissertation, ELTE Budapest, 2002, xviii+367pp.
  • [28] J. X. Madarász and G. Székely, Comparing relativistic and Newtonian dynamics in first-order logic, in The Vienna Circle in Hungary, Veröffentlichungen des Instituts Wiener Kreis, Vol. 16, A. Máté, M. Rédei, and F. Stadler, eds., Springer, Vienna, 2011, pp. 155-179.
  • [29] Maarten Marx and Yde Venema, Multi-dimensional modal logic, Applied Logic Series, vol. 4, Kluwer Academic Publishers, Dordrecht, 1997. MR 1427056
  • [30] J. D. Monk, On the lattice of equational classes of one- and two-dimensional polyadic algebras, Notices Amer. Math. Soc. 16 (1969), 183.
  • [31] Donald Monk, On equational classes of algebraic versions of logic. I, Math. Scand. 27 (1970), 53-71. MR 0280345, https://doi.org/10.7146/math.scand.a-10987
  • [32] Roger D. Maddux, Relation algebras, Studies in Logic and the Foundations of Mathematics, vol. 150, Elsevier B. V., Amsterdam, 2006. MR 2269199
  • [33] I. Németi, Varieties of cylindric algebras, Preprint, Budapest, 1985.
  • [34] I. Németi, On varieties of cylindric algebras with applications to logic, Ann. Pure Appl. Logic 36 (1987), no. 3, 235-277. MR 915900, https://doi.org/10.1016/0168-0072(87)90019-4
  • [35] István Németi, Algebraization of quantifier logics, an introductory overview, Studia Logica 50 (1991), no. 3-4, 485-569. MR 1170186, https://doi.org/10.1007/BF00370684
  • [36] Vladimir V. Rybakov, Admissibility of logical inference rules, Studies in Logic and the Foundations of Mathematics, vol. 136, North-Holland Publishing Co., Amsterdam, 1997. MR 1454360
  • [37] Ildikó Sain, On the search for a finitizable algebraization of first order logic, Log. J. IGPL 8 (2000), no. 4, 497-591. MR 1776151, https://doi.org/10.1093/jigpal/8.4.497
  • [38] Ildikó Sain and Viktor Gyuris, Finite schematizable algebraic logic, Log. J. IGPL 5 (1997), no. 5, 699-751. MR 1465620, https://doi.org/10.1093/jigpal/5.5.699
  • [39] Ildikó Sain and Richard J. Thompson, Strictly finite schema axiomatization of quasipolyadic algebras, Algebraic logic (Budapest, 1988) Colloq. Math. Soc. János Bolyai, vol. 54, North-Holland, Amsterdam, 1991, pp. 539-571. MR 1153440
  • [40] Gábor Sági and Dorottya Sziráki, Some variants of Vaught's conjecture from the perspective of algebraic logic, Log. J. IGPL 20 (2012), no. 6, 1064-1082. MR 2999224, https://doi.org/10.1093/jigpal/jzr049
  • [41] T. Sayed-Ahmed, Splitting methods in algebraic logic: proving results on non-atom-canonicity, non-finite axiomatizability and non-first-order definability for cylindric and relation algebras, Preprint arXiv:1503.02189, 2015.
  • [42] György Serény, Isomorphisms of finite cylindric set algebras of characteristic zero, Notre Dame J. Formal Logic 34 (1993), no. 2, 284-294. MR 1231290, https://doi.org/10.1305/ndjfl/1093634658
  • [43] András Simon, Finite schema completeness for typeless logic and representable cylindric algebras, Algebraic logic (Budapest, 1988) Colloq. Math. Soc. János Bolyai, vol. 54, North-Holland, Amsterdam, 1991, pp. 665-670. MR 1153445, https://doi.org/10.1007/BF02631111
  • [44] Venema, Y., Many-dimensional modal logic. PhD Dissertation, Amsterdam, 1992. 177pp.
  • [45] Yde Venema, Cylindric modal logic, J. Symbolic Logic 60 (1995), no. 2, 591-623. MR 1335139, https://doi.org/10.2307/2275853
  • [46] James Owen Weatherall, Are Newtonian gravitation and geometrized Newtonian gravitation theoretically equivalent?, Erkenntnis 81 (2016), no. 5, 1073-1091. MR 3547774, https://doi.org/10.1007/s10670-015-9783-5

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03B10, 03G15, 08B15, 03Gxx, 03C40, 03A10

Retrieve articles in all journals with MSC (2010): 03B10, 03G15, 08B15, 03Gxx, 03C40, 03A10


Additional Information

H. Andréka
Affiliation: Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Reáltanoda st. 13-15, H-1053 Hungary
Email: andreka.hajnal@renyi.mta.hu

I. Németi
Affiliation: Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Reáltanoda st. 13-15, H-1053 Hungary
Email: nemeti.istvan@renyi.mta.hu

DOI: https://doi.org/10.1090/tran/7083
Received by editor(s): September 12, 2015
Received by editor(s) in revised form: September 20, 2016
Published electronically: August 22, 2017
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society