Abstract
Let S be a signature of operations and relations definable in relation algebra (e.g. converse, composition, containment, union, identity, etc.), let R(S) be the class of all S-structures isomorphic to concrete algebras of binary relations with concrete interpretations for symbols in S, and let F(S) be the class of S-structures isomorphic to concrete algebras of binary relations over a finite base. To prove that membership of R(S) or F(S) for finite S-structures is undecidable, we reduce from a known undecidable problem—here we use the tiling problem, the partial group embedding problem and the partial group finite embedding problem to prove undecidability of finite membership of R(S) or F(S) for various signatures S. It follows that the equational theory of R(S) is undecidable whenever S includes the boolean operators and composition. We give an exposition of the reduction from the tiling problem and the reduction from the group embedding problem, and summarize what we know about the undecidability of finite membership of R(S) and of F(S) for different signatures S.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
One such variant is when (i) the instances are restricted to those \(\tau \) that contain a special tile whose four sides all have a fixed ‘white’ colour that occurs only on this one tile, and (ii) \(\tau \) is a yes-instance iff each tile in \(\tau \) occurs in some tiling of the plane. This is the variant actually used in the proof, but these extra particulars will not concern us in this outline.
- 2.
A relation algebra is integral if its identity element \(1'\) is an atom.
References
Andréka, H., Givant, S., & Németi, I. (1997). Decision problems for equational theories of relation algebras. Memoirs of the American Mathematical Society, 126(604).
Andréka, H., Givant, S., & Németi, I. (2020). Nonrepresentable relation algebras from group system. The Review of Symbolic Logic, 13(4), 861–881. arXiv:1809.05473
Andréka, H., Monk, J., & Németi, I. (eds.). (1991). Algebraic logic. In Colloquia Mathematica Societatis Janos Bolyai (Vol. 54). North-Holland, Amsterdam.
Andréka, H., & Németi, I. (2013). Reducing first-order logic to \({{\sf Df\it }_{3}}\). In H. Andréka, M. Ferenczi, & I. Németi (Eds.), Cylindric-like algebras and algebraic logic (Vol. 22, pp. 15–35). Bolyai Society Mathematical Studies. Springer.
Berger, R. (1966). The undecidability of the domino problem, Memoirs (Vol. 66). Providence, Rhode Island: American Mathematical Society.
Comer, S. (1984). Combinatorial aspects of relations. Algebra Universalis, 18, 77–94.
Evans, T. (1953). Embeddability and the word problem. Journal of the London Mathematical Society, 28, 76–80.
Givant, S. (1988). Tarski’s development of logic and mathematics based on the calculus of relations. In Andréka et al. (Eds.), Colloquia Mathematica Societatis Janos Bolyai (Vol. 54, pp. 189–215). North-Holland, Amsterdam.
Givant, S. (2006). The calculus of relations as a foundation for mathematics. Journal of Automated Reasoning, 37(4), 277–322.
Givant, S., & Andréka, H. (2002). Groups and algebras of binary relations. The Bulletin of Symbolic Logic, 8, 38–64.
Hall, T. E., Kublanovskii, S. I., Margolis, S., Sapir, M. V., & Trotter, P. G. (1997). Algorithmic problems for finite groups and finite 0-simple semigroups. Journal of Pure and Applied Algebra, 119, 75–96.
Hirsch, R. (1995). Completely representable relation algebras. Bulletin of the Interest Group in Propositional and Predicate Logics, 3(1), 77–92.
Hirsch, R. (2018). Decidability of equational theories for subsignatures of relation algebra. In: Proceedings of the Seventh International Conference of Relational and Algebraic Methods in Computer Science.
Hirsch, R., & Hodkinson, I. (2002). Relation algebras by games. North-Holland, Amsterdam: Elsevier Science.
Hirsch, R., & Jackson, M. (2012). Undecidability of representability as binary relations. Journal of Symbolic Logic, 77, 1211–1244.
Jackson, M. (1999). Some undecidable embedding problems for finite semigroups. Proceedings of the Edinburgh Mathematical Society, 42, 113–125.
Jackson, M. (2000). The embeddability of ring and semigroup amalgams is undecidable. Journal of the Australian Mathematical Society, Series A, 69, 272–286.
Jackson, M., & Volkov, M. V. (2009). Undecidable problems for completely 0-simple semigroups. Journal of Pure and Applied Algebra, 213, 1961–1978.
Jónsson, B., & Tarski, A. (1952). Boolean algebras with operators, II. American Journal of Mathematics, 74, 127–162.
Kharlampovich, O., & Sapir, M. V. (1995). Algorithmic problems in varieties. International Journal of Algebra and Computation, 5(4–5), 379–602.
Kublanovsky, S., & Sapir, M. V. (1998). Potential divisibility in finite semigroups is undecidable. International Journal of Algebra and Computation, 8, 671–679.
Maddux, R. D. (1980). The equational theory of \({\rm {CA}}_{3}\) is undecidable. The Journal of Symbolic Logic, 45(2), 311–316. http://www.jstor.org/stable/2273191.
Maddux, R. D. (1982). Some varieties containing relation algebras. Transactions of the American Mathematical Society, 272(2), 501–526.
Maddux, R. D. (1994). A perspective on the theory of relation algebras. Algebra Universalis, 31, 456–465.
Németi, I. (1986). Free algebras and decidability in algebraic logic. Doctor of Science dissertation, Hungarian Academy of Sciences.
Neuzerling, M. (2016). Undecidability of representability for lattice-ordered semigroups and ordered complemented semigroups. Algebra universalis, 76, 431–443.
Post, E. (1947). Recursive unsolvability of a problem of Thue. Journal of Symbolic Logic, 12(1), 1–11.
Sapir, M. V. (1996). Eventually \({\mathscr{H}}\)-related sets and systems of equations over finite semigroups and rings. Journal of Algebra, 183, 365–377.
Slobodskoĭ, A. M. (1981). Undecidability of the universal theory of finite groups. Algebra i Logika, 20(207–230), 251.
Tarski, A., & Givant, S. (1987). A formalization of set theory without variables. No. 41 in Colloquium Publications. American Mathematical Society, Providence, Rhode Island.
Vaught, R. (1962). On a theorem of Cobham concerning undecidable theories. In Logic, methodology and philosophy of science, Proceedings of the 1960 International Congress (pp. 14–25). Stanford University Press.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Hirsch, R., Hodkinson, I., Jackson, M. (2021). Undecidability of Algebras of Binary Relations. In: Madarász, J., Székely, G. (eds) Hajnal Andréka and István Németi on Unity of Science. Outstanding Contributions to Logic, vol 19. Springer, Cham. https://doi.org/10.1007/978-3-030-64187-0_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-64187-0_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-64186-3
Online ISBN: 978-3-030-64187-0
eBook Packages: Religion and PhilosophyPhilosophy and Religion (R0)