Mathematical Logic Quarterly 55 (2):138-153 (2009)

Built on the foundations laid by Peirce, Schröder, and others in the 19th century, the modern development of relation algebras started with the work of Tarski and his colleagues [21, 22]. They showed that relation algebras can capture strong first-order theories like ZFC, and so their equational theory is undecidable. The less expressive class WA of weakly associative relation algebras was introduced by Maddux [7]. Németi [16] showed that WA's have a decidable universal theory. There has been extensive research on increasing the expressive power of WA by adding new operations [1, 4, 11, 13, 20]. Extensions of this kind usually also have decidable universal theories. Here we give an example – extending WA's with set-theoretic projection elements – where this is not the case. These “logical” connectives are set-theoretic counterparts of the axiomatic quasi-projections that have been investigated in the representation theory of relation algebras [22, 6, 19]. We prove that the quasi-equational theory of the extended class PWA is not recursively enumerable. By adding the difference operator D one can turn WA and PWA to discriminator classes where each universal formula is equivalent to some equation. Hence our result implies that the projections turn the decidable equational theory of “WA + D ” to non-recursively enumerable
Keywords decision problems  quasi‐projections  Weakly associative relation algebras
Categories (categorize this paper)
DOI 10.1002/malq.200710074
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,512
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

On the Calculus of Relations.Alfred Tarski - 1941 - Journal of Symbolic Logic 6 (3):73-89.
Finitary Algebraic Logic.Roger D. Maddux - 1989 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 35 (4):321-332.
Finitary Algebraic Logic.Roger D. Maddux - 1989 - Mathematical Logic Quarterly 35 (4):321-332.
On Varieties of Cylindric Algebras with Applications to Logic.I. Németi - 1987 - Annals of Pure and Applied Logic 36:235-277.

View all 8 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles


Added to PP index

Total views
17 ( #639,437 of 2,520,896 )

Recent downloads (6 months)
1 ( #405,457 of 2,520,896 )

How can I increase my downloads?


My notes