Skip to main content
edited tags
Link
YCor
  • 63.9k
  • 5
  • 187
  • 286
Became Hot Network Question
Source Link
Noah Schweber
  • 20.7k
  • 10
  • 111
  • 332

What is a "general" relation algebra?

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.