This is an old revision of the document!

Table of Contents

## Relation algebras

Abbreviation: RA

### Definition

A relation algebra is a structure $\mathbf{A}=\langle A,\vee,0,\wedge,1,\neg,\circ,^{\smallsmile},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$

Example 1:

### Properties

Classtype variety undecidable undecidable undecidable no unbounded yes yes yes, $n=2$ yes yes yes yes yes yes no no no

### Finite members

$\begin{array}{lr} [http://localhost/gap/ramaddux.html Small relation algebras] f(1)= &1\\ f(2)= &1\\ f(3)= &0\\ f(4)= &3\\ f(5)= &0\\ f(6)= &0\\ \end{array}$