relation algebra

It is a well-known 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 set-theoretic 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$:

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$.

 $\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. 1.

$a\ ;i=a$

2. 2.

$a\ ;(b\ ;c)=(a\ ;b)\ ;c$

3. 3.

$a^{--}=a$

4. 4.

$(a\ ;b)^{-}=b^{-}\ ;a^{-}$

5. 5.

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

6. 6.

$(a\vee b)^{-}=a^{-}\vee b^{-}$

7. 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

Title relation algebra RelationAlgebra 2013-03-22 17:48:18 2013-03-22 17:48:18 CWoo (3771) CWoo (3771) 11 CWoo (3771) Definition msc 03G15 msc 06E25 OperationsOnRelations set relation algebra