Relation algebras and groups
by
Hajnal Andréka
Mathematical Institute, Budapest, Hungary
Coauthors: Steven Givant (Mills Colege, Oaklanad, USA)

An algebra of binary relations (or set relation algebra) is an algebra whose universe consists of binary relations on some set U, and whose operations are those of forming the (set-theoretic) union of two relations, the complement of a relation, the composition of two relations, and the inverse of a relation. There is also a distinguished element, the identity relation on U. The study of these algebras was initiated by De Morgan, and intensively developed by Peirce and Schröder in the second half of the 19th century.

In the 1940s, Tarski put the theory on a modern footing. He introduced the concept of an abstract relation algebra and used algebraic and metamathematical techniques to study them. A relation algebra is any algebra (of the same similarity type as algebras of binary relations) satisfying a certain finite set of equational postulates-equations that are valid in all algebras of binary relations. Tarski asked whether every abstract relation algebra is representable as - that is, is isomorphic to - a concrete algebra of binary relations. Lyndon provided a negative answer by constructing a relation algebra that is not represesntable. However, Jónsson and Tarski showed (even before Lyndon's construction) that the answer to the question may be positive when additional hypotheses are imposed. For example, every atomic relation algebra in which the atoms are functional is representable. (A functional element is one that satisfies the equation x^\smallsmile;x <= 1', where ^\smallsmile denotes the abstract operation of inversion, while  ;  denotes the abstract operation of relative composition and 1' denotes the identity element.) As a corollary they concluded that every relation algebra in which the Boolean unit is the sum of finitely many functional elements must also be representable. Finally, they proved that every atomic relation algebra in which the atoms are points is representable. (A point is an element that satisfies the equation x^\smallsmile;1;x <= 1' where 1 denotes the Boolean unit. Points behave like relations that consist of just one ordered pair.) Generalizing this last theorem, Maddux proved that a relation algebra in which the identity element is a sum of points and pairs is atomic and representable. The work reported in this abstract constitutes a far-reaching generalization of the theorems of Jónsson-Tarski and Maddux.

A diagonal element is one that is below the identity element 1'. A diagonal atom x is said to be measurable if its ``square'', x;1;x, is the sum of functional elements. The name comes from the fact that (in a representable algebra) the number of functional elements beneath the square x;1;x determines the ``size" of x. A relation algebra is diagonally measurable if its identity element is the sum of measurable atoms.

The study of atomic, diagonally measurable relation algebras has led to a new and quite broad construction of relation algebras, one that comprehends all full set relation algebras and simultaneously yields new and interesting classes of representable and non-representable relation algebras. It can be viewed as a generalization of the well-known construction of relation algebras as complex algebras of groups. Instead of a single group, the construction involves a system of pairwise disjoint groups, a corresponding system of isomorphisms between quotients of the groups, and a system of cosets in the quotients that serve to ``shift" relational composition. The resulting algebra is called a generalized group relation algebra. When the shifting cosets coincide with the normal subgroups by means of which the quotients are formed (i.e., they are the identity cosets in the quotient groups), the resulting relation algebra is an algebra of binary relations. It may happen, however, that the shifting cosets do not coincide with the normal subgroups, and in this case the resulting relation algebra may cease to be representable.

Theorem. Every atomic, diagonally measurable relation algebra is canonically embeddable in a generalized group relation algebra.

In fact, the (MacNeille) completion of a diagonally measurable relation algebra is again diagonally measurable (with the same atoms below the identity and the same functional elements as the original algebra), and this completion is isomorphic to (and not just embeddable in) a generalized group relation algebra. In case there are only finitely many functional elements below the square of each diagonal atom, the assumption of atomicity is superfluous: every such diagonally measurable relation algebra is automatically atomic. When the functional elements below the square on each measurable, diagonal atom form a cyclic group, or even the product of two cyclic groups, the resulting generalized group relation algebra is actually a set relation algebra (that is, the shifting cosets coincide with the normal subgroups). However, there are examples which show that, in general, generalized group relation algebras, even those based on finite groups (and in fact on groups that are copies of Z₂×Z₂×Z₂) may not be representable.

The above theorem contains the representation theorems of Jónsson-Tarski and of Maddux as very special cases. In fact, even for these special cases, it goes substantially beyond those theorems by clarifying the underlying structure of the representing algebras. For example, the representation theorem for atomic relation algebras with functional atoms is that special case of the theorem when all the groups are isomorphic to one another and the normal subgroups by means of which the quotients are formed are all trivial (i.e., they are the one-element subgroup). The representation theorem for relation algebras in which the identity element is a sum of points and pairs is that special case of the theorem when all the groups are either trivial or of order two.

Date received: August 3, 1999