Complexity of equations valid in algebras of relations. II: Finite axiomatizations (Q1377626): Difference between revisions

[This article is reviewed together with Part I above: ibid. 89, No. 2-3, 149-209 (1997; Zbl 0898.03023).] In 1988, \textit{B. Jónsson} proved that the class of representable relation algebras is not axiomatizable by any set of equations with only a finite number of variables [``The theory of binary relations'', in: H. Andréka et al. (eds.), Algebraic logic, Pap. Colloq., Budapest/Hung. 1988, Colloq. Math. Soc. János Bolyai 54, 245-292 (1991; Zbl 0760.03018), Theorem 3.5.6.]. (This fact was also mentioned by Tarski in a lecture in 1974.) This paper contains several extensions of Jónsson's theorem to the representable cylindric and polyadic equality algebras of dimension 3 or more. For one example, assume \(n\geq 3\), and let \(\Sigma\) be an equational axiomatization of a class \({\mathbf K}\) of representable cylindric algebras of dimension \(n\) such that \({\mathbf K}\) contains all \(n\)-dimensional cylindric set algebras of dimension \(n\) over an infinite base. Let be \(k,l<n\) and \(m<\omega\). Then \(\Sigma\) has infinitely many equations in which the following items must occur: complementation, meet or join, a diagonal element with index \(l\), more than \(k\) cylindrifications, and more than \(m\) variables. Many other results are obtained by a systematic investigation of reducts of cylindric, relation, and polyadic algebras. In many cases the varieties so obtained are shown to be finitely axiomatizable. The nonfinitizability results are given in part I, while part II contains finite axiomatizations. The paper concludes with a diagram illustrating all the results together with open problems.