Repository | Journal | Volume | Article

235076

Complexity of equational theory of relational algebras with standard projection elements

Szabolcs MikulásIldikó SainSimon András

pp. 2159-2182

Abstract

The class (mathsf{TPA}) of t rue p airing a lgebras is defined to be the class of relation algebras expanded with concrete set theoretical projection functions. The main results of the present paper is that neither the equational theory of (mathsf{TPA}) nor the first order theory of (mathsf{TPA}) are decidable. Moreover, we show that the set of all equations valid in (mathsf{TPA}) is exactly on the (Pi ^1_1) level. We consider the class (mathsf{TPA}^-) of the relation algebra reducts of (mathsf{TPA})’s, as well. We prove that the equational theory of (mathsf{TPA}^-) is much simpler, namely, it is recursively enumerable. We also give motivation for our results and some connections to related work.

Publication details

Published in:

Székely Gergely (2015) Logic and relativity theory. Synthese 192 (7).

Pages: 2159-2182

DOI: 10.1007/s11229-015-0689-1

Full citation:

Mikulás Szabolcs, Sain Ildikó, András Simon (2015) „Complexity of equational theory of relational algebras with standard projection elements“. Synthese 192 (7), 2159–2182.