How many varieties of cylindric algebras are there

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.