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 :
some familiar identities:
In addition, there is also a rule that is true for all binary relations on :
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 .
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.
- 1 S. R. Givant, The Structure of Relation Algebras Generated by Relativizations, American Mathematical Society (1994).
|Date of creation||2013-03-22 17:48:18|
|Last modified on||2013-03-22 17:48:18|
|Last modified by||CWoo (3771)|
|Defines||set relation algebra|