Hostname: page-component-745bb68f8f-cphqk Total loading time: 0 Render date: 2025-02-04T15:03:32.165Z Has data issue: false hasContentIssue false
  • English
  • Français

The equational theory of CA3 is undecidable1

Published online by Cambridge University Press:  12 March 2014

Roger Maddux
Roger Maddux*
Affiliation:
Iowa State University, Ames, Iowa 50010
Get access Rights & Permissions [Opens in a new window]

Extract

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 RCA0 = CA0 and RCA1 = CA1 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 ≤ α.)

Thus the only cases left open in 1961 were CA2, RCA2 and CA3. Shortly there-after Henkin proved, in one of Tarski's seminars at Berkeley, that the equational theory of CA2 is decidable, and Scott proved that the set of valid sentences in a first-order language with only two variables is recursive [11]. (For a more model-theoretic proof of Scott's theorem see [9].) Scott's result is equivalent to the decidability of the equational theory of RCA2, so the only case left open was CA3.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 45 , Issue 2 , June 1980 , pp. 311 - 316
Copyright
Copyright © Association for Symbolic Logic 1980

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

1

The results in this paper are part of Chapter 12 of the author's doctoral dissertation, which was submitted to the University of California, Berkeley, with Alfred Tarski as advisor.

References

REFERENCES

[1]Davis, M., Computability and solvability, McGraw-Hill, New York, 1958.Google Scholar
[2]Halmos, P. R., Algebraic logic. I, Monadic Boolean algebras, Compositio Mathematica, vol. 12 (1956), pp. 217–249. (Reprinted in Algebraic logic, Chelsea, New York, 1962, pp. 37–72.)Google Scholar
[3]Henkin, L. and Tarski, A., Cylindric algebras. Lattice theory, Proceedings of Symposia in Pure Mathematics, vol. 2 (Dilworth, R. P., Editor), American Mathematical Society, Providence, R. I., 1961, pp. 83–113.Google Scholar
[4]Henkin, L., Monk, J. D. and Tarski, A., Cylindric algebras. Part I, North-Holland, Amsterdam, 1971.Google Scholar
[5]Jaśkowski, S., Sur les variables propositionelles dépendantes, Studia Societatis Scientiarum Torunensis Sec. A, vol. 1 (1948), pp. 17–21.Google Scholar
[6]Jaśkowski, S., Undecidability of first order sentences in the theory of free groupoids, Fundamenta Mathematicae, vol. 43 (1956), pp. 36–45.CrossRefGoogle Scholar
[7]Maddux, R. D., The equational theory of CA3 is undecidable, Notices of the American Mathematical Society, vol. 23 (1976), p. A–19.Google Scholar
[8]Monk, J. D., Review of [10], Mathematical Reviews, vol. 38, no. 5 (1969), #4311, p. 768.Google Scholar
[9]Mortimer, M., On languages with two variables, Zeitschrift für Mathematische Logik and Grundlagen der Mathematik, vol. 21 (1975), pp. 135–140.CrossRefGoogle Scholar
[10]Pieczkowski, A., Undecidability of the homogeneous formulas of degree 3 of the predicate calculus, Studia Logica, vol. 22 (1968), pp. 7–16.CrossRefGoogle Scholar
[11]Scott, D., A decision method for validity of sentences in two variables, this Journal, vol. 27 (1962), p. 477.Google Scholar