Decidability of relation algebras with weakened associativity
HTML articles powered by AMS MathViewer
- by I. Németi PDF
- Proc. Amer. Math. Soc. 100 (1987), 340-344 Request permission
Abstract:
Tarski showed that mathematics can be built up in the equational theory EqRA of relation algebras (RA’s), hence EqRA is undecidable. He raised the problem "how much associativity of relation composition is needed for this result." Maddux defined the classes $\operatorname {NA} \supset \operatorname {WA} \supset \operatorname {SA} \supset \operatorname {RA}$ by gradually weakening the associativity of relation composition, and he proved that the equational theory of SA is still undecidable. We showed, elsewhere, that mathematics can be built up in SA, too. In the present paper we prove that the equational theories of WA and NA are already decidable. Hence mathematics cannot be built up in WA or NA. This solves a problem in the book by Tarski and Givant.References
- Leon Henkin, J. Donald Monk, and Alfred Tarski, Cylindric algebras. Part I, Studies in Logic and the Foundations of Mathematics, vol. 64, North-Holland Publishing Co., Amsterdam, 1985. With an introductory chapter: General theory of algebras; Reprint of the 1971 original. MR 781929
- Leon Henkin, J. Donald Monk, and Alfred Tarski, Cylindric algebras. Part I, Studies in Logic and the Foundations of Mathematics, vol. 64, North-Holland Publishing Co., Amsterdam, 1985. With an introductory chapter: General theory of algebras; Reprint of the 1971 original. MR 781929
- Bjarni Jónsson, Varieties of relation algebras, Algebra Universalis 15 (1982), no. 3, 273–298. MR 689767, DOI 10.1007/BF02483728 R. Maddux, Topics in relation algebras, Doctoral Dissertation, Berkeley, 1978.
- Roger Maddux, The equational theory of $\textrm {CA}_{3}$ is undecidable, J. Symbolic Logic 45 (1980), no. 2, 311–316. MR 569401, DOI 10.2307/2273191
- Roger Maddux, Some varieties containing relation algebras, Trans. Amer. Math. Soc. 272 (1982), no. 2, 501–526. MR 662049, DOI 10.1090/S0002-9947-1982-0662049-7
- Roger Maddux, A sequent calculus for relation algebras, Ann. Pure Appl. Logic 25 (1983), no. 1, 73–101. MR 722170, DOI 10.1016/0168-0072(83)90055-6 I. Németi, The variety $\operatorname {CA}_3$ is not generated by its finite members, Preprint, 1984. —, Logic with three variables has Gödel’s incompleteness property—thus free cylindric algebras are not atomic, Preprint, 1985.
- Wolfgang Schönfeld, An undecidability result for relation algebras, J. Symbolic Logic 44 (1979), no. 1, 111–115. MR 523495, DOI 10.2307/2273710 A. Tarski and S. Givant, A formalization of set theory without variables, Amer. Math. Soc. Colloq. Publ., vol. 41, Amer. Math. Soc., Providence, R.I., 1986.
- Walter Taylor, Equational logic, Houston J. Math. Survey (1979), iii+83. MR 546853
Additional Information
- © Copyright 1987 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 100 (1987), 340-344
- MSC: Primary 03G15; Secondary 03B25, 03G25, 08A50
- DOI: https://doi.org/10.1090/S0002-9939-1987-0884476-5
- MathSciNet review: 884476