How many varieties of cylindric algebras are there
HTML articles powered by AMS MathViewer
- by H. Andréka and I. Németi PDF
- Trans. Amer. Math. Soc. 369 (2017), 8903-8937 Request permission
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^{|\alpha |}$ many varieties of geometric (i.e., representable) $\alpha$-dimensional cylindric algebras, which means that $2^{|\alpha |}$ 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^{|\alpha |}$ 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
- 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, DOI 10.1007/s00012-009-0022-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
- 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, DOI 10.2307/2275414
- 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
- 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, DOI 10.1007/978-3-319-06025-5_{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, DOI 10.1090/S0002-9947-1988-0961607-5
- 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
- Thomas William Barrett and Hans Halvorson, Morita equivalence, Rev. Symb. Log. 9 (2016), no. 3, 556–582. MR 3569170, DOI 10.1017/S1755020316000186
- 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, DOI 10.1007/978-3-642-35025-2_{3}
- W. J. Blok, Varieties of interior algebras, PhD Dissertation, University of Amsterdam, 1976.
- W. J. Blok, The lattice of modal logics: an algebraic investigation, J. Symbolic Logic 45 (1980), no. 2, 221–236. MR 569394, DOI 10.2307/2273184
- William Craig, Logic in algebraic form, Studies in Logic and the Foundations of Mathematics, Vol. 72, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1974. Three languages and theories. MR 0411962
- 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, DOI 10.1090/S0002-9947-2011-05332-8
- 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
- S. R. Givant, Relation algebras, vol. I: Arithmetic and algebra; vol. II: Complete extensions, representations, varieties, and atom structures, Springer-Verlag, to appear.
- Robert Goldblatt, Varieties of complex algebras, Ann. Pure Appl. Logic 44 (1989), no. 3, 173–242. MR 1020344, DOI 10.1016/0168-0072(89)90032-8
- Paul R. Halmos, Algebraic logic, Chelsea Publishing Co., New York, 1962. MR 0131961
- 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. With an introductory chapter: General theory of algebras; Reprint of the 1971 original. MR 781929
- 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
- 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
- Robin Hirsch and Ian Hodkinson, Step by step—building representations in algebraic logic, J. Symbolic Logic 62 (1997), no. 1, 225–279. MR 1450522, DOI 10.2307/2275740
- Robin Hirsch and Ian Hodkinson, Axiomatising various classes of relation and cylindric algebras, Log. J. IGPL 5 (1997), no. 2, 209–229. MR 1433257, DOI 10.1093/jigpal/5.2.209
- 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. With a foreword by Wilfrid Hodges. MR 1935083
- Peter Jipsen and Henry Rose, Varieties of lattices, Lecture Notes in Mathematics, vol. 1533, Springer-Verlag, Berlin, 1992. MR 1223545, DOI 10.1007/BFb0090224
- Bjarni Jónsson, Varieties of relation algebras, Algebra Universalis 15 (1982), no. 3, 273–298. MR 689767, DOI 10.1007/BF02483728
- 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
- J. X. Madarász, Logic and relativity (in the light of definability theory), PhD Dissertation, ELTE Budapest, 2002, xviii+367pp.
- 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.
- Maarten Marx and Yde Venema, Multi-dimensional modal logic, Applied Logic Series, vol. 4, Kluwer Academic Publishers, Dordrecht, 1997. MR 1427056, DOI 10.1007/978-94-011-5694-3
- J. D. Monk, On the lattice of equational classes of one- and two-dimensional polyadic algebras, Notices Amer. Math. Soc. 16 (1969), 183.
- Donald Monk, On equational classes of algebraic versions of logic. I, Math. Scand. 27 (1970), 53–71. MR 280345, DOI 10.7146/math.scand.a-10987
- Roger D. Maddux, Relation algebras, Studies in Logic and the Foundations of Mathematics, vol. 150, Elsevier B. V., Amsterdam, 2006. MR 2269199
- I. Németi, Varieties of cylindric algebras, Preprint, Budapest, 1985.
- I. Németi, On varieties of cylindric algebras with applications to logic, Ann. Pure Appl. Logic 36 (1987), no. 3, 235–277. MR 915900, DOI 10.1016/0168-0072(87)90019-4
- István Németi, Algebraization of quantifier logics, an introductory overview, Studia Logica 50 (1991), no. 3-4, 485–569. Algebraic logic. MR 1170186, DOI 10.1007/BF00370684
- 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
- Ildikó Sain, On the search for a finitizable algebraization of first order logic, Log. J. IGPL 8 (2000), no. 4, 497–591. MR 1776151, DOI 10.1093/jigpal/8.4.497
- Ildikó Sain and Viktor Gyuris, Finite schematizable algebraic logic, Log. J. IGPL 5 (1997), no. 5, 699–751. MR 1465620, DOI 10.1093/jigpal/5.5.699
- 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
- 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, DOI 10.1093/jigpal/jzr049
- 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.
- 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, DOI 10.1305/ndjfl/1093634658
- 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, DOI 10.1007/BF02631111
- Venema, Y., Many-dimensional modal logic. PhD Dissertation, Amsterdam, 1992. 177pp.
- Yde Venema, Cylindric modal logic, J. Symbolic Logic 60 (1995), no. 2, 591–623. MR 1335139, DOI 10.2307/2275853
- James Owen Weatherall, Are Newtonian gravitation and geometrized Newtonian gravitation theoretically equivalent?, Erkenntnis 81 (2016), no. 5, 1073–1091. MR 3547774, DOI 10.1007/s10670-015-9783-5
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
- MR Author ID: 26015
- 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
- MR Author ID: 130245
- Email: nemeti.istvan@renyi.mta.hu
- Received by editor(s): September 12, 2015
- Received by editor(s) in revised form: September 20, 2016
- Published electronically: August 22, 2017
- © Copyright 2017 American Mathematical Society
- 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
- MathSciNet review: 3710648