Skip to main content
SpringerLink
Log in

Undecidability of representability for lattice-ordered semigroups and ordered complemented semigroups

  • Published:
Algebra universalis Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Andréka H.: Representations of distributive lattice-ordered semigroups with binary relations. Algebra Universalis 28, 12–25 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  2. Andréka H., Mikulás S.: Axiomatizability of positive algebras of binary relations. Algebra Universalis 66, 7–34 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  3. 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)

  4. Evans T.: Embeddability and the word problem. J. Lond. Math. Soc. 28, 76–80 (1953)

    Article  MathSciNet  MATH  Google Scholar 

  5. Hirsch R., Hodkinson I.: Representability is not decidable for finite relation algebras. Trans. Amer. Math. Soc. 353, 1403–1425 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  6. Hirsch R., Jackson M.: Undecidability of representability as binary relations. J. Symbolic Logic 77, 1211–1244 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  7. Jónsson, B., Tarski, A.: Representation problems for relation algebras. Bull. Amer. Math. Soc. 54, 80 (1948)

  8. Lyndon R.C.: The representation of relational algebras. Ann. of Math. (2). 51, 707–729 (1950)

    Article  MathSciNet  MATH  Google Scholar 

  9. Maddux, R.D.: Relation Algebras. Studies in Logic and the Foundation of Mathematics, vol. 150. Elsevier B.V., Amsterdam (2006)

  10. 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)

  11. Monk D.: On representable relation algebras. Michigan Math. J. 11, 207–210 (1964)

    Article  MathSciNet  MATH  Google Scholar 

  12. 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)

  13. Tarski A.: On the calculus of relations. J. Symbolic Logic. 6, 73–89 (1941)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Statistics, La Trobe University, Bundoora Victoria, 3086, Australia

    Murray Neuzerling

Authors
  1. Murray Neuzerling
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Murray Neuzerling.

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

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00012-016-0409-9

2010 Mathematics Subject Classification

Key words and phrases

Search

Navigation