Undecidability of representability as binary relations
- 1 December 2012
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 77 (4) , 1211-1244
Abstract
In this article we establish the undecidability of representability and of finite representability as algebras of binary relations in a wide range of signatures. In particular, representability and finite representability are undecidable for Boolean monoids and lattice ordered monoids, while representability is undecidable for Jónsson's relation algebra. We also establish a number of undecidability results for representability as algebras of injective functions.Keywords
This publication has 43 references indexed in Scilit:
- Relatively inherently nonfinitely q-based semigroupsTransactions of the American Mathematical Society, 2008
- Dynamic algebras as a well-behaved fragment of relation algebras2006
- The Class of Representable Ordered Monoids has a Recursively Enumerable, Universal Axiomatisation but it is Not Finitely AxiomatisableLogic Journal of the IGPL, 2005
- Some undecidable embedding problems for finite semigroupsProceedings of the Edinburgh Mathematical Society, 1999
- The equational theory of union-free algebras of relationsAlgebra universalis, 1995
- A remark on representable positive cylindric algebrasAlgebra universalis, 1991
- Representations of distributive lattice-ordered semigroups with binary relationsAlgebra universalis, 1991
- Decidability of Relation Algebras with Weakened AssociativityProceedings of the American Mathematical Society, 1987
- Unsolvability of the universal theory of finite groupsAlgebra and Logic, 1981
- Representation of modular lattices and of relation algebrasTransactions of the American Mathematical Society, 1959