Relation algebras by games (Q700879)

There are twenty-one chapters in six parts. Parts of eight chapters are modified versions of nine previously published papers (six by Hirsch and Hodkinson, one by Hirsch, one by Hodkinson, and one by Andréka and Hodkinson). There are more than 400 exercises ranging from drill to open problems. Chapter 21 has a list of twenty-one open problems, recalled from the body of the text, that the authors believe would ``make a significant contribution to research in this field.'' The book is itself such a contribution, since it is built around the solutions to several open problems. The first third of the book is occupied by the five chapters of Part I. It contains a historical introduction, preliminaries from model theory, universal algebra, and Boolean algebras, two chapters on relation algebras (with basic definitions, elementary facts, and many examples), and brief surveys of relativized representations, cylindric algebras, and other approaches to algebraic logic. In Chapter 2, many basic definitions and facts from model theory are recalled, including the compactness theorem, the Löwenheim-Skolem-Tarski theorem, theorems on the existence of saturated models and ultraproducts, Los's theorem, and so on. The theory of Boolean algebras with operators is summarized through the existence, uniqueness, and preservation theorems for completions and perfect extensions. This summary includes a survey of results on the interaction of atom structures, complex algebras, Sahlqvist equations, and modal logic. In Chapters 3 and 4, representations of a relation algebra are viewed as models of an appropriate first-order theory constructed from the algebra. This allows the authors to prove Monk's theorem, that the class of representable relation algebras is closed under perfect extensions, by using the existence of saturated models of the associated first-order theories. Using this result, they then prove Tarski's theorem, that the class of representable relation algebras is closed under homomorphisms, by constructing a representation of a homomorphic image of a representable algebra from a representation of its perfect extension. Examples of relation algebras include proper relation algebras (algebras of binary relations), group relation algebras (whose elements are subsets of a group), Lyndon algebras (whose elements are sets of points in a projective geometry), and Monk algebras (which are designed to utilize some basic results of Ramsey theory). Chapter 5 reviews the definitions and basic facts, and gives a brief survey of results about nonassociative relation algebras, weakly associative relation algebras, semi-associative relation algebras, weakly representable relation algebras (wRRA), cylindric algebras, and the connections among these classes that arise through relativization and the formation of reducts. Chapter 6 is a short survey of other kinds of algebras of relations, including diagonal-free cylindric algebras, Halmos's polyadic algebras, and Pinter's substitution algebras. There is an informative discussion of the (as yet unresolved) finitization problem, and a list of representation results for relation algebras. The second third of the book is comprised of Part II (Chapters 7-11), on games, networks, and axiomatization, and Part III (Chapters 12 and 13), on approximations to representations. The general theme of Part II is that representability can be characterized by the existence of a winning strategy for a game played with networks. A network over some algebra is a (typically finite) graph whose edges are labeled with elements of the algebra. A network is essentially just a portion of a representation. Networks serve as positions in games. The object of a typical game on an algebra is, for the first player (male), to ferret out a difficulty that prevents the algebra from being representable (or having some other nice property), while the second player (female) attempts to build a representation (or some other appropriate structure) in response to challenges by the first player. These ideas are illustrated by a proof of Maddux's theorem that every weakly associative relation algebra has a relativized representation. An appropriate infinite game is defined and shown to be winnable by the second player, which implies that every countable weakly associative relation algebra has a relativized representation. This conclusion can then be extended to all weakly associative relation algebras by compactness or ultraproducts. There are many variations on the games. They can be played on networks in general, or on networks restricted in some way, such as having atoms as labels or bounded size (no more than \(p\) nodes, for some fixed bound \(p<\omega\)). Depending on the application, moves may consist of choosing an edge and two elements, choosing two nearly identical networks, dropping a node and its edges from a network, properly labeling a set of edges of a network, or choosing one of two alternative networks. A given game can last for countably many moves (an infinite game), or it can be terminated after a fixed finite number of rounds (an \(r\)-round game for some finite length \(r<\omega\)). A key lemma is that if the second player can win all the finite-length games, then she can win the infinite game. According to the central result of Chapter 7, if the second player can win a certain game on a relation algebra, then that algebra is representable. The proof relies on the fact that the representable relation algebras form an equational class. The ability of the second player to win all finite-length games can be expressed as a sequence of first-order sentences, one for each finite-length game. The collection of such sentences characterizes representability. Each sentence in such a collection has a quantifier prefix of the form \((\forall\exists)^r\), where \(r\) is the number of rounds in the corresponding game. The sentence says, roughly, that for every move by the first player, there is a response available to the second player such that every move by the first player, layer, etc. By restricting the second player to choosing only one of two alternative moves, the existential quantifier can be reduced to a disjunction and the resulting sentence is universal. For discriminator varieties (the typical case in this book), a universal sentence is equivalent to an equation in all simple algebras. These techniques are applied to obtain axiomatizations for various classes, including representable relation algebras and representable cylindric algebras in Chapter 8, and some pseudo-elementary classes and pseudo-universal classes in Chapter 9. Chapter 10 is a more formal presentation of some of this material, including precise definitions of games and strategies in terms of trees labeled with variables and formulas. Chapter 11 is primarily about atomic relation algebras and \textit{R. C. Lyndon}'s conditions from his paper ``The representation of relational algebras'' [Ann. Math. (2) 51, 707-729 (1950; Zbl 0037.29302)]. Assume \(\mathfrak{A}\) is an atomic relation algebra. Atomic networks are those networks whose labels are atoms of \(\mathfrak{A}\). A new ``atom-game'' is introduced, played on atomic networks. The main results are that the atomic relation algebra \(\mathfrak{A}\) satisfies the Lyndon conditions iff the second player wins all finite-length atom-games on \(\mathfrak{A}\) iff \(\mathfrak{A}\) is elementarily equivalent to a completely representable (hence also atomic) relation algebra. Furthermore, if \(\mathfrak{A}\) is completely representable then the second player wins the infinite atom-game on \(\mathfrak{A}\). The converse fails in general but holds if the number of atoms is countable. The exercises include examples of finite symmetric integral representable relation algebras with no finite representations, Monk's theorem that \(\text{RRA}\), the class of representable relation algebra, is not finitely based, and Jónsson's proof that there is no equational axiomatization of \(\text{RRA}\) that uses only finitely many variables. The latter two results are both proved via Lyndon's algebras, obtained from projective lines, which were published in 1961. Jónsson's proof was found in 1988, but the result was stated by Tarski in a videotaped lecture in 1974. Perhaps this proof was at one time in the 1960's known to both Tarski and Jónsson. For \(n\geq 3\), \(\text{RA}_n\) is the class of relation algebras of dimension \(n\), and \(\mathbf{S}\text{RaCA}_n\) is the class of subalgebras of relation-algebraic reducts of cylindric algebras of dimension \(n\). It has long been known that these classes are canonical varieties. \(\text{RA}_n\) is defined via the concept of relational basis. Every atomic algebra in \(\mathbf{S}\text{RaCA}_n\) has a relational basis. This implies that \(\mathbf{S}\text{RaCA}_n\subseteq\text{RA}_n\). In spite of the names, \(\text{RA}_3\) and \(\mathbf{S}\text{RaCA}_3\) are strictly larger classes than \(\text{RA}\), the class of all relation algebras. For \(n=4\) and \(n=\omega\) the situation is quite nice, and provides characterizations of \(\text{RA}\) and \(\text{RRA}\), since \(\text{RA}=\text{RA}_4=\mathbf{S}\text{RaCA}_4\) and \(\text{RRA}=\text{RA}_\omega=\mathbf{S}\text{RaCA}_\omega\). When \(4\leq n<\omega\), these classes form descending chains of varieties of relation algebras that converge to \(\text{RRA}\), that is, \(\text{RA}_{n+1}\subset\text{RA}_n\) and \(\mathbf{S}\text{RaCA}_{n+1}\subset\mathbf{S}\text{RaCA}_n\), where all inclusions are known to be strict, and \(\text{RRA}=\bigcap_{3\leq n<\omega}\text{RA}_n=\bigcap_{3\leq n<\omega}\mathbf{S}\text{RaCA}_n\). In Chapters 12 and 13 these definitions and results are reviewed and extended. A variation on the atom-game is introduced in which there is a fixed finite bound \(p\) on the number of nodes in the networks that appear in the game. The second player wins the infinite \(p\)-bounded atom-game if and only if the algebra has a \(p\)-dimensional relational basis. An extension of the concept of relational basis, called ``hyperbasis'', is used to characterize \(\mathbf{S}\text{RaCA}_n\) in a manner similar to the definition of \(\text{RA}_n\). The classes \(\text{RA}_n\) and \(\mathbf{S}\text{RaCA}_n\) are also characterized in terms of relativized representations that have certain nice properties. The last third of the book consists of Part IV (Chapters 14-17), which contains various constructions of algebras, and Part V (Chapters 18 and 19) on decidability and the finite base property. In Chapter 14 a relational structure \(\mathfrak{S}(G)\) is associated with every graph \(G\), with these crucial properties. If \(G\) has infinite chromatic number (and is itself necessarily infinite), then \(\mathfrak{Cm}\mathfrak{S}(G)\), the complex algebra of \(\mathfrak{S}(G)\), is a representable relation algebra. On the other hand, if \(G\) has a finite chromatic number, and \(G\) itself is either infinite or sufficiently large compared to its chromatic number, then \(\mathfrak{Cm}\mathfrak{S}(G)\notin\text{RRA}\). This allows for two significant theorems. If, for example, \(G\) is a countable chain (undirected edges, all nodes of degree 2), then \(\mathfrak{Cm}\mathfrak{S}(G)\notin\text{RRA}\), but it turns out that if \(\mathfrak{A}\) is the subalgebra of \(\mathfrak{Cm}\mathfrak{S}(G)\) generated by the atoms of \(\mathfrak{Cm}\mathfrak{S}(G)\), then \(\mathfrak{A}\) is representable. It follows that \(\text{RRA}\) is not closed under completions, for \(\mathfrak{Cm}\mathfrak{S}(G)\) is the completion of \(\mathfrak{A}\). This result settles a 30-year old problem of Monk that was first solved by Hodkinson using a different example. Then, using a result of Erdős that there are finite graphs with arbitrarily large girth and chromatic number, the authors construct a sequence of infinite graphs \(G_i\) with infinite chromatic number and increasing girth, say \(G_i\) has girth \(i\). The ultraproduct of the graphs \(G_i\) is 2-colorable because it has infinite girth, so the corresponding structure has a nonrepresentable complex algebra. But the complex algebras of the \(\mathfrak{S}(G_i)\) are in \(\text{RRA}\). Thus the class of structures whose complex algebras are in \(\text{RRA}\) does not form an elementary class. For \(i>15\), the algebra \(\mathfrak{Cm}\mathfrak{S}(G_i)\) satisfies only finitely many Lyndon conditions, so the second player will lose any sufficiently long finite-length atom-game played on \(\mathfrak{Cm}\mathfrak{S}(G_i)\). This algebra cannot be completely representable (for it would otherwise satisfy all the Lyndon conditions) but it is, nevertheless, representable. It is complete, atomic, and representable, but has no complete representations. The earliest example of such an algebra appears in Lyndon's 1950 paper. Additional examples, from the reviewer's 1978 dissertation, conclude Chapter 14. The main result of Chapter 15 is that \(\mathbf{S}\text{RaCA}_{n+1}\) is not finitely based relative to \(\mathbf{S}\text{RaCA}_n\) (and a similar statement for neat reducts of cylindric algebras). The proofs utilize variations on Monk algebras and techniques from Ramsey theory, and they produce other interesting results. For every finite \(n\geq 5\), the inclusion \(\mathbf{S}\text{RaCA}_n\subseteq\text{RA}_n\) is strict, and, in fact, \(\mathbf{S}\text{RaCA}_n\) is not finitely based relative to \(\text{RA}_n\), nor is it finitely based relative to \(\text{RA}_n\cap\mathbf{S}\text{RaCA}_{n-1}\). Furthermore, for every finite \(n\geq 5\), \(\text{RA}_n\) is not included in \(\mathbf{S}\text{RaCA}_5\). Chapters 16 and 17 are devoted to the construction and application of the rainbow algebra \(\mathfrak{A}_{A,B}\), which is built from two relational structures \(A\) and \(B\) for a language having only binary and unary relation symbols. The rainbow algebra \(\mathfrak{A}_{A,B}\) is always complete and atomic, and it is finite whenever \(A\) and \(B\) are finite. The number of atoms in \(\mathfrak{A}_{A,B}\) is approximately the sum of the squares of the cardinalities of \(A\) and \(B\). The idea is to translate Ehrenfeucht-Fraïssé games on relational structures to games on algebras. It is a result from model theory that the second player wins the standard \(p\)-pebble \(r\)-round Ehrenfeucht-Fraïssé ``forth'' game from \(A\) to \(B\) just in case every positive existential sentence with \(p\) variables and quantifier depth \(r\) true in \(A\) is also true in \(B\). The main result is that if the second player can win a (slightly modified) \(p\)-pebble finite-length Ehrenfeucht-Fraïssé game from \(A\) to \(B\), then the second player can win a \(p\)-bounded finite-length atom-game on \(\mathfrak{A}_{A,B}\). This construction is quite powerful. It provides alternative proofs of earlier theorems, a proof of Haiman's theorem that \(\text{wRRA}\) is not finitely based, and some significant new results. For example, the class of completely representable relation algebras is not elementary. Perhaps most important is that \(\text{RA}_{n+1}\) is not finitely based relative to \(\text{RA}_n\) whenever \(4\leq n<\omega\), and that \(\text{RA}_n\) and \(\mathbf{S}\text{RaCA}_n\) are not closed under completions whenever \(6\leq n\) (leaving open the case \(n=5\).) Chapter 18 is devoted to showing that if \(K\) is any class of algebras that contains \(\text{RRA}\) and is contained in either \(\mathbf{S}\text{RaCA}_5\) or \(\text{wRRA}\), then there is no algorithm for determining whether a finite algebra belongs to \(K\). In particular, the question ``is a finite \(\text{RA}\) in \(\text{RRA}\)?'' is undecidable. It follows immediately from these results that if \(K\) is a variety, then the equational theory of \(K\) is also undecidable. The method is to encode each instance of the (undecidable) tiling problem as a relation algebra. Given a set of edge-labeled tiles \(\tau\), there is an algebra \(\mathfrak{A}_\tau\) that is representable if and only if there is a tiling of the plane using copies of tiles from \(\tau\) so that adjacent tiles have matching labels on their common edge. Every weakly associative relation algebra has a relative representation, but if the algebra is finite then, in fact, such a representation can be constructed on a finite set. In Chapter 19, this and similar results for finite algebras in \(\text{RA}_n\) and subalgebras of relation-algebraic reducts of finite \(n\)-dimensional cylindric algebras, involving appropriate notions of relative representation, are derived fairly directly from recent deep results in model theory that are stated with references but without proof. Part VI, the Epilogue, has just two short chapters. One is a fifteen-page summary of the book, and the other is a list of twenty-one unsolved problems. There are 326 items in the bibliography and ten pages of symbol indexes, organized into ten tables according to subjects. This book is a significant advance in the theory of relation algebras. Many of its main results solve difficult and long-standing problems. Its methods, techniques, and constructions are powerful tools for exploring the intricate and varied world of relation algebras. Its many open problems indicate fruitful directions for further research.