relation algebra (original) (raw)

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 ∩,∪ and ′, 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×A is the top and ∅×∅(=∅) is the bottom of R⁢(A);
• •
  if R and S are binary relations on A, then so are R∘S, relation composition of R and S, and R-1, the inverse of R;
• •
  IA, defined by {(a,a)∣a∈A}, is a binary relation which is also the identity with respect to ∘, also known as the identity relation on A;
• •
  some familiar identities:
  1. (a)
     R∘(S∘T)=(R∘S)∘T
  2. (b)
     (R-1)-1=R
  3. (c)
     (R∘S)-1=S-1∘R-1
  4. (d)
     (R∪S)∘T=(R∘T)∪(S∘T)
  5. (e)
     (R∪S)-1=R-1∪S-1

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

The verification of this rule is as follows: first note that sufficiency implies necessity, for if (R-1∘T)∩S=∅, then (R∘S)∩T=((R-1)-1∘S)∩T=∅. To show sufficiency, suppose (a,b)∈S is also an element of R-1∘T. Then there is c∈A such that (a,c)∈R-1 and (c,b)∈T. Therefore, (c,a)∈R and (c,b)=(c,a)∘(a,b)∈R∘S as well. This shows that (R∘S)∩T≠∅.

Definition. A relation algebra is a Boolean algebra B with the usual Boolean operators ∨,∧,′, and additionally a binary operator ;, a unary operator -, and a constant i such that

1. 1. a;i=a
2. 1. a;(b;c)=(a;b);c
3. 1. a--=a
4. 1. (a;b)-=b-;a-
5. 1. (a∨b);c=(a;c)∨(b;c)
6. 1. (a∨b)-=a-∨b-
7. 1. a-;(a;b)′≤b′

where ≤ 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 ∘, - is the inverse (or converse) operator -1, and i is IA.

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