Decidability of relation algebras with weakened associativity
Istvàn Németi · Proceedings of the American Mathematical Society · 1987
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 NA ⊃ WA ⊃ SA ⊃ RA \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.