What is a "general" relation algebra?

Question

I'm trying to understand why (or if) the axioms of relation algebras are "the right ones." For example, we can back up the idea that the group axioms exactly capture the notion of "symmetries of an object" with the fact that every group is isomorphic to the automorphism group of some graph; that is, we have a well-motivated way (the construction $\mathfrak{A}\leadsto \mathit{Aut}(\mathfrak{A})$ to produce some things which are groups, and in fact up to isomorphism every group appears as the result of that construction.

I'm looking for something similar for relation algebras. The problem is the existence of non-representable relation algebras: any construction $\mathfrak{A}\leadsto\mathit{Rel}(\mathfrak{A})$ which sends a structure to some set of relations on the underlying set of that structure will fail to capture relation algebras. At best it will yield the proper subvariety $\mathsf{RRA}$ of representable relation algebras. At the moment, this latter variety seems much more natural to me. Of course it's not very well-behaved - in particular, there is no finite equational axiomatization of $\mathsf{RRA}$ - but I understand where general elements of it "come from."

Is there a reasonably-simple process for producing relation algebras which yields every relation algebra up to isomorphism (or at least such that the variety of r.a.s so yielded is $\mathsf{RA}$ itself)?

Basically, if I run into a relation algebra in the wild, how should I think about it? There is one natural candidate that leaps to mind, namely the construal of $2^G$ as a relation algebra for each group $G$ with composition as $A\circ B=\{ab: a\in A,b\in B\}$, identity as $\{e\}$, and converse as $A{\check{}}=\{a^{-1}: a\in A\}$, but the "surjectivity" of this construction isn't apparent to me.

Answer 1

There is one natural candidate that leaps to mind, namely the construal of $2^G$ as a relation algebra for each group $G$ $\ldots$

This construction will not answer your question, since each relation algebra of the form $2^G$ is representable. To see this, for each $A\subseteq G$ define a binary relation $\rho_A$ on $G$ by $ \rho_A :=\{(x,y)\in G^2\;|\; x^{-1}y\in A\}. $ Now check that

1. $\rho_A\cup \rho_B = \rho_{A\cup B}$
2. $\rho_A\cap \rho_B = \rho_{A\cap B}$
3. $\rho_A\circ \rho_B = \rho_{A\cdot B}$
4. $\rho_{\{e\}} = \Delta$ (the equality relation)
5. $\emptyset = \rho_{\emptyset}$
6. $G\times G=\rho_G$
7. $(\rho_A)^{\cup} = \rho_{A^{\cup}}$
8. $(G\times G)\setminus\rho_A = \rho_{G\setminus A}$.
9. $A=B$ iff $\rho_A=\rho_B$.

These show that $A\mapsto \rho_A$ is a representation of $2^G$. Thus the $2^G$-construction is ``insufficiently surjective''.

---

Concerning the original question about why the axioms of RA are ``the right ones'', let me
add a pointer to the recent paper

Rob Egrot and Robin Hirsch
First-order axiomatisations of representable relation algebras need formulas of unbounded quantifier depth
The Journal of Symbolic Logic. 2022;87(3):1283-1300.

On the second page of this article the authors write:

So Tarski’s axiomatisation of RA was in a sense a failure, but it also turns out to be a remarkable success, for the following reason. Relation algebra equations correspond exactly with first-order statements about binary relations that can be stated using at most 3 variables (see [25, theorems 3.9(viii)(ix)] for a proof), and, moreover, a relation algebra equation is valid in RA if and only if the corresponding first-order sentence is provable (in classical proof systems) using at most 4 variables [20, theorem 24]. So Tarski’s axioms neatly capture an intuitively meaningful fragment of the first-order theory of binary relations. Furthermore, an axiomatisation such that the ‘4’ in the statement above could be replaced by ‘5’ would require an infinite number of additional axioms (this result seems to lack a precise statement in the literature, but it can be pieced together from the material in e.g. [12, section 6]).

Answer 2

I don't know anything about the history and context of this idea of a relation algebra but the definition doesn't smell like "the right one" to me, and for a simple reason: why restrict attention to binary relations?

We can consider, for any set $X$, collections of $n$-ary relations for every $n$ (that is, subsets of $X^n$), which form Boolean subalgebras of each $X^n$ and are also closed under composition and maybe also projection and maybe also permutations. This gadget forms a variation of a Lawvere theory (we just replace functions with relations) which one might call a concrete relational Lawvere theory, and then we can try to axiomatize such things (a collection $B_n$ of Boolean algebras equipped with a family of composition and maybe also projection operations and maybe also permutation actions, such that...).

This is a structure I wanted to try thinking about awhile ago because of the following question: given a group $G$ acting on a set $X$, what is the "maximal structure" preserved by this group action? I think it must be the collection of all $G$-invariant subsets of all finite products $X^n$, or the "$G$-invariant relations on $X$" (an $n$-ary and "set-theoretic" version of the Hecke algebra), which forms a concrete relational Lawvere theory, and then I was hoping to find conditions under which $G$ was exactly the automorphism group of this structure. (Very likely someone already knows this.)

Anyway, I don't know if it would be harder or easier for such a thing to be representable, and I have no idea what axioms to impose, but in any case the restriction to binary relations doesn't seem natural to me.

Answer 3

As relation algebras are Boolean algebras with extra bits of structure (sometimes `with operations'), they occur importantly in the algebraic semantics of modal logics (see for instance the paper R. Goldblatt, Algebraic Polymodal Logic: A Survey, published in the Logic Journal of the IGPL, 8, (2000) pages 393–450, Special Issue on Algebraic Logic).

There the point is that the logic is dual to the algebra. (see P. Blackburn, M. de Rijke, and Y. Venema, Modal Logic, Cambridge Tracts in Theoretical Computer Science perhaps, as well). Such dualities are often linked with representability results (especially when viewed categorically, via the Yoneda embedding etc).

How to think of or motivate general relation algebras may be answered by looking at the corresponding modal logics, at least in some interesting cases. These have a geometric semantics (thus interpreting the logic in terms of structures nearer to spatial ones, Kripke frames etc) and the algebraic / relation based semantics using Boolean algebras with operators.

Answer 4

I understand where general elements of it "come from."

Well, you do and you don't. You do because you know the elements of a representable relation algebra are relations on some set. You don't because you don't know which set.

In the case of groups, the construction which realizes each abstract element of a group as a bijection is simple: just let the group act on itself. The existential quantification over all possible representations may therefore be eliminated in favor of the Cayley representation.

The Cayley representation does not have an analogue in relation algebras. In fact, the problem of deciding whether a finite algebra is representable is undecidable (Hirsch & Hodkinson 2001, Representability is not decidable for finite relation algebras). There are, again in contrast to groups, even finite relation algebras which are not finitely representable (i.e. representable by relations over a finite set). Not having a finite axiomatization is one thing, but not even being able to decide if a finite algebra lies in your variety is quite another.

By the way, an unrelated motivation to care about non-representable relation algebras is that they do have some uses. For example, every modular lattice can be represented as the lattice of equivalence elements of some symmetric relation algebra (Maddux 1981, Embedding modular lattices into relation algebras). In this case you can construct the relation algebra explicitly. Such relation algebras must be non-representable in general, because in representable relation algebras if the equivalence elements commute they in fact form an Arguesian lattice (Jónsson 1953, On the representation of lattices).