Search for a command to run...
?1. Summary A family of binary relations, or sets of ordered pairs, which is a boolean algebra, which is closed under the operations of forming converses and relative products, and which contains an identity relation, constitutes what Tarski has called a proper relational algebra. Tarski has given a set of axioms for abstract algebras of this type, and has raised the question whether every abstract algebraic system satisfying these axioms is isomorphic to a proper relational algebra. It follows from the results established below that this is not the case. In Part One we obtain, after some preliminaries, a set C of conditions which are necessary and sufficient for a finite algebra to be isomorphic to a proper relational algebra. A finite model is exhibited which satisfies all of Tarski's axioms, but which does not satisfy all the conditions C, and hence is not representable. The conditions C, which are infinite in number and non-finitary in the sense that they contain bound variables, are necessary for any relational algebra, finite or infinite, that is complete as a boolean algebra, to be representable. In Part Two it is shown, by means of an infinite model, that no set of finitary axioms suffices to characterize the class of representable relational algebras. The relation of these results to some unsolved problems is discussed in the last section (?15).