On varieties of cylindric algebras with applications to logic (Q1098852)

Some interesting decidability and undecidability results are proved. They have to do with cylindric versions of logic with equality only, or with only monadic predicates. In ordinary first order logic the theories in question are among the simplest decidable theories known. Their cylindric versions turn out to be mostly undecidable; this is the main import of this interesting article. The exact logical counterparts of the cylindric apparatus is carefully formualated in this article, so that the reason behind this paradoxical sounding situation becomes clear. The main results are: (1) The equational theory of minimal \(CA_{\alpha}s\) is r.e. iff \(\alpha\geq \omega\). (2) The equational theory of monadic- generated \(CA_{\alpha}s\) is r.e. iff \(\alpha >2\). For the rest, let \(\alpha >2\) and let K be a class of monadic-generated \(CA_{\alpha}s\). (3) The equational theory of K is either decidable or not r.e. (4) For \(\alpha\) infinite, the equational theory of K is decidable iff there is an \(n\in \omega\) such that all set algebras in K have base of size at most n. (5) For \(\alpha <\omega\), the equational theory of K is decidable iff there is an \(n\in \omega\) such that \(K\subseteq SPL\), where L is the class of all monadic-generated \(CA_{\alpha}s\) generated by at most n 1- dimensional elements. Several other interesting results are proved, too. It is interesting that the unsolvability of diophantine equations plays a role in the proofs.