×

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

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
PDFBibTeX XMLCite