Last updated
Was this helpful?
Last updated
Was this helpful?
In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse (unary operation).
The motivating example of a relation algebra is the algebra 2↑X² of all binary relations on a set X, that is, subsets of the cartesian square X², with R • S interpreted as the usual composition of binary relations R and S, and with the converse of R as the converse relation.
Relation algebra emerged in the 19th-century work of Augustus De Morgan and Charles Peirce, which culminated in the algebraic logic of Ernst Schröder.
The equational form of relation algebra was developed by Alfred Tarski and his students, starting in the 1940s.
Tarski and Givant (1987) applied relation algebra to a variable-free treatment of axiomatic set theory, with the implication that mathematics founded on set theory could itself be conducted without variables.
A relation algebra (𝙇, ∧, ∨, ⁻, 0, 1, •, ˘, 𝑰) is an algebraic structure equipped with the Boolean operations of
conjunction x ∧ y
disjunction x ∨ y
negation x⁻
Boolean constant 0
Boolean constant 1
relational operation of composition x • y
relational operation of converse x˘
relational constant I
such that these operations and constants satisfy certain equations constituting an axiomatization of a calculus of relations.
Roughly, a relation algebra is to a system of binary relations on a set containing the empty (0), complete (1), and identity (I) relations and closed under these 5 operations as a group is to a system of permutations of a set containing the identity permutation and closed under composition and inverse.
However, the first order theory of relation algebras is not complete for such systems of binary relations.