Relation algebras (Q868510)

The book is an introduction to the calculus of relations and the theory of relation algebras (r.a.s): the reader need not have any preliminary knowledge of the subject. However, it is not quite a textbook, for many theorems are stated without proofs and many proofs are incomplete. Often, instead of a proof of a theorem that can be found in the literature, only a reference to the relevant paper is provided. On the other hand, the book contains very extensive material (the bibliography, in particular) both on relation algebras and from related areas and may serve as a handbook for a reseacher. Still, applications (in computer science, for instance) are not presented in any form. Review by chapters: Chapter 1,``Calculus of relations'', introduces the reader to r.a.s through the calculus of relations of De Morgan and Pierce. Tarski's axiomatization of the calculus is presented; the chapter also includes the representation problem for relational algebras, the incompleteness of Tarski's axioms, and reasons for studying r.a.s with weakened associative laws for composition of relations. The author's paper ``The origin of relation algebras in the development and axiomatization of the calculus of relations'' [Stud. Log. 50, No.~3--4, 421--455 (1991; Zbl 0754.03042)] is an early version of this chapter. Chapter 2, ``Set theory'', presents Tarski's simplified version of Bernays-Gödel set theory and demonstrates how relational calculus can be developed on the basis of this system. The chapter ends with the construction, carried out within the calculus of relations, of the Dedekind-MacNeille completion of a partial ordering. Chapter 3, ``General algebra'', contains, along with some background on general algebra, proofs of several basic properties of the class of representable r.a.s. In particular, a proof of Tarski's theorem that this class is equational is presented. Chapter 4, ``Logic with equality'', presents basic facts about first-order logic, including the completeness theorem and the Löwenheim-Skolem Theorem. Like the formalism of [\textit{A.~Tarski} and \textit{S.~Givant}, A formalization of set theory without variables. Providence, RI: American Mathematical Society (1987; Zbl 0654.03036)], the logical languages of this chapter are actually extended and have some second-order features such as predicate operators and predicate equality. On the other hand, emphasis is on logics restricted to finitely many variables. Chapter 5, ``Boolean algebras'', starts with elementary matters, but treats also several advanced topics and constructions, such as the regular-open Boolean algebra of a topological closure operator, the complex algebra of a r.a., and the perfect extension of a Boolean algebra. Chapter 6, ``Relation algebras'', is the most voluminous in the monograph. Elementary arithmetic in r.a.s is developed in detail, the results being grouped according to the axioms needed to derive them. Some known classes of r.a.s are given an equational characterization. The chapter contains also various special results on the equational theories of some particular classes of r.a.s, several important examples of r.a.s, surveys of small finite r.a.s and finite integral r.a.s with the largest possible groups of automorphisms etc. In Chapter 7, ``Algebraic logic'', the formal systems of Chapter 4 are discussed again. Free relational algebras, semi-associative relational algebras, and representable relation algebras are constructed as algebras of formulas. For a binary relational language, the so-called algebraic semantics is developed and some results of Tarski on the Tarski-Givant formalization of set theory [loc.~cit.] are presented. Chapter 8, ``4329 finite integral relation algebras'', contains various numerical data on the mentioned algebras with 5 atoms.