Relation algebra

In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation. The motivating example of a relation algebra is the algebra 2X² of all binary relations on a set X, that is, subsets of the cartesian square X2, with R•S interpreted as the usual composition of binary relations R and S, and with the converse of R as the converse relation. In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation. The motivating example of a relation algebra is the algebra 2X² of all binary relations on a set X, that is, subsets of the cartesian square X2, 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 treated here 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 (L, ∧, ∨, −, 0, 1, •, I, ˘) is an algebraic structure equipped with the Boolean operations of conjunction x∧y, disjunction x∨y, and negation x−, the Boolean constants 0 and 1, the relational operations of composition x•y and converse x˘, and the 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 five 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. Following Jónsson and Tsinakis (1993) it is convenient to define additional operations x◁y = x•y˘, and, dually, x▷y = x˘•y . Jónsson and Tsinakis showed that I◁x = x▷I, and that both were equal to x˘. Hence a relation algebra can equally well be defined as an algebraic structure (L, ∧, ∨, −, 0, 1, •, I, ◁, ▷). The advantage of this signature over the usual one is that a relation algebra can then be defined in full simply as a residuated Boolean algebra for which I◁x is an involution, that is, I◁(I◁x) = x . The latter condition can be thought of as the relational counterpart of the equation 1/(1/x) = x for ordinary arithmetic reciprocal, and some authors use reciprocal as a synonym for converse. Since residuated Boolean algebras are axiomatized with finitely many identities, so are relation algebras. Hence the latter form a variety, the variety RA of relation algebras. Expanding the above definition as equations yields the following finite axiomatization. The axioms B1-B10 below are adapted from Givant (2006: 283), and were first set out by Tarski in 1948. L is a Boolean algebra under binary disjunction, ∨, and unary complementation ()−: This axiomatization of Boolean algebra is due to Huntington (1933). Note that the meet of the implied Boolean algebra is not the • operator (even though it distributes over ∨ {displaystyle vee } like a meet does), nor is the 1 of the Boolean algebra the I constant. L is a monoid under binary composition (•) and nullary identity I: