Relation algebras with \(n\)-dimensional relational bases (Q1964020): Difference between revisions

This paper provides an illuminating relative representation theory for relation algebras with \(n\)-dimensional bases, and confirms a conjecture, first published in 1983, that the class of \((n+1)\)-dimensional relation algebras is not finitely axiomatizable relative to the larger class of \(n\)-dimensional relation algebras. Every relation algebra \(A\) has a relative representation, that is, an isomorphic embedding of \(A\) into a relation algebra whose elements are subsets of some binary relation \(R\), whose Boolean operations are intersection, union, and complementation relative to \(R\), and whose relative operations are relativized to \(R\). For example, the relative product of two binary relations is the result of composing the two relations and intersecting the result with \(R\). The binary relation \(R\) can always be arranged to be symmetric and reflexive, but it can be an equivalence relation only if \(A\) is a representable relation algebra. An \(n\)-dimensional relation algebra \(A\) is, by definition, a subalgebra of an atomic relation algebra with an \(n\)-dimensional basis. An \(n\)-dimensional basis is a special set of \(n\times n\) matrices of atoms. Each \(n\times n\) matrix of atoms serves as an abstract algebraic analog of a sequence of length \(n\). To be a basis a set of matrices must be closed under various operations that correspond in certain ways to the operations of permuting the elements of a sequence, or replacing one element in a sequence with another. The authors show that if \(A\) is an \(n\)-dimensional relation algebra, then it has what they call an \(n\)-square relativized representation, one in which \(R\) is a kind of binary approximation to an \(n\)-ary relation. If the algebra \(A\) is also atomic, then it has an \(n\)-square relativized representation that is also complete, that is, it preserves arbitrary meets and joins. From these results the authors also show that the class of \(n\)-dimensional relation algebras has a recursive equational axiomatization. The primary technical innovation in this paper is a method for constructing, from two relational structures that have only unary and binary relations, a complete atomic relation algebra that has an \(n\)-dimensional basis if and only if there is a strategy for playing a certain Ehrenfeucht-Fraïssé game on the two relational structures. This construction is used to show that the class of \((n+1)\)-dimensional relation algebras is not finitely axiomatizable relative to the \(n\)-dimensional relation algebras, and that the class of atomic algebras with complete \(n\)-square relativized representations is elementary if and only if \(n\) is 3 or 4.