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)

Request Permissions   Purchase Content 
 
 

 

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?)


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