Abstract
We solve a problem of Jónsson [12] by showing that the class ℛ of (isomorphs of) algebras of binary relations, under the operations of relative product, conversion, and intersection, and with the identity element as a distinguished constant, is not axiomatizable by a set of equations. We also show that the set of equations valid in ℛ is decidable, and in fact the set of equations true in the class of all positive algebras of relations is decidable.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ackermann, W.,Solvable cases of the decision problem, Studies in logic and the foundations of mathematics, North-Holland Publishing Co., Amsterdam, 1954, viii+114 pp.
Andréka, H.,On union-relation composition reducts of relation algebras, Abstracts of Amer. Math. Soc.10,2 (1989), 174.
Andréka, H.,Representation of distributive-lattice-ordered semigroups with binary relations, Algebra Universalis28 (1991), 12–25.
Andréka, H. andNémeti, I.,Positive reducts of representable relation algebras do not form a variety, Preprint (1990).
Börner, F. andPöschel, R.,Clones of operations on binary relations, Contributions to general algebra7 (1991), 51–70.
Bredikhin, D. A.,On relation algebras with general superpositions, in: Algebraic Logic, Coll. Math. Soc. J. Bolyai Vol. 54, North-Holland, 1991, pp. 111–124.
Bredikhin, D. A.,The variety generated by ordered involuted semigroups of binary relations, Proc. Suslin Conf., Saratov, 1991, p. 27.
Bredikhin, D. A.,The equational theory of relation algebras with positive operations (In Russian.) Izv. Vyash, Uchebn. Zaved., Math., No 3, 1993, pp. 23–30.
Bredikhin, D. A. andSchein, B. M.,Representations of ordered semigroups and lattices by binary relations, Colloq. Math.39 (1978), 1–12.
Comer, S. D.,A remark on representable positive cylindric algebras, Algebra Universalis28 (1991), 150–151.
Haiman, M.,Arguesian lattices which are not linear, Bull. Amer. Math. Soc.16 (1987), 121–123.
Jónsson, B.,Representation of modular lattices and relation algebras, Trans. Amer. Math. Soc.92 (1959), 449–464.
Kozen, D.,On induction vs *-continuity, in:Logics of Programs, Lecture Notes in Computer Science 131, Springer Verlag, Berlin, 1982, pp. 167–176.
Németi, I.,Algebraizations of quantifier logics, An introductory overview, Version 10.2, Preprint, Mathematical Institute of the Hungarian Academy of Sciences, Budapest, 1992, Abstracted in: Studia Logica, vol L, No 3/4, 1991.
Schein, B. M.,Relation algebras and function semigroups, Semigroup Forum1 (1970), 1–62.
Schein, B. M.,Representation of involuted semigroups by binary relations, Fund. Math.82 (1974), 121–141.
Tarski, A. andGivant, S.,A formalization of set theory without variables, Colloquium Publications 41, American Mathematical Society, Providence, R.I., 1987, xxii +318 pp.
Author information
Authors and Affiliations
Additional information
H. Andréka's research was supported by Hungarian National Research Fund No. 1911 and No. 2258.
Rights and permissions
About this article
Cite this article
Andréka, H., Bredikhin, D.A. The equational theory of union-free algebras of relations. Algebra Universalis 33, 516–532 (1995). https://doi.org/10.1007/BF01225472
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01225472