Relation algebras

Abbreviation: RA

Definition

A relation algebra is a structure $\mathbf{A}=\langle A,\vee,0,\wedge,1,\neg,\circ,^{\smile},e\rangle$ such that

$\langle A,\vee,0,\wedge,1,\neg\rangle$ is a Boolean algebra

$\langle A,\circ,e\rangle $ is a monoid

$\circ$ is join-preserving: $(x\vee y)\circ z=(x\circ z)\vee (y\circ z)$

$^{\smile}$ is an involution: $x^{\smile\smile}=x$, $(x\circ y)^{\smile}=y^{\smile}\circ x^{\smile}$

$^{\smile}$ is join-preserving: $(x\vee y)^{\smile}=x^{\smile}\vee y^{\smile}$

$\circ$ is residuated: $x^{\smile}\circ(\neg (x\circ y))\le\neg y$

Morphisms

Let $\mathbf{A}$ and $\mathbf{B}$ be relation algebras. A morphism from $\mathbf{A}$ to $\mathbf{B}$ is a function $h:A\to B$ that is a Boolean homomorphism and preserves $\circ$, $^{\smile}$, $e$:

$h(x\circ y)=h(x)\circ h(y)$, $h(x^{\smile})=h(x)^{\smile}$, $h(e)=e$

Examples

Example 1: $\langle \mathcal P(U^2), \cup, \emptyset, \cap, U^2, -, \circ, ^\smile, id_U \rangle$ the full relation algebra of binary relations on a set $U$.

Example 2: $\langle \mathcal P(G), \cup, \emptyset, \cap, G, -, \circ, ^\smile, \{e\} \rangle$ the group relation algebra of a group $\langle G, *, ^{-1}, e \rangle$, where $X\circ Y=\{x*y : x\in X, y\in Y\}$ and $X^\smile=\{x^{-1} : x\in X\}$.

Basic results

Properties

Finite members

$\begin{array}{lr} f(1)= &1\\ f(2)= &1\\ f(3)= &0\\ f(4)= &3\\ f(5)= &0\\ f(6)= &0\\ \end{array}$

Small relation algebras

Subclasses

Superclasses

References