Abstract
We prove that the problems of representing a finite ordered complemented semigroup or finite lattice-ordered semigroup as an algebra of binary relations over a finite set are undecidable. In the case that complementation is taken with respect to a universal relation, this result can be extended to infinite representations of ordered complemented semigroups.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Andréka H.: Representations of distributive lattice-ordered semigroups with binary relations. Algebra Universalis 28, 12–25 (1991)
Andréka H., Mikulás S.: Axiomatizability of positive algebras of binary relations. Algebra Universalis 66, 7–34 (2011)
Bredikhin, D.A.: An abstract characterization of some classes of algebras of binary relations. In: Algebra and Number Theory, No. 2, pp. 3–19. Kabardino-Balkarsk. Gos. Univ., Nalchik (1977) (Russian)
Evans T.: Embeddability and the word problem. J. Lond. Math. Soc. 28, 76–80 (1953)
Hirsch R., Hodkinson I.: Representability is not decidable for finite relation algebras. Trans. Amer. Math. Soc. 353, 1403–1425 (2001)
Hirsch R., Jackson M.: Undecidability of representability as binary relations. J. Symbolic Logic 77, 1211–1244 (2012)
Jónsson, B., Tarski, A.: Representation problems for relation algebras. Bull. Amer. Math. Soc. 54, 80 (1948)
Lyndon R.C.: The representation of relational algebras. Ann. of Math. (2). 51, 707–729 (1950)
Maddux, R.D.: Relation Algebras. Studies in Logic and the Foundation of Mathematics, vol. 150. Elsevier B.V., Amsterdam (2006)
Mikulás, S.: Axiomatizability of algebras of binary relations. In: Classical and New Paradigms of Computation and their Complexity Hierarchies. Trends Log. Stud. Log. Libr., vol. 23, pp. 187–205. Kluwer Acad. Publ., Dordrecht (2004)
Monk D.: On representable relation algebras. Michigan Math. J. 11, 207–210 (1964)
Schein B.M.: Representation of subreducts of Tarski relation algebras. In: Algebraic Logic (Budapest, 1988). Colloq. Math. Soc. János Bolyai, vol. 54, pp. 621–635. North-Holland, Amsterdam (1991)
Tarski A.: On the calculus of relations. J. Symbolic Logic. 6, 73–89 (1941)
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by I. Hodkinson.
The author would like to thank Marcel Jackson, Ian Hodkinson and the anonymous reviewer for their valuable comments and suggestions.
Rights and permissions
About this article
Cite this article
Neuzerling, M. Undecidability of representability for lattice-ordered semigroups and ordered complemented semigroups. Algebra Univers. 76, 431–443 (2016). https://doi.org/10.1007/s00012-016-0409-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00012-016-0409-9