Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Decidability of relation algebras with weakened associativity

Author: I. Németi
Journal: Proc. Amer. Math. Soc. 100 (1987), 340-344
MSC: Primary 03G15; Secondary 03B25, 03G25, 08A50
MathSciNet review: 884476
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [HMT71] L. Henkin, J. D. Monk and A. Tarski, Cylindric algebras, Part I, North-Holland, 1971, 1985. MR 781929 (86m:03095a)
  • [HMT85] -, Cylindric algebras, Part II, North-Holland, 1985. MR 781930 (86m:03095b)
  • [J82] B. Jónsson, Varieties of relation algebras, Algebra Universalis 15 (1982), 273-298. MR 689767 (84g:08023)
  • [M78] R. Maddux, Topics in relation algebras, Doctoral Dissertation, Berkeley, 1978.
  • [M80] -, The equational theory of $ \operatorname{CA}_3$ is undecidable, J. Symbolic Logic 45 (1980), 311-316. MR 569401 (81e:03060)
  • [M82] -, Some varieties containing relation algebras, Trans. Amer. Math. Soc. 272 (1982), 501-526. MR 662049 (84a:03079)
  • [M83] -, A sequent calculus for relation algebras, Ann. Pure Appl. Logic 25 (1983), 73-101. MR 722170 (85h:03067)
  • [N84] I. Németi, The variety $ \operatorname{CA}_3$ is not generated by its finite members, Preprint, 1984.
  • [N85] -, Logic with three variables has Gödel's incompleteness property--thus free cylindric algebras are not atomic, Preprint, 1985.
  • [S79] R. Schönfeld, An undecidability result for RA's, J. Symbolic Logic 44 (1979), 111-115. MR 523495 (80f:03074)
  • [TG] 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.
  • [T79] W. Taylor, Equational logic, Houston J. Math. 1979, Survey. MR 546853 (80j:03042)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03G15, 03B25, 03G25, 08A50

Retrieve articles in all journals with MSC: 03G15, 03B25, 03G25, 08A50

Additional Information

Article copyright: © Copyright 1987 American Mathematical Society

American Mathematical Society