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.