zbMATH — the first resource for mathematics

Simple relation algebras. (English) Zbl 1437.03001
Cham: Springer (ISBN 978-3-319-67695-1/hbk; 978-3-319-67696-8/ebook). xxiv 622 p. (2017).
This book is a research monograph dealing with constructions that arose in connection with a half dozen papers about relation algebras: [B. Jónsson, Discrete Math. 70, No. 1, 27–45 (1988; Zbl 0649.03047); J.-P. Olivier and D. Serrato, C. R. Acad. Sci., Paris, Sér. A 290, 939–941 (1980; Zbl 0438.18003); S. R. Givant, The structure of relation algebras generated by relativizations. Providence, RI: American Mathematical Society (1994; Zbl 0812.03035); R. D. Maddux, Trans. Am. Math. Soc. 328, No. 1, 83–131 (1991; Zbl 0746.03055); S. Givant and H. Andréka, Bull. Symb. Log. 8, No. 1, 38–64 (2002; Zbl 1002.03055); M. El Bachraoui, Proceedings of the Argentinian Workshop on Theoretical Computer Science (WAIT’2001) (Buenos Aires), 27–45 (2001)]
Part I (Chapters 1 and 2) and Part II (Chapters 3–6) were written by Givant. Part III (Chapters 7–9) was written “with the collaboration” of Andréka, and both authors wrote Part IV (Chapters 10–11). There are three appendices. Appendix A summarizes just those parts of the theory of relation algebras used in this book, while Appendix B does the same for projective geometries. Each chapter and Appendix B has a set of exercises, ranging in number from 14 from 69, for a total of 383 exercises. Many of these ask the reader to complete parts of proofs, or to formulate and prove extensions of various results. Some are drawn from other sources, or carry the reader Through standard relation-algebraic facts. Appendix C contains hints or partial solutions for 114 exercises.
The origins, content, methods, results, and goals of this book are best described by some extensive quotations. On pages xiii–xiv of the Introduction, “The historical roots of semiproducts go back to the paper of Jónsson. The paper was motivated by an earlier work of Olivier and Serrato, in which the notion of a Schröder category was introduced in order to give certain results about relation algebras a category-theoretic and seemingly more general formulation. Jónsson showed that the apparent greater generality is illusory: every Schröder category can be used to build a simple relation algebra whose elements are systems of morphisms from the category …\ Jónsson called his construction a semiproduct. He used it to analyze relation algebras generated by a single equivalence element, and in particular to prove that any such algebra is finite and representable. Motivated by Jónsson’s paper, Givant … show[ed] that every relation algebra \(\mathfrak A\) may actually be written as a relativization of some simple relation algebra, called a simple closure of \(\mathfrak A\). … A separate line of development was motivated by the paper of Maddux, in which a representation theorem was established for all pair-dense relation algebras, … Maddux’s theorem led Givant in 1988 to a generalization of McKinsey’s group complex algebra construction: … a system of groups, together with … isomorphisms between quotients of the groups. The … paper of El Bachraoui … led Givant to a common generalization of the representation theorems of Jónsson-Tarski, Maddux, and El Bachraoui. The … generalization … involves the notion of a semipower of a relation algebra (treated in Part II of this work). Eventually, it was realized that all four constructions – the construction of Jónsson, the simple closure construction, the construction of relation algebras from systems of groups and quotient isomorphisms, and the semipower construction – are special cases of a much broader phenomenon, and this gave rise to the general notion of a semiproduct.”
“The notions and theorems of Chapters 1, 4, and 6 were developed by Givant in January and February of 2002. He then prepared a first draft of the material now contained in Parts I and II. In mid-March, Hajnal Andréka read the draft and became interested in the work. She posed several problems, and there ensued a stimulating exchange of ideas between the two authors. The contributions of each of the authors are described in the various chapter introductions and also in the text itself. The notions and theorems of Chapters 7 and 8 are a result of this exchange, and date to March and April of 2002. Some of the theorems of Chapter 9 also date to this period. The remainder were found in July and August of 2002. The results of Chapter 11 are also a result of the exchange, and were obtained in May of 2002. The results of Chapter 10 date to November and December of that year.”
Chapter 1 provides a framework for a method of breaking the structure of a simple relation algebra into smaller pieces using a partition of the identity element. It describes how the overall structure of the algebra can be recovered from the pieces. Chapter 2 does the same for a method that uses an equivalence element and its complement. Chapter 1 is preparation for diagonal semiproducts, semipowers, and simple closures, treated in Chapters 3–5, respectively. Chapters 2 and 7 are preparation for quotient semiproducts and insertion semiproducts, treated in Chapters 8 and 10, respectively. In Chapter 6, the constructions of Chapters 3–5 are applied to obtain representation theorems for quasi-bijective relation algebras, plus descriptions of several closely related classes of representable atomic relation algebras. The quotient semiproducts of Chapter 8 are illustrated in Chapter 9 by examples constructed from groups and projective geometries. The insertion semiproducts of Chapter 10 are illustrated by examples in Chapter 11.
This book is seen as a contribution to a proposed research program described on pages x–xi in the Introduction. “One of the fundamental problems of any algebraic theory is the analysis of its models, and in particular the analysis of the basic algebras that form the building blocks for the models of the theory. In group theory, for instance, manifestations of this analysis include the classification of finite simple groups and the classification of finite Abelian groups. In Boolean algebra, one might mention the theorem that every Boolean algebra is a subdirect product of the two-element Boolean algebra (which is the only simple Boolean algebra), and every finite Boolean algebra is a direct product of the two-element Boolean algebra. The basic building blocks of relation algebras are simple relation algebras, particularly atomic ones.”
“In analogy with group theory, the program naturally suggests itself of classifying all simple relation algebras, or at least all finite, simple relation algebras. This program might be interpreted in several different ways, but the goal is to come up with a well-defined class of ‘basic’ simple relation algebras, and a finite list of construction techniques such that every finite, simple relation algebra is obtainable from the basic examples by applying one or more of the construction techniques, perhaps in some specific order. As a concrete example of an interpretation of this program, consider the class of finite, integral relation algebras, that is to say, relation algebras of finite cardinality greater than one, such that the relative product of two elements is zero if and only if one of the elements is zero. All such algebras are known to be simple. One may ask if there is a list of finitely many construction techniques so that every finite, simple relation algebra can be constructed from the class of finite integral relation algebras using one or more of these techniques. In other words, the program may be viewed as reducing the problem of constructing and analyzing all finite, simple relation algebras to that of constructing and analyzing all finite, integral relation algebras.”
“This book can be viewed as a contribution to this program. It presents a fairly general method for developing tools to construct and analyze simple relation algebras, it gives some examples of how this general method can lead to constructions that are interesting, beautiful, and useful, and how these constructions can, in turn, be used to prove significant theorems. In each of these theorems, the method is indeed used to reduce the result for simple relation algebras to the corresponding result for integral relation algebras.”
The analogy with groups, comparing simple groups with simple or integral relation algebras, runs into difficulties. Non-trivial diagonal semiproducts, semipowers, simple closures, and quotient semiproducts are relation algebras that are not integral, because the identity element in an integral relation algebra is an atom, hence there are no non-trivial partitions of the identity element (the topic of Chapter 1). Insertion semiproducts can be integral and they can have non-trivial equivalence elements (the topic of Chapter 2). In fact, any integral relation algebra with a non-trivial equivalence element is a non-trivial insertion semiproduct of itself with the relativization of itself to the equivalence element.
Integral relation algebras vastly outnumber the non-integral ones. The number of isomorphism types of finite integral relation algebras with \(n\) atoms, of which \(s\) are symmetric, is asymptotic to \(2^{Q(n,s)}/P(n,s)\), where \(Q(n,s)=\frac{n-1}6((n-1)^2+3s-1)\) and \(P(n,s)=2^{\frac{n-s}2}(s-1)!\Big(\frac{n-s}2\Big)!\). This formula produces numbers far too large when \(n\) and \(s\) are small, but it shows that the number of finite relation algebras with \(n\) atoms grows like \(2^{n^3}\), and that almost all finite relation algebras are not only integral but also symmetric, as can be seen by comparing the values obtained when \(s=n\) to those when \(s<n\). Finite integral relation algebras behave more like graphs than groups, and, in fact, increase at a rate like ternary relations. (The exponent is cubic for relation algebras, but only quadratic for graphs.) For example, the number of finite integral relation algebras with at most 6 atoms is 4,890,876, while the number of finite non-integral relation algebras with at most 6 atoms is 16: just one with 4 atoms, 2 with 5 atoms, and 13 with 6 atoms. These 16 finite non-integral relation algebras do arise as diagonal semiproducts of smaller algebras, but the 4,890,876 integral relation algebras with at most 6 atoms require other analytical methods. Those with non-trivial equivalence elements can be analyzed as insertion semiproducts, and about one-fourth of the 4527 integral relation algebras with at most 5 atoms have non-trivial equivalence elements. Among the 47965 finite integral relation algebras with 2 symmetric atoms and 4 non-symmetric atoms, less than five percent have non-trivial equivalence elements. As \(n\) increases, essentially all finite relation algebras with \(n\) atoms will be integral, symmetric, without non-trivial equivalence elements, and beyond the realm of this book.
On pages xvi–xvii, “Chapter 6 establishes a common generalization of several representation theorems from the literature. Call a relation algebra quasi-bijective if it is atomic, and if below each rectangle with atomic sides there is at most one non-bijective atom – at most one atom that does not satisfy a certain characteristic equational property of set-theoretic bijections. Examples of quasi-bijective relation algebras include atomic relation algebras with functional atoms, shown to be representable (by Jónsson and Tarski), atomic pair-dense relation algebras (including all simple, pair-dense relation algebras), shown to be representable (by Maddux), strictly elementary relation algebras, shown to be representable (by El Bachraoui), and elementary relation algebras, independently shown to be representable by Givant and El Bachraoui, …. Chapter 6 gives a structural description of all quasi-bijective relation algebras. The formulation and proof of this structure theorem draws on the results from Chapters 3–5.”
“One consequence of this theorem is that every quasi-bijective relation algebra is completely representable. This gives the common generalization of the representation theorems cited above. Another consequence is a structural description of the classes of relation algebras to which the cited representation theorems apply. For example, atomic relation algebras with functional atoms are essentially just direct products of semipowers of complex algebras of groups. Atomic pair-dense relation algebras are essentially just direct products of diagonal semiproducts of semipowers of the complex algebras of one-element and two-element groups. Strictly elementary relation algebras are essentially just direct products of diagonal semiproducts of semipowers of minimal simple set relation algebras on one-element and threeelement sets. Elementary relation algebras are essentially just direct products of diagonal semiproducts of semipowers of minimal simple set relation algebras on one-element, two-element, and three-element sets.”
Jónsson and Tarski not only proved atomic relation algebras with functional atoms are representable, but also that a relation algebra is representable if its unit element is the join of finitely many functional elements. The obvious question (not explicitly mentioned by Jónsson and Tarski in their paper) is whether a relation algebra is representable if its unit element is the join of functional elements. The positive answer, generalizing both results, was obtained and announced in 1976 by Maddux and Tarski. (The original proof was rediscovered 35 years later and published by the authors of this book.) This result was soon superceded by Maddux’s 1978 result that a relation algebra is representable if its unit is the join of elements of the form \(\breve x{;}y\), where \(x\) and \(y\) are functional elements. Besides generalizing the previous results, this theorem has Tarski’s QRA theorem as a very special case, that a relation algebra is representable if \(1=\breve x{;}y\), where \(x\) and \(y\) are functional elements. Tarski’s QRA Theorem is the basis for his formalization of set theory without variables. The “common generalization” in Chapter 6 only generalizes the representability of relation algebras with functional atoms. None of the later results are even mentioned in this book.
On page 68, in the Introduction to Part II (Chapters 3–6), “The main result of Maddux is a representation theorem for pair-dense relation algebras: relation algebras in which the identity is can be written as a sum of non-zero elements, each of which satisfies an equation that is characteristic of subidentity relations with at most two pairs. It is proved in Chapter 6 that a relation algebra is atomic and pair-dense if and only if it is essentially isomorphic to a direct product of simple bijection semiproducts in which each base algebra is the complex algebra of a group of order one or two.” Maddux’s abstract begins with the claim that “pair-dense relation algebras are completely representable”. This is correct only if “completely” is deleted (the same correction should be made to the statement of Theorem 54 and only the last line of its proof should be deleted). The same mistake was made by R. C. Lyndon in his 1950 paper [Ann. Math. (2) 51, 707–729 (1950; Zbl 0037.29302)]. The observation missed in both cases is due to [A. Abian, J. Lond. Math. Soc., II. Ser. 3, 618–620 (1971; Zbl 0218.06005)], that a Boolean algebra has a join-preserving isomorphism into an algebra of sets if and only if it is atomic. Pair-dense relation algebras need not be atomic, as is pointed out on page 203 and in Exercise 6.10. However, Theorems 6.20, 6.21, 6.22, and 6.23 are restricted to those pair-dense relation algebras that are atomic. Theorem 6.20 says that every simple pair-dense relation algebra is completely representable, while Theorem 51 in Maddux’s paper goes further to say that every simple pair-dense relation algebra \(\mathfrak A\) has a complete representation over a set \(U\) if and only if the cardinality of \(U\) is equal to the cardinality of the set of points of \(\mathfrak A\) plus twice the cardinality of the set of pairs of \(\mathfrak A\) that do not contain any points. Theorems 6.22 and 6.23 go on to describe \(\mathfrak A\) as a diagonal semiproduct of semipowers of complex algebras of the groups \(\mathbb{Z}_1\) and \(\mathbb{Z}_2\), but there is no cardinality information.
Every quasi-bijective relation algebra is atomic, but a relation algebra is pair-dense if the identity element is the sum of points and pairs, which need not be atoms. On page 203, “One consequence … is that a simple pair-dense relation algebra is quasi-bijective,” and “Since the factor algebras are simple and pair-dense, they are quasi-bijective.” To make sense of these remarks, one needs to know that if a pair-dense relation algebra is simple then it is also atomic, as is required in order to be quasi-bijective. The fact that simple pair-dense relation algebras are atomic is not mentioned anywhere in the book, but it can be proved rather easily from Lemma 6.18. The proof of Lemma 6.18 is left to the reader as Exercise 6.8, but extensive hints are given on pages 585–6.
No such problems arise in the description of strictly elementary and elementary relation algebras, both shown to be representable by El Bachraoui, since they are required by definition to be atomic.
Chapter 7 investigates quotient relation algebras and equijections. The universe of a quotient relation algebra \(\mathfrak A/e\) is the set of elements of \(\mathfrak A\) that are below \(e{;}1{;}e\) and have the form \(e{;}x{;}e\), where \(e\) is an equivalence element. This set is closed under the operations of the algebra, so they are simply restricted to this set, but the identity element is taken to be \(e\). On page 213 (also 259), “The construction was apparently introduced by McKenzie in his doctoral dissertation …, and it seems not to have been studied further by other authors.” It was not given a name by McKenize, but Jónsson called it \(e{;}\mathfrak A{;}e\), Comer called it \(\mathfrak A{/\!/}e\), and Maddux called it \(\mathfrak{Fa}_e\mathfrak A\). On page 220, “The quotient construction can be motivated (and perhaps was motivated) by an interesting, but little-known theorem from” the Jónsson-Tarski paper, namely Theorem 4.27. A more general and detailed version of Theorem 4.27 is stated and proved as Theorem 102, pp. 143–148, in [R. D. Maddux, Relation algebras. Amsterdam: Elsevier (2006; Zbl 1197.03051)]. In Section 81, pp. 502–506, there is also a brief survey of McKenzie’s results, including several basic ones that appear in this book, such as the preservation of representability, and more advanced ones that do not. Chapter 7 goes much further, presenting many additional details, and introduces a new concept, that of normal equivalence elements, ones that commute with every other element. There is an extensive abstract algebraic study of equijections (the name used in this book for difunctional elements), which act as isomorphisms between quotient relation algebras.
The semipower construction of Chapter 4 builds a simple relation algebra from a given relation algebra \(\mathfrak A\) together with copies of \(\mathfrak A\) produced by a system of bijections. This construction is generalized in Chapter 8 by using equijections instead of bijections, and quotients of \(\mathfrak A\) rather than copies. Quotient semiproducts are illustrated in Chapter 9 by two examples. The first uses complex algebras of groups, and the second uses complex algebras of projective geometries. It is shown that every quotient semiproduct constructed from complex algebras of groups is completely representable, but a quotient semiproduct constructed from complex algebras of geometries may fail to be representable, even if all of its base algebras are completely representable. Some non-representable examples are given, along with a characterization of representable complex algebras of geometries.
In Chapter 10, the insertion semiproduct of two relation algebras \(\mathfrak B\) and \(\mathfrak C\) is constructed whenever the relativization of \(\mathfrak B\) to some equivalence element \(e\) containing the identity element of \(\mathfrak B\) is isomorphic to the quotient of \(\mathfrak C\) by some normal equivalence element containing the identity element of \(\mathfrak C\). The insertion semiproduct is obtained by replacing the part of \(\mathfrak B\) below \(e\) with a copy of \(\mathfrak C\). When \(\mathfrak B\) and \(\mathfrak C\) are atomic, each atom \(a\) of \(\mathfrak B\) is replaced by the set of atoms of \(\mathfrak C\) that are below the image of \(a\) under the isomorphism. Representations of insertion semiproducts are characterized in terms of the representations of the base algebras. There is a very well illustrated example of the representation of a particular insertion semiproduct, and also examples of non-representable insertion semiproducts with representable base algebras. The chapter ends with generalizations and connections with other systems.
In Chapter 11, a relation algebra is defined to be \(n\)-quasi-bijective if it is atomic and each element of the form \(x{;}1{;} y\), where \(x\) and \(y\) are atoms, is above at most \(n\) non-bijective atoms. There is an example of a non-representable 2-quasi-bijective relation algebra that is simple but not integral. It is shown that every integral 2-quasi-bijective relation algebra is completely representable. Relation algebras that are atomic and have at most two non-bijective atoms are also shown to be completely representable. A complete classification of all such algebras is presented. This involves a list of all ten integral relation algebras with three atoms, plus five more with four atoms.
Two incidental remarks. The non-representable 2-quasi-bijective relation algebra in Section 11.1 is not even weakly representable in Jónsson’s sense, for it fails all three of his simplest axioms for weak representability. Its non-representability is shown in this book by cardinality considerations. The four-atom integral relation algebra labelled (l) in Table 11.6 is shown to be a subalgebra of the complex algebra of the group \(\mathbb{Q}\times\mathbb{Z}_2\), so is it representable on an infinite set. However, it is also a subalgebra of the complex algebra of the quaternion group, so it has a representation on a finite set with only eight elements.
The book is very well written, easy to read, and has no typographical errors. There are few grammatical or mathematical errors. For example, in Theorems 6.14, 6.15, 6.16, 6.21, 6.22, 6.23, 6.26, 6.27, and 6.28, the phrase “A necessary and sufficient for …” should be replaced by “A necessary and sufficient condition for …”. In Lemma A.2(ix), “\(=0\)” should be added to the condition in the middle. To be correct, the word “representation” should be replaced by “square representation” in Exercise 9.8. In the second example on page 498, one should take \(e\) to be the element \(\text{1'}+d\) in \(\mathfrak B\) (in accordance with the instructions on page 497, line 5) rather than the identity element \(\text{1'}\) of \(\mathfrak B\) (as suggested on page 498). There are over 50 diagrams and illustrations of algebras, most of them beautifully multi-colored. They are very helpful in understanding the constructions.

03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
03G15 Cylindric and polyadic algebras; relation algebras
08A05 Structure theory of algebraic structures
08A30 Subalgebras, congruence relations
Full Text: DOI