# Relation algebra

[https://en.wikipedia.org/wiki/Relation\_algebra](https://en.wikipedia.org/wiki/Relation_algebra)

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.
