# 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$:

• 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:

1. (a)

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

2. (b)

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

3. (c)

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

4. (d)

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

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

• 1 S. R. Givant, The Structure of Relation Algebras Generated by Relativizations, American Mathematical Society (1994).
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