relation algebra
It is a well-known fact that if is a set, then the power set of , equipped with the intersection operation , the union operation , 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 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 is the top and is the bottom of ;
-
•
if and are binary relations on , then so are , relation composition of and , and , the inverse of ;
-
•
, defined by , is a binary relation which is also the identity with respect to , also known as the identity relation on ;
-
•
some familiar identities:
-
(a)
-
(b)
-
(c)
-
(d)
-
(e)
-
(a)
In addition, there is also a rule that is true for all binary relations on :
(1) |
The verification of this rule is as follows: first note that sufficiency implies necessity, for if , then . To show sufficiency, suppose is also an element of . Then there is such that and . Therefore, and as well. This shows that .
It can be shown that Rule (1) is equivalent to the following inclusion
(2) |
Definition. A relation algebra is a Boolean algebra with the usual Boolean operators , and additionally a binary operator , a unary operator , and a constant such that
-
1.
-
2.
-
3.
-
4.
-
5.
-
6.
-
7.
where 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 , is the inverse (or converse) operator , 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.
References
- 1 S. R. Givant, The Structure 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 |