INTRODUCTION The foundation of an algebraic theory of binary relations was laid by C. S. Peirce, building on earlier work of Boole and De Morgan. The basic universe of discourse of this theory is a collection of binary relations over some set, and the basic operations on these relations are those of forming unions, complements, relative products (i.e., relational compositions), and converses (i.e., inverses). There is also a distinguished relation, the identity relation. Other operations and distinguished relations studied by Peirce are definable in terms of the ones just mentioned. Such an algebra of relations is called a set relation algebra. A modern development of this theory as a theory of abstract relation algebras, axiomatized by a finite set of equations, was undertaken by Tarski and his students and colleagues, beginning around 1940. In 1942, Tarski proved that all of classical mathematics could be developed within the framework of the equational theory of relation algebras. Indeed, he created a general method for interpreting into the equational theory of relation algebras first-order theories that are strong enough to form a basis for the development of mathematics in particular, set theories and number theories. As a consequence, he established that the equational theories of relation algebras and of set relation algebras are undecidable (see Tarski [1941], p. 88 and Tarski-Givant [1987], Theorem 8.5(xii)(/3) and the historical remark in Footnote 3* on p. 168). They were the first known examples of undecidable equa- tional theories. As was pointed out in op. cit., Tarski's proof actually shows more. Namely, any class of relation algebras that contains the full set relation algebra on some infinite set (i.e., the set relation algebra whose universe consists of all binary relations on some infinite set) must have an undecidable equational theory. Tarski continued to be interested in decision problems for classes of relation algebras, and at various times he posed one or more such problems to his students. We gather together here some of these problems. TARSKI'S DECISION PROBLEMS FOR RELATION ALGEBRAS. Which of the follow- ing classes have undecidable equational theories? (1) Group relation algebras, i.e., algebras of complexes (subsets) of groups under the usual Boolean and group complex operations. (2) Abelian group relation algebras. (3) Boolean group relation algebras. (4) Abelian relation algebras, i.e., relation algebras in which the relative product operation is commutative. (5) Abelian set relation algebras. (6) Symmetric relation algebras, i.e., relation algebras in which conversion is the identity operation. Received by the editor February 7, 1995. xi
Previous Page Next Page