relation algebra


It is a well-known fact that if A is a set, then P(A) the power setMathworldPlanetmath of A, equipped with the intersectionMathworldPlanetmath operationMathworldPlanetmath , the union operation , and the complementPlanetmathPlanetmath operation turns P(A) into a Boolean algebraMathworldPlanetmath. 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 relationsMathworldPlanetmath 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 , 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 RS, relation compositionPlanetmathPlanetmath of R and S, and R-1, the inverseMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath of R;

  • IA, defined by {(a,a)aA}, is a binary relation which is also the identityPlanetmathPlanetmath with respect to , also known as the identity relation on A;

  • some familiar identities:

    1. (a)

      R(ST)=(RS)T

    2. (b)

      (R-1)-1=R

    3. (c)

      (RS)-1=S-1R-1

    4. (d)

      (RS)T=(RT)(ST)

    5. (e)

      (RS)-1=R-1S-1

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

(RS)T= iff (R-1T)S= (1)

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

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

R-1(RS)S. (2)

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

    a;(b;c)=(a;b);c

  3. 3.

    a--=a

  4. 4.

    (a;b)-=b-;a-

  5. 5.

    (ab);c=(a;c)(b;c)

  6. 6.

    (ab)-=a-b-

  7. 7.

    a-;(a;b)b

where is the induced partial orderMathworldPlanetmath 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 converseMathworldPlanetmath) 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 subalgebrasPlanetmathPlanetmathPlanetmath of an algebraMathworldPlanetmath, homomorphismsPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath 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 StructureMathworldPlanetmath of Relation Algebras Generated by Relativizations, American Mathematical Society (1994).
Title relation algebra
Canonical name RelationAlgebra
Date of creation 2013-03-22 17:48:18
Last modified on 2013-03-22 17:48:18
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 11
Author CWoo (3771)
Entry type Definition
Classification msc 03G15
Classification msc 06E25
Related topic OperationsOnRelations
Defines set relation algebra