PlanetMath: relation algebra

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (191)
Orphanage
Unclass'd
Unproven (496)
Corrections (10)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

relation algebra

(Definition)

It is a well-known fact that if is a set, then the power set of , equipped with the intersection operation $\cap$ , the union operation $\cup$ , and the complement operation turns 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 :

binary relations are closed under $\cap,\cup$ and , and in fact, satisfy all the axioms of a Boolean algebra. In short, the set of binary relations on is a Boolean algebra, where $A\times A$ is the top and $\varnothing\times \varnothing (=\varnothing)$ is the bottom of ;
if and are binary relations on , then so are $R\circ S$ , relation composition of and , and $R^{-1}$ , the inverse of ;
, defined by $\lbrace (a,a)\mid a\in A\rbrace$ , is a binary relation which is also the identity with respect to $\circ$ , also known as the identity relation on ;
some familiar identities:
1. $R\circ (S\circ T) = (R\circ S)\circ T$
2. $(R^{-1})^{-1}=R$
3. $(R\circ S)^{-1} = S^{-1}\circ R^{-1}$
4. $(R\cup S)\circ T= (R\circ T)\cup (S\circ T)$
5. $(R\cup S)^{-1}=R^{-1}\cup S^{-1}$

In addition, there is also a rule that is true for all binary relations on :

$\displaystyle (R\circ S)\cap T=\varnothing$ iff $\displaystyle \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\ne \varnothing$ .

It can be shown that Rule (1) is equivalent to the following inclusion

$\displaystyle R^{-1}\circ(R\circ S)'\subseteq S'.$

(2)

Definition. A relation algebra is a Boolean algebra with the usual Boolean operators $\vee, \wedge, '$ , and additionally a binary operator $\ ;$ , a unary operator , and a constant such that

$a\ ;i=a$
$a\ ;(b\ ; c)=(a\ ;b)\ ;c$
$a^{--}=a$
$(a\ ;b)^-=b^-\ ;a^-$
$(a \vee b)\ ; c=(a\ ; c)\vee (b\ ; c)$
$(a \vee b)^- = a^- \vee b^-$
$a^- \ ; (a\ ; b)'\le b'$

where $\le$ is the induced partial order in the underlying Boolean algebra.

Clearly, the set of all binary relations on a set is a relation algebra, as we have just demonstrated. Specifically, in , $\ ;$ is the composition operator $\circ$ , is the inverse (or converse) operator $^{-1}$ , and is .

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 that is a subalgebra of , the set of all binary relations on a set , is called a set relation algebra.