You are here
Homerelation algebra
Primary tabs
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 $\varnothing\times\varnothing(=\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}}$
In addition, there is also a rule that is true for all binary relations on $A$:
$\displaystyle(R\circ S)\cap T=\varnothing\quad\mbox{ iff }\quad(R^{{1}}\circ T% )\cap S=\varnothing$  (1) 
The verification of this rule is as follows: first note that sufficiency implies necessity, for if $(R^{{1}}\circ T)\cap S=\varnothing$, then $(R\circ S)\cap T=((R^{{1}})^{{1}}\circ S)\cap T=\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\neq\varnothing$.
It can be shown that Rule (1) is equivalent to the following inclusion
$\displaystyle 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}}\leq b^{{\prime}}$
where $\leq$ 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).
Mathematics Subject Classification
03G15 no label found06E25 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections