The structure of relation algebras generated by relativizations.

*(English)*Zbl 0812.03035
Contemporary Mathematics. 156. Providence, RI: American Mathematical Society (AMS). xv, 134 p. (1994).

The prime example of a relation algebra is \({\mathfrak Re}(U)\), where \(U\) can be any set. This algebra consists of the Boolean algebra of all binary relations on \(U\) (i.e., subsets of \(U\times U\)), supplemented with the binary operation of relational composition, the unary operation that forms the converse of a relation, and the identity relation on \(U\) as a distinguished element. A representable relation algebra is, by definition, an algebra that is isomorphic to a subalgebra of a direct product of algebras of the form \({\mathfrak Re}(U)\). Alfred Tarski proved that the class of representable relation algebras is closed under the formation of homomorphic images, and is therefore equational. But J. Donald Monk showed that it has no finite equational axiomatization. The class of (not necessarily representable) relation algebras is defined by a specially chosen finite set of equations that hold in all the representable relation algebras. One equation that holds in every representable relation algebra is
\[
0\text{'}; 0\text{'} = 0\text{'}; 0\text{'}; 0\text{'}; 0\text{'}.\tag{1}
\]
Here \(0\text{'}\) is the diversity element, the complement of the identity element \(1\text{'}\). (The notational convention of adding superscript commas to the digits 0 and 1, which denote the smallest and largest relations on \(U\), is due to Ernst Schröder.) Equation (1) was first shown to hold in all relation algebras by Julia Robinson in 1945, when she was a graduate student participating in Tarski’s seminar on relation algebras at Berkeley. Robinson’s result is the crucial step in the proof that if a relation algebra is generated by its diversity element, then it is finite and representable. In fact, it has at most 32 elements.

An element \(e\) of a relation algebra is said to be an equivalence element if \(e;e = e\) and \(\breve e = e\). The reason for this definition is that the equivalence elements of \({\mathfrak Re}(U)\) are the equivalence relations over subsets of \(U\). Now the identity element \(1^{\text{'}}\) is an equivalence element, so the diversity element \(0\text{'}\) is the complement of an equivalence element. Louise Chin and Tarski modified the proof of Robinson’s theorem to show that if \(e\) is an equivalence element, then \(\overline{e};\overline{e} = \overline{e};\overline{e}; \overline{e}; \overline{e}\). Around 35 years later Bjarni Jónsson generalized the result on relation algebras generated by their diversity elements by showing that if a relation algebra is generated by a single equivalence element, then it is finite and representable. Jónsson asked whether this is still true if the single equivalence element is replaced by a finite chain (linearly ordered set) of equivalence elements. He asked whether a relation algebra that is generated by a finite chain of equivalence elements must be finite and representable. This monograph is the result of Givant’s positive answer to this question.

The seventh and last chapter gives some examples that show why Jónsson formulated the problem as he did. For example, it is natural to ask whether every relation algebra generated by two equivalence elements is finite. But it is easy to find examples of infinite representable relation algebras that are generated by two equivalence elements. Let \(e_ 1\) be the equivalence relation on \(\{0,1,2,3,\dots\}\) whose equivalence classes are \(\{0\}, \{1,2\}, \{3,4\},\dots\) and let \(e_ 2\) be the equivalence relation whose equivalence classes are \(\{0,1\}, \{2,3\}, \{4,5\},\dots.\) Then \(e_ 1\) and \(e_ 2\) generate a subalgebra of \({\mathfrak Re}(\{0, 1, 2, 3, \dots\})\) that contains all the singleton relations \(\{\langle n,n\rangle\}\) for \(n = 0,1,2,3,\dots\), and hence is infinite. These two equivalence relations do not commute, that is, \(e_ 1;e_ 2 \neq e_ 2;e_ 1\), so their relative product \(e_ 1;e_ 2\) is not an equivalence element. (Two equivalence relations commute if and only if their relative product is an equivalence relation.) A slightly more complicated example shows that two commuting equivalence relations can still generate an infinite relation algebra. For all nonnegative integers \(k\) and \(l\), let \(S(k,l)\) be the unit square in the standard \(xy\)-coordinate plane whose lower left-hand corner is the point \((k,l)\). Thus the squares \(S(k,l)\) form an infinite checkerboard in the first quadrant of the \(xy\)-plane. Into each square \(S(k,k)\) on the main diagonal put a pebble labeled with the number \(2k\). Into each square \(S(k+1,k)\) on the superdiagonal put a pebble labeled with the number \(2k + 1\). This yields a one-to-one correspondence between nonnegative integers and pebbles on the main diagonal and the superdiagonal. Into every other square put two or more unlabeled pebbles. Let \(U\) be the set of all the pebbles on the checkerboard. Say that two pebbles are “horizontally equivalent” if they occupy squares in the same horizontal row, and that two pebbles are “vertically equivalent” if their squares are in the same vertical column. It turns out that horizontal and vertical equivalence are commuting equivalence relations on the set of pebbles, but they generate an infinite subalgebra of \({\mathfrak Re}(U)\). To see this, denote horizontal and vertical equivalence by \(h\) and \(v\), respectively. Let \(a = (h \cdot v) - ((h \cdot v \cdot 0\text{'});1)\), \(e_ 1 = a;v;a\), and \(e_ 2 = a;h;a\). Then, modulo the correspondence between nonnegative integers and pebbles, we are in the previous example. Thus a representable relation algebra generated by two commuting equivalence elements may not be finite. Must a relation algebra generated by commuting equivalence elements be representable? Not necessarily, as is shown in Chapter 7 by a finite nonrepresentable relation algebra generated by three commuting equivalence elements. No such example with two commuting equivalence elements is known. Another example from Chapter 7 shows that if the associativity of relational composition (one of the equational axioms for relation algebras) is weakened to \((x;y);1 = x;(y;1)\), an equational law called “semiassociativity”, then Jónsson’s original theorem fails, since there is an infinite semiassociative relation algebra generated by a single equivalence element.

These examples put some limits on the solution on Jónsson’s original problem, but Givant generalizes in other directions. Indeed, he shows that a relation algebra is representable if it is generated by a pseudo- tree of equivalence elements. A pseudo-tree of equivalence elements is a set of equivalence elements with the following properties. If \(e\) is an equivalence element in the pseudo-tree, then the equivalence elements in the pseudo-tree that contain \(e\) form a chain, and any two equivalence elements in the pseudo-tree are either disjoint or form a two-element chain. Furthermore, if the number of equivalence elements in the pseudo- tree is finite, then so is the relation algebra they generate. It follows from these results that a relation algebra is representable if it is generated by elements that are either included in the identity element \(1\text{'}\) or have the form \(x;1\) or \(1;x\).

Chapter 7 contains the main results of this monograph, some of which where mentioned above. The preceding six chapters are primarily devoted to the development of the concepts and results needed for Chapter 7.

In Chapter 1, atoms and other elements of various kinds are defined, namely, reflexive, transitive, equivalence, subidentity, ideal, and domain elements. Laws governing these various kinds of elements are presented. Some other kinds of elements are defined, namely rectangles and squares. The arithmetic of rectangles is so crucial to the later results that all of Chapter 4 is devoted to it.

Chapter 2 has general algebraic results, including the universal characterization of simple algebras, the equivalence of simplicity with subdirect indecomposability and direct indecomposability, the definitions of ideals and relativization, the connections between ideals, homomorphisms, and relativization, the fact that the relativization of a relation algebra to an equivalence element is again a relation algebra, the definitions of direct sum (also called weak direct product), inner direct product, and inner direct sum. Perfect extensions are defined, and various theorems on the existence, uniqueness, and properties of perfect extensions are mentioned. Proofs are either presented or references to proofs in the literature are given. (There is one exception. A proof of the representability of the perfect extension of a representable relation algebra can be found in the reviewer’s paper “A sequent calculus for relation algebras” [Ann. Pure Appl. Logic 25, 73-101 (1983; Zbl 0528.03016)].)

Chapter 3 is devoted to the characteristic \(\| e\|\) of an equivalence element \(e\) in a relation algebra. Suppose \(e_ 1\) is an equivalence relation on a set \(U_ 1\) with 3 or more equivalence classes. Then the characteristic of \(e_ 1\) in \({\mathfrak Re}(U_ 1)\) is 3. Suppose \(e_ 2\) is an equivalence relation on a \(U_ 2\) with less than 3 equivalence classes. Then the characteristic of \(e_ 2\) in \({\mathfrak Re}(U_ 2)\) is the number of equivalence classes of \(e_ 2\). However, the equivalence element \(\langle e_ 1,e_ 2\rangle\) in the direct product \({\mathfrak Re}(U_ 1) \times {\mathfrak Re}(U_ 2)\) has no characteristic. The general situation reflects this example. An equivalence element \(e\) has a characteristic if this makes sense, but every relation algebra with an equivalence element \(e\) can be decomposed into direct factors in which each projected image of \(e\) does have a characteristic. The concept of characteristic is recast in terms of a 4- valued measure, which is a natural generalization of the standard notion of 2-valued measure on a Boolean algebra.

Chapter 5 contains detailed descriptions of subalgebras generated by subalgebras of relativizations; start with an algebra \(\mathfrak A\), relativize to an equivalence element \(e\), thus obtaining \({\mathfrak A}(e)\), take a subalgebra \(\mathfrak B\) of \({\mathfrak A}(e)\), and describe the structure of the subalgebra of \(\mathfrak A\) generated by the universe of \(\mathfrak B\). The arithmetic of rectangles is heavily used here.

If \(n\) is 1, 2, or 3, then it is easy to see that every simple representable relation algebra is the relativization of another simple representable relation algebra to an equivalence element \(e\) with characteristic \(n\). This fact extends to arbitrary relation algebras, and the idea of the construction can be considerably generalized, leading to the concept of simple closure. Chapter 6 presents existence and uniqueness theorems for simple closures, and proves the representability of simple closures of representable relation algebras.

The monograph is highly readable, well illustrated, and has very few typographical errors.

An element \(e\) of a relation algebra is said to be an equivalence element if \(e;e = e\) and \(\breve e = e\). The reason for this definition is that the equivalence elements of \({\mathfrak Re}(U)\) are the equivalence relations over subsets of \(U\). Now the identity element \(1^{\text{'}}\) is an equivalence element, so the diversity element \(0\text{'}\) is the complement of an equivalence element. Louise Chin and Tarski modified the proof of Robinson’s theorem to show that if \(e\) is an equivalence element, then \(\overline{e};\overline{e} = \overline{e};\overline{e}; \overline{e}; \overline{e}\). Around 35 years later Bjarni Jónsson generalized the result on relation algebras generated by their diversity elements by showing that if a relation algebra is generated by a single equivalence element, then it is finite and representable. Jónsson asked whether this is still true if the single equivalence element is replaced by a finite chain (linearly ordered set) of equivalence elements. He asked whether a relation algebra that is generated by a finite chain of equivalence elements must be finite and representable. This monograph is the result of Givant’s positive answer to this question.

The seventh and last chapter gives some examples that show why Jónsson formulated the problem as he did. For example, it is natural to ask whether every relation algebra generated by two equivalence elements is finite. But it is easy to find examples of infinite representable relation algebras that are generated by two equivalence elements. Let \(e_ 1\) be the equivalence relation on \(\{0,1,2,3,\dots\}\) whose equivalence classes are \(\{0\}, \{1,2\}, \{3,4\},\dots\) and let \(e_ 2\) be the equivalence relation whose equivalence classes are \(\{0,1\}, \{2,3\}, \{4,5\},\dots.\) Then \(e_ 1\) and \(e_ 2\) generate a subalgebra of \({\mathfrak Re}(\{0, 1, 2, 3, \dots\})\) that contains all the singleton relations \(\{\langle n,n\rangle\}\) for \(n = 0,1,2,3,\dots\), and hence is infinite. These two equivalence relations do not commute, that is, \(e_ 1;e_ 2 \neq e_ 2;e_ 1\), so their relative product \(e_ 1;e_ 2\) is not an equivalence element. (Two equivalence relations commute if and only if their relative product is an equivalence relation.) A slightly more complicated example shows that two commuting equivalence relations can still generate an infinite relation algebra. For all nonnegative integers \(k\) and \(l\), let \(S(k,l)\) be the unit square in the standard \(xy\)-coordinate plane whose lower left-hand corner is the point \((k,l)\). Thus the squares \(S(k,l)\) form an infinite checkerboard in the first quadrant of the \(xy\)-plane. Into each square \(S(k,k)\) on the main diagonal put a pebble labeled with the number \(2k\). Into each square \(S(k+1,k)\) on the superdiagonal put a pebble labeled with the number \(2k + 1\). This yields a one-to-one correspondence between nonnegative integers and pebbles on the main diagonal and the superdiagonal. Into every other square put two or more unlabeled pebbles. Let \(U\) be the set of all the pebbles on the checkerboard. Say that two pebbles are “horizontally equivalent” if they occupy squares in the same horizontal row, and that two pebbles are “vertically equivalent” if their squares are in the same vertical column. It turns out that horizontal and vertical equivalence are commuting equivalence relations on the set of pebbles, but they generate an infinite subalgebra of \({\mathfrak Re}(U)\). To see this, denote horizontal and vertical equivalence by \(h\) and \(v\), respectively. Let \(a = (h \cdot v) - ((h \cdot v \cdot 0\text{'});1)\), \(e_ 1 = a;v;a\), and \(e_ 2 = a;h;a\). Then, modulo the correspondence between nonnegative integers and pebbles, we are in the previous example. Thus a representable relation algebra generated by two commuting equivalence elements may not be finite. Must a relation algebra generated by commuting equivalence elements be representable? Not necessarily, as is shown in Chapter 7 by a finite nonrepresentable relation algebra generated by three commuting equivalence elements. No such example with two commuting equivalence elements is known. Another example from Chapter 7 shows that if the associativity of relational composition (one of the equational axioms for relation algebras) is weakened to \((x;y);1 = x;(y;1)\), an equational law called “semiassociativity”, then Jónsson’s original theorem fails, since there is an infinite semiassociative relation algebra generated by a single equivalence element.

These examples put some limits on the solution on Jónsson’s original problem, but Givant generalizes in other directions. Indeed, he shows that a relation algebra is representable if it is generated by a pseudo- tree of equivalence elements. A pseudo-tree of equivalence elements is a set of equivalence elements with the following properties. If \(e\) is an equivalence element in the pseudo-tree, then the equivalence elements in the pseudo-tree that contain \(e\) form a chain, and any two equivalence elements in the pseudo-tree are either disjoint or form a two-element chain. Furthermore, if the number of equivalence elements in the pseudo- tree is finite, then so is the relation algebra they generate. It follows from these results that a relation algebra is representable if it is generated by elements that are either included in the identity element \(1\text{'}\) or have the form \(x;1\) or \(1;x\).

Chapter 7 contains the main results of this monograph, some of which where mentioned above. The preceding six chapters are primarily devoted to the development of the concepts and results needed for Chapter 7.

In Chapter 1, atoms and other elements of various kinds are defined, namely, reflexive, transitive, equivalence, subidentity, ideal, and domain elements. Laws governing these various kinds of elements are presented. Some other kinds of elements are defined, namely rectangles and squares. The arithmetic of rectangles is so crucial to the later results that all of Chapter 4 is devoted to it.

Chapter 2 has general algebraic results, including the universal characterization of simple algebras, the equivalence of simplicity with subdirect indecomposability and direct indecomposability, the definitions of ideals and relativization, the connections between ideals, homomorphisms, and relativization, the fact that the relativization of a relation algebra to an equivalence element is again a relation algebra, the definitions of direct sum (also called weak direct product), inner direct product, and inner direct sum. Perfect extensions are defined, and various theorems on the existence, uniqueness, and properties of perfect extensions are mentioned. Proofs are either presented or references to proofs in the literature are given. (There is one exception. A proof of the representability of the perfect extension of a representable relation algebra can be found in the reviewer’s paper “A sequent calculus for relation algebras” [Ann. Pure Appl. Logic 25, 73-101 (1983; Zbl 0528.03016)].)

Chapter 3 is devoted to the characteristic \(\| e\|\) of an equivalence element \(e\) in a relation algebra. Suppose \(e_ 1\) is an equivalence relation on a set \(U_ 1\) with 3 or more equivalence classes. Then the characteristic of \(e_ 1\) in \({\mathfrak Re}(U_ 1)\) is 3. Suppose \(e_ 2\) is an equivalence relation on a \(U_ 2\) with less than 3 equivalence classes. Then the characteristic of \(e_ 2\) in \({\mathfrak Re}(U_ 2)\) is the number of equivalence classes of \(e_ 2\). However, the equivalence element \(\langle e_ 1,e_ 2\rangle\) in the direct product \({\mathfrak Re}(U_ 1) \times {\mathfrak Re}(U_ 2)\) has no characteristic. The general situation reflects this example. An equivalence element \(e\) has a characteristic if this makes sense, but every relation algebra with an equivalence element \(e\) can be decomposed into direct factors in which each projected image of \(e\) does have a characteristic. The concept of characteristic is recast in terms of a 4- valued measure, which is a natural generalization of the standard notion of 2-valued measure on a Boolean algebra.

Chapter 5 contains detailed descriptions of subalgebras generated by subalgebras of relativizations; start with an algebra \(\mathfrak A\), relativize to an equivalence element \(e\), thus obtaining \({\mathfrak A}(e)\), take a subalgebra \(\mathfrak B\) of \({\mathfrak A}(e)\), and describe the structure of the subalgebra of \(\mathfrak A\) generated by the universe of \(\mathfrak B\). The arithmetic of rectangles is heavily used here.

If \(n\) is 1, 2, or 3, then it is easy to see that every simple representable relation algebra is the relativization of another simple representable relation algebra to an equivalence element \(e\) with characteristic \(n\). This fact extends to arbitrary relation algebras, and the idea of the construction can be considerably generalized, leading to the concept of simple closure. Chapter 6 presents existence and uniqueness theorems for simple closures, and proves the representability of simple closures of representable relation algebras.

The monograph is highly readable, well illustrated, and has very few typographical errors.

Reviewer: R.Maddux (Ames)