Jónsson, Bjarni The theory of binary relations. (English) Zbl 0760.03018 Algebraic logic, Pap. Colloq., Budap./Hung. 1988, Colloq. Math. Soc. János Bolyai 54, 245-292 (1991). [For the entire collection see Zbl 0741.00041.]This survey is an updated version of a series of lecture notes written at the University of Montreal in 1984. The paper comprises four sections.The first section presents several clones of operations on the set \(\text{Re}(U)\) of all binary relations on a set \(U\): the Boolean clone \(C_ b(U)\), generated by the Boolean operations \(\cap,\cup,^ -\), the classical clone \(C_ c(U)\), generated by \(\cap,\cup,^ -,|\) (composition), \(\smallsmile\) (conversion) and \(E\) (identity relation), the invariant clone \(C_ i(U)\) of all operations that are invariant under every permutation of \(U\), and the logical clone \(C_ \ell(U)\) of the operations whose associated classes of relational structures are strictly elementary. The logical clone is finitely generated if and only if \(U\) is finite.The second section is devoted to Boolean algebras with operators (i.e., operations that are finitely join-preserving in each of their arguments). The author focuses on perfect extensions, poly-algebras (i.e., sets \(U\) equipped with poly-operations, i.e., mappings from \(U\) to the power set of \(U)\), and duality for Boolean algebras with operators.The next section deals with relation algebras. The starting point is a review of the elementary arithmetic properties of relation algebras. The next topic is the problem of converting a Boolean algebra into a relation algebra, which the author solves in terms of poly-groups. The basic structural properties of relation algebras are then listed, including several characterizations of simple relation algebras. The next topic is representation: a relation algebra is said to be representable if it is isomorphic to a subalgebra of the full algebra of binary relations on \(U\). The author gives a universal-algebraic proof of the Tarski theorem which states that the class RRA of representable relation algebras is equational, presents Lyndon’s example of a non-representable relation algebra and proves that every equational basis for the class RRA contains equations with infinitely many variables, which is a stronger version of a theorem due to Monk.The last section is concerned with modal logics and modal algebras. An algebraic characterization of propositional modal logic is presented, while modal algebras (i.e., Boolean algebras equipped with a normal unary operator) turn out to be the associated algebraic structures. The concept of a Kleene algebra originates in the study of non-deterministic computer programs; the algebra of regular events is a Kleene algebra. Dynamic logic is obtained from classical propositional logic by adjoining modal operators associated with the elements of a Kleene algebra. The associated algebras are termed dynamic algebras and the author presents a few theorems on the representation of dynamic algebras.The results are given with full proofs, sketchy proofs or no proofs at all; some of the proofs are new. A few research problems are stated; see also the companion paper by I. Németi and H. Andréka [same Proceedings, 431-442 (1991; Zbl 0756.08002)]. Reviewer: S.Rudeanu (Bucureşti) Cited in 4 ReviewsCited in 26 Documents MSC: 03Gxx Algebraic logic 03G15 Cylindric and polyadic algebras; relation algebras 08A02 Relational systems, laws of composition 03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations 68Q55 Semantics in the theory of computing 03G05 Logical aspects of Boolean algebras 03G25 Other algebras related to logic 03B45 Modal logic (including the logic of norms) 03B70 Logic in computer science 08A40 Operations and polynomials in algebraic structures, primal algebras 03E20 Other classical set theory (including functions, relations, and set algebra) 03G10 Logical aspects of lattices and related structures 06B20 Varieties of lattices Keywords:dynamic logic; survey; clones of operations; binary relations; Boolean algebras with operators; relation algebras; modal logics; modal algebras; Kleene algebra; non-deterministic computer programs; dynamic algebras Citations:Zbl 0741.00041; Zbl 0756.08002 PDFBibTeX XMLCite \textit{B. Jónsson}, Colloq. Math. Soc. János Bolyai 54, 245--292 (1991; Zbl 0760.03018)