Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-23T05:37:13.977Z Has data issue: false hasContentIssue false
  • English
  • Français

Undecidability of representability as binary relations

Published online by Cambridge University Press:  12 March 2014

Robin Hirsch  and
Marcel Jackson
Robin Hirsch
Affiliation:
Department of Computer Science, University College London, London WC1E 6BT, UK, E-mail: [email protected]
Marcel Jackson
Affiliation:
Department of Mathematics and Statistics, La Trobe University, Victoria 3086, Australia, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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

Relation algebrabinary relationsrepresentabilityBoolean monoidlattice ordered monoidBrandt semigroup
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 77 , Issue 4 , December 2012 , pp. 1211 - 1244
Copyright
Copyright © Association for Symbolic Logic 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCE

[1]Albert, A. A., Quasigroups I, Transactions of the American Mathematical Society, vol. 54 (1943), pp. 507–519.CrossRefGoogle Scholar
[2]Andréka, H., On the ‘union-relation composition’ reducts of relation algebras, Abstracts of Papers Presented to the American Mathematical Society, vol. 10 (1989), no. 2, p. 174, full, unpublished manuscript called ‘On the representation problem of distributive semilattice-ordered semigroups’, Mathematical Institute, Hungarian Academy of Sciences, Budapest.Google Scholar
[3]Andréka, H., Representation of distributive lattice-ordered semigroups with binary relations, Algebra Universalis, vol. 28 (1991), pp. 12–25.CrossRefGoogle Scholar
[4]Andréka, H. and Bredikhin, D., The equational theory of union-free algebras of relations, Algebra Universalis, vol. 33 (1995), pp. 516–532.CrossRefGoogle Scholar
[5]Andréka, H., Monk, D., and Németi, I. (editors), Algebraic logic, Colloquia mathematica Societatis Jànos Bolyai, vol. 54, North-Holland, Amsterdam, 1991.Google Scholar
[6]Bredikhin, D. A., An abstract characterization of some classes of algebras of binary relations, Algebra and number theory, no. 2, Kabardino-Balkarsk. Gos. Univ., Nalchik, 1977, in Russian, pp. 319.Google Scholar
[7]Bredikhin, D. A., Reducts of Tarski relation algebras, Algebra and Logic, vol. 37 (1998), pp. 1–8.CrossRefGoogle Scholar
[8]Bredikhin, D. A. and Schein, B. M., Representations of ordered semigroups and lattices by binary relations, Colloquium Mathematicum, vol. 39 (1978), pp. 1–12.CrossRefGoogle Scholar
[9]Comer, S., A remark on representable positive cylindric algebras, Algebra Universalis, vol. 28 (1991), pp. 150–151.CrossRefGoogle Scholar
[10]Desharnais, J., Möller, B., and Struth, G., Kleene algebra with domain, ACM Transactions on Computational Logic, vol. 7 (2006), pp. 798–833.CrossRefGoogle Scholar
[11]Evans, T., Embeddability and the word problem, Journal of the London Mathematical Society, vol. 28 (1953), pp. 76–80.CrossRefGoogle Scholar
[12]Fountain, J., Free right type a semigroups, Glasgow Mathematical Journal, vol. 33 (1991), pp. 135–148.CrossRefGoogle Scholar
[13]Freyd, P. and Scedrov, A., Categories, allegories, Mathematical Library, vol. 39, North-Holland, Amsterdam, 1990.Google Scholar
[14]Garvac'kii, V. S., ∩-semigroups of transformations, Theory of semigroups and its applications 2, Izdat. Saratov Uni., Saratov, 1971, in Russian, pp. 2–13.Google Scholar
[15]Göller, S., Lohrey, M., and Lutz, C., PDL with intersection and converse: satisfiability and infinite-state model checking, this Journal, vol. 74 (2009), pp. 279–314.Google Scholar
[16]Gould, V. and Kambites, M., Faithful functors from cancellative categories to cancellative monoids with an application to abundant semigroups, International Journal of Algebra and Compututation, vol. 15 (2005), pp. 683–698.CrossRefGoogle Scholar
[17]Hall, T. E., Kublanovsky, S. I., Margolis, S., Sapir, M. V., and Trotter, P. G., Decidable and undecidable problems related to finite 0-simple semigroups, Journal of Pure and Applied Algebra, vol. 119 (1997), pp. 75–96.CrossRefGoogle Scholar
[18]Hardin, C. and Kozen, D., The complexity of the Horn theory of REL, Technical Report TR2003-1896, Computer Science Department, Cornell University, May 2003.Google Scholar
[19]Higman, G., A finitely generated infinite simple group, Journal of the London Mathematical Society, vol. 26 (1951), pp. 61–64.CrossRefGoogle Scholar
[20]Hirsch, R., The class of representable ordered monoids has a recursively enumerable, universal axiomatisation but it is not finitely axiomatisable, Logic Journal of the IGPL, vol. 13 (2005), pp. 159–171.CrossRefGoogle Scholar
[21]Hirsch, R. and Hodkinson, I., Representability is not decidable for finite relation algebras, Transactions of the American Mathematical Society, vol. 353 (2001), pp. 1403–1425.CrossRefGoogle Scholar
[22]Hirsch, R. and Hodkinson, I., Relation algebras by games, Studies in Logic and the Foundations of Mathematics, vol. 147, North-Holland, Amsterdam, 2002.Google Scholar
[23]Hirsch, R. and Mikulás, Sz., Representable semilattice-ordered monoids, Algebra Universalis, vol. 57 (2007), pp. 333–370.CrossRefGoogle Scholar
[24]Hodkinson, I. and Mikulas, S., A non-finite axiomatizability result for a reduct of rra, Algebra Universalis, vol. 43 (2000), pp. 127–156.CrossRefGoogle Scholar
[25]Hodkinson, I. and Venema, Y., Canonical varieties with no canonical axiomatisation, Transactions of the American Mathematical Society, vol. 357 (2005), pp. 4579–4605.CrossRefGoogle Scholar
[26]Howie, J. M., Fundamentals of semigroup theory, 2nd ed., Oxford University Press, New York, 1995.CrossRefGoogle Scholar
[27]Jackson, M., Some undecidable embedding problems for finite semigroups, Proceedings of the Edinburgh Mathematical Society. Series II, vol. 42 (1998), pp. 113–125.CrossRefGoogle Scholar
[28]Jackson, M. and Stokes, T., An invitation to C-semigroups, Semigroup Forum, vol. 62 (2001), pp. 279–310.CrossRefGoogle Scholar
[29]Jackson, M. and Stokes, T., The algebra of partial maps with domain and range: extending Schein's representation, Communications in Algebra, vol. 37 (2009), pp. 2845–2870.CrossRefGoogle Scholar
[30]Jackson, M. and Stokes, T., Modal restriction semigroups: towards an algebra of functions, International Journal of Algebra and Compututation, vol. 21 (2011), pp. 1053–1095.CrossRefGoogle Scholar
[31]Jackson, M. and Volkov, M. V., Relatively inherently nonfinitely q-based semigroups, Transactions of the American Mathematical Society, vol. 361 (2009), pp. 2181–2206.CrossRefGoogle Scholar
[32]Jackson, M. and Volkov, M. V., Undecidable problems for completely 0-simple semigroups, Journal of Pure and Applied Algebra, vol. 213 (2009), pp. 1961–1978.CrossRefGoogle Scholar
[33]Jónsson, B., Representation of modular lattices and relation algebras, Transactions of the American Mathematical Society, vol. 92 (1959), pp. 449–464.CrossRefGoogle Scholar
[34]Jónsson, B., The theory of binary relations, Colloquia mathematica Societatis Jónos Bolyai (Andréka, H., Monk, J., and Németi, I., editors), Algebraic logic, vol. 54, North-Holland, Amsterdam, 1991, pp. 245–292.Google Scholar
[35]Jónsson, B. and Tarski, A., Boolean algebras with operators. Part II, American Journal of Mathematics, vol. 74 (1952), pp. 127–162.CrossRefGoogle Scholar
[36]Kharlampovich, O. and Sapir, M., Algorithmic problems in varieties, International Journal of Algebra and Compututation, vol. 5 (1995), pp. 379–602.CrossRefGoogle Scholar
[37]Kurucz, A., Decision problems in algebraic logic, Ph.D. thesis, Hungarian Academy of Sciences, Budapest, 1997, available at http://www.math-inst.hu/algebraic-logic/kuagthes.dvi.Google Scholar
[38]Lyndon, R., The representation of relational algebras, Annals of Mathematics, vol. 51 (1950), pp. 707–729.CrossRefGoogle Scholar
[39]Lyndon, R., The representation of relation algebras II, Annals of Mathematics, vol. 63 (1956), pp. 294–307.CrossRefGoogle Scholar
[40]Madarász, R. Sz. and Crvenković, S., Relacione algebre, Matematički Institut, Belgrade, 1992, Serbo-Croatian.Google Scholar
[41]Maddux, R. D., Relation algebras, Studies in Logic and the Foundations of Mathematics, vol. 150, North-Holland, Amsterdam, 2006.Google Scholar
[42]Mikulás, Sz., Axiomatizability of algebras of binary relations. Classical and new paradigms of computation and their complexity hierarchies, Trends in Logic—Studia Lógica Library, 23, Kluwer Academic Publishers, Dordrecht, 2004.Google Scholar
[43]Möller, B. and Struth, G., Algebras of modal operators and partial correctness, Theoretical Computer Science, vol. 351 (2006), pp. 221–239.CrossRefGoogle Scholar
[44]Monk, D., On representable relation algebras, Michigan Mathematical Journal, vol. 11 (1964), pp. 207–210.CrossRefGoogle Scholar
[45]Németi, I., Decidability of relation algebras with weakened associativity, Proceedings of the American Mathematical Society, vol. 100 (1987), no. 2, pp. 340–344.CrossRefGoogle Scholar
[46]Pratt, V., Dynamic algebras as a well-behaved fragment of relation algebras, Algebraic logic and universal algebra in computer science (Bergman, C. H., Maddux, R. D., and Pigozzi, D. L., editors), Lecture Notes in Computer Science, 425, Springer-Verlag, 1990, pp. 77–110.CrossRefGoogle Scholar
[47]Robinson, R. M., Undecidability and nonperiodicity for tilings of the plane, Inventiones Mathematical vol. 12 (1971), pp. 177–209.CrossRefGoogle Scholar
[48]Schein, B. M., The representation of ordered semigroups, Rossisskaya Akademiya Nauk. Matematicheskiĭ Sbornik (New Series), vol. 65 (1964), no. 107, pp. 188–197, in Russian.Google Scholar
[49]Schein, B. M., On certain classes of semigroups of binary relations, Rossisškaya Akademiya Nauk. Sibirskoe Otdelenie, vol. 6 (1965), pp. 616–635, Russian; English translation in American Mathematical Society Translations. Series 2, vol. 139 (1988), pp. 117–137.Google Scholar
[50]Schein, B. M., Lectures on transformation semigroups, Idzat. Saratov Univ., Saratov, (1970), Russian; English translation in Translations of the American Mathematical Society. Series 2. vol. 113 (1979) no. 2, pp. 123–181.Google Scholar
[51]Schein, B. M., Relation algebras and function semigroups, Semigroup Forum, vol. 1 (1970), pp. 1–62.CrossRefGoogle Scholar
[52]Schein, B. M., Restrictively multiplicative algebras of transformations, Izvestiya Vysšhikh. Učhebnykh. Zavedeniĭ. Matematika, vol. 95 (1970), no. 4, pp. 91–102, in Russian.Google Scholar
[53]Schein, B. M., Representation of reducts of Tarski relation algebras, Colloquia mathematica Societatis János Bolyai, vol. 54, 1991, pp. 379–394.Google Scholar
[54]Schein, B. M., Difference semigroups, Communications in Algebra, vol. 20 (1992), pp. 2153–2169.CrossRefGoogle Scholar
[55]Schein, B. M., Subsemigroups of inverse semigroups, Le Matematiche, vol. 51 (1996), pp. 205–227.Google Scholar
[56]Slobodskoi, A., Undecidability of the universal theory of finite groups, Algebra i Logika, vol. 20 (1981), pp. 207–230, 251, Russian; English translation in Algebra and Logic vol. 20 (1981), pp. 139–156 (1982).Google Scholar
[57]Stokes, T., Eq-monoids, Acta Universitatis Szegediensis. Acta Scientiarum Mathematicarum, vol. 72 (2006), pp. 481–506.Google Scholar
[58]Stone, M., The theory of representations for Boolean algebras, Transactions of the American Mathematical Society, vol. 40 (1936), pp. 37–111.Google Scholar
[59]Tarski, A., On the calculus of relations, this Journal, vol. 6 (1941), pp. 73–89.Google Scholar
[60]Tarski, A. and Givant, S., A formalization of set theory without variables, Colloquium Publications, vol. 41, American Mathematical Society, Providence, Rhode Island, 1987.Google Scholar
[61]Venema, Y., Atom structures andSahlqvist equations, Algebra Universalis, vol. 38 (1997), pp. 185–199.CrossRefGoogle Scholar
[62]Zareckiĭ, K. A., The representation of ordered semigroups by binary relations, Izvestiya Vysšhikh. Učhebnykh. Zavedeniĭ. Matematika, vol. 6 (1959), no. 13, pp. 48–50.Google Scholar