The equational theory of CA ₃ is undecidable1

E-ISSN： 1943-5886|45|2|311-316

ISSN： 0022-4812

Source： The Journal of Symbolic Logic, Vol.45, Iss.2, 1980-06, pp. : 311-316

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

There is no algorithm for determining whether or not an equation is true in every 3-dimensional cylindric algebra. This theorem completes the solution to the problem of finding those values of α and β for which the equational theories of CA_α and RCA_β are undecidable. (CA _α and RCA_β are the classes of α-dimensional cylindric algebras and representable β-dimensional cylindric algebras. See [4] for definitions.) This problem was considered in [3]. It was known that RCA ₀ = CA ₀ and RCA ₁ = CA ₁ and that the equational theories of these classes are decidable. Tarski had shown that the equational theory of relation algebras is undecidable and, by utilizing connections between relation algebras and cylindric algebras, had also shown that the equational theories of CA_α and RCA_β are undecidable whenever 4 ≤ α and 3 ≤ β. (Tarski's argument also applies to some varieties K ⊆ RCA_β with 3 ≤ β and to any variety K such that RCA_α ⊆ K ⊆ CA_α and 4 ≤ α.)