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)


    2. (b)


    3. (c)


    4. (d)


    5. (e)


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.


  2. 2.


  3. 3.


  4. 4.


  5. 5.


  6. 6.


  7. 7.


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.


  • 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