relation algebra
It is a wellknown fact that if $A$ is a set, then $P(A)$ the power set^{} of $A$, equipped with the intersection^{} operation^{} $\cap $, the union operation $\cup $, and the complement^{} operation ${}^{\prime}$ turns $P(A)$ into a Boolean algebra^{}. Indeed, a Boolean algebra can be viewed as an abstraction of the family of subsets of a set with the usual settheoretic operations. The algebraic abstraction of the set of binary relations^{} on a set is what is known as a relation algebra.
Before defining formally what a relation algebra is, let us recall the following facts about binary relations on some given set $A$:

•
binary relations are closed under $\cap ,\cup $ and ${}^{\prime}$, and in fact, satisfy all the axioms of a Boolean algebra. In short, the set $R(A)$ of binary relations on $A$ is a Boolean algebra, where $A\times A$ is the top and $\mathrm{\varnothing}\times \mathrm{\varnothing}\phantom{\rule{veryverythickmathspace}{0ex}}(=\mathrm{\varnothing})$ is the bottom of $R(A)$;

•
if $R$ and $S$ are binary relations on $A$, then so are $R\circ S$, relation composition^{} of $R$ and $S$, and ${R}^{1}$, the inverse^{} of $R$;

•
${I}_{A}$, defined by $\{(a,a)\mid a\in A\}$, is a binary relation which is also the identity^{} with respect to $\circ $, also known as the identity relation on $A$;

•
some familiar identities:

(a)
$R\circ (S\circ T)=(R\circ S)\circ T$

(b)
${({R}^{1})}^{1}=R$

(c)
${(R\circ S)}^{1}={S}^{1}\circ {R}^{1}$

(d)
$(R\cup S)\circ T=(R\circ T)\cup (S\circ T)$

(e)
${(R\cup S)}^{1}={R}^{1}\cup {S}^{1}$

(a)
In addition, there is also a rule that is true for all binary relations on $A$:
$(R\circ S)\cap T=\mathrm{\varnothing}\mathit{\hspace{1em}}\text{iff}\mathit{\hspace{1em}}({R}^{1}\circ T)\cap S=\mathrm{\varnothing}$  (1) 
The verification of this rule is as follows: first note that sufficiency implies necessity, for if $({R}^{1}\circ T)\cap S=\mathrm{\varnothing}$, then $(R\circ S)\cap T=({({R}^{1})}^{1}\circ S)\cap T=\mathrm{\varnothing}$. To show sufficiency, suppose $(a,b)\in S$ is also an element of ${R}^{1}\circ T$. Then there is $c\in A$ such that $(a,c)\in {R}^{1}$ and $(c,b)\in T$. Therefore, $(c,a)\in R$ and $(c,b)=(c,a)\circ (a,b)\in R\circ S$ as well. This shows that $(R\circ S)\cap T\ne \mathrm{\varnothing}$.
It can be shown that Rule (1) is equivalent^{} to the following inclusion
${R}^{1}\circ {(R\circ S)}^{\prime}\subseteq {S}^{\prime}.$  (2) 
Definition. A relation algebra is a Boolean algebra $B$ with the usual Boolean operators $\vee ,\wedge {,}^{\prime}$, and additionally a binary operator $;$, a unary operator ${}^{}$, and a constant $i$ such that

1.
$a;i=a$

2.
$a;(b;c)=(a;b);c$

3.
${a}^{}=a$

4.
${(a;b)}^{}={b}^{};{a}^{}$

5.
$(a\vee b);c=(a;c)\vee (b;c)$

6.
${(a\vee b)}^{}={a}^{}\vee {b}^{}$

7.
${a}^{};{(a;b)}^{\prime}\le {b}^{\prime}$
where $\le $ is the induced partial order^{} in the underlying Boolean algebra.
Clearly, the set of all binary relations $R(A)$ on a set $A$ is a relation algebra, as we have just demonstrated. Specifically, in $R(A)$, $;$ is the composition operator $\circ $, ${}^{}$ is the inverse (or converse^{}) operator ${}^{1}$, and $i$ is ${I}_{A}$.
A relation algebra is an algebraic system. As an algebraic system, we can define the usual algebraic notions, such as subalgebras^{} of an algebra^{}, homomorphisms^{} between two algebras, etc… A relation algebra $B$ that is a subalgebra of $R(A)$, the set of all binary relations on a set $A$, is called a set relation algebra.
References
 1 S. R. Givant, The Structure^{} of Relation Algebras Generated by Relativizations, American Mathematical Society (1994).
Title  relation algebra 

Canonical name  RelationAlgebra 
Date of creation  20130322 17:48:18 
Last modified on  20130322 17:48:18 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  11 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03G15 
Classification  msc 06E25 
Related topic  OperationsOnRelations 
Defines  set relation algebra 