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 $\mathrm{\varnothing }\times \mathrm{\varnothing }(=\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:

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