# 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 2^{X²} of all binary relations on a set *X*, that is, subsets of the cartesian square *X*^{2}, with *R*•*S* interpreted as the usual composition of binary relations *R* and *S*, and with the converse of *R* interpreted as the inverse 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.

## Definition

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 relation algebras. 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.

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.

### Axioms

The axioms **B1-B10** below are adapted from Givant (2006: 283), and were first set out by Tarski in 1948.^{[1]}

*L* is a Boolean algebra under binary disjunction, ∨, and unary complementation ()^{−}:

**B1**:*A*∨*B*=*B*∨*A***B2**:*A*∨ (*B*∨*C*) = (*A*∨*B*) ∨*C***B3**: (*A*^{−}∨*B*)^{−}∨ (*A*^{−}∨*B*^{−})^{−}=*A*

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 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**:

**B4**:*A*•(*B*•*C*) = (*A*•*B*)•*C***B5**:*A*•**I**=*A*

Unary converse ()^{} is an involution with respect to composition:

**B6**:*A*^{}=*A***B7**: (*A*•*B*)^{}=*B*^{}•*A*^{}

Axiom B6 defines conversion as an involution, whereas B7 expresses the antidistributive property of conversion relative to composition.^{[2]}

Converse and composition distribute over disjunction:

**B8**: (*A*∨*B*)^{}=*A*^{}∨*B*^{}**B9**: (*A*∨*B*)•*C*= (*A*•*C*)∨(*B*•*C*)

**B10** is Tarski's equational form of the fact, discovered by Augustus De Morgan, that *A*•*B* ≤ *C*^{−} *A*^{}•*C* ≤ *B*^{−} *C*•*B*^{} ≤ *A*^{−}.

**B10**: (*A*^{}•(*A*•*B*)^{−})∨*B*^{−}=*B*^{−}

These axioms are ZFC theorems; for the purely Boolean **B1-B3**, this fact is trivial. After each of the following axioms is shown the number of the corresponding theorem in chpt. 3 of Suppes (1960), an exposition of ZFC: **B4** 27, **B5** 45, **B6** 14, **B7** 26, **B8** 16, **B9** 23.

## Expressing properties of binary relations in RA

The following table shows how many of the usual properties of binary relations can be expressed as succinct **RA** equalities or inequalities. Below, an inequality of the form *A*≤*B* is shorthand for the Boolean equation *A*∨*B* = *B*.

The most complete set of results of this nature is chpt. C of Carnap (1958), where the notation is rather distant from that of this entry. Chpt. 3.2 of Suppes (1960) contains fewer results, presented as ZFC theorems and using a notation that more resembles that of this entry. Neither Carnap nor Suppes formulated their results using the **RA** of this entry, or in an equational manner.

R is | If and only if: |
---|---|

Functional | R^{}•R ≤ I |

Left-total | I ≤ R•R^{} (R^{} is surjective) |

Function | functional and left-total. |

Injective | R•R^{} ≤ I (R^{} is functional) |

Surjective | I ≤ R^{}•R (R^{} is left-total) |

Bijection | R^{}•R = R•R^{} = I (Injective surjective function) |

Transitive | R•R ≤ R |

Reflexive | I ≤ R |

Coreflexive | R ≤ I |

Irreflexive | R ∧ I = 0 |

Symmetric | R^{} = R |

Antisymmetric | R ∧ R^{} ≤ I |

Asymmetric | R ≠ R^{} |

Total | R ∨ R^{} = 1 |

Connex | I ∨ R ∨ R^{} = 1 |

Idempotent | R•R = R |

Preorder | R is transitive and reflexive. |

Equivalence | R is a symmetric preorder. |

Partial order | R is an antisymmetric preorder. |

Total order | R is a total partial order. |

Strict partial order | R is transitive and irreflexive. |

Strict total order | R is a connex strict partial order. |

Dense | R ∧ I^{−} ≤ (R ∧ I^{−})•(R ∧ I^{−}). |

## Expressive power

The metamathematics of **RA** are discussed at length in Tarski and Givant (1987), and more briefly in Givant (2006).

**RA** consists entirely of equations manipulated using nothing more than uniform replacement and the substitution of equals for equals. Both rules are wholly familiar from school mathematics and from abstract algebra generally. Hence **RA** proofs are carried out in a manner familiar to all mathematicians, unlike the case in mathematical logic generally.

**RA** can express any (and up to logical equivalence, exactly the) first-order logic (FOL) formulas containing no more than three variables. (A given variable can be quantified multiple times and hence quantifiers can be nested arbitrarily deeply by "reusing" variables.) Surprisingly, this fragment of FOL suffices to express Peano arithmetic and almost all axiomatic set theories ever proposed. Hence **RA** is, in effect, a way of algebraizing nearly all mathematics, while dispensing with FOL and its connectives, quantifiers, turnstiles, and modus ponens. Because **RA** can express Peano arithmetic and set theory, Gödel's incompleteness theorems apply to it; **RA** is incomplete, incompletable, and undecidable. (N.B. The Boolean algebra fragment of **RA** is complete and decidable.)

The **representable relation algebras**, forming the class **RRA**, are those relation algebras isomorphic to some relation algebra consisting of binary relations on some set, and closed under the intended interpretation of the **RA** operations. It is easily shown, e.g. using the method of pseudoelementary classes, that **RRA** is a quasivariety, that is, axiomatizable by a universal Horn theory. In 1950, Roger Lyndon proved the existence of equations holding in **RRA** that did not hold in **RA**. Hence the variety generated by **RRA** is a proper subvariety of the variety **RA**. In 1955, Alfred Tarski showed that **RRA** is itself a variety. In 1964, Donald Monk showed that **RRA** has no finite axiomatization, unlike **RA**, which is finitely axiomatized by definition.

### Q-Relation Algebras

An **RA** is a Q-Relation Algebra (**QRA**) if, in addition to **B1-B10**, there exist some *A* and *B* such that (Tarski and Givant 1987: §8.4):

**Q0**:*A*^{}•*A*≤**I****Q1**:*B*^{}•*B*≤**I****Q2**:*A*^{}•*B*= 1

Essentially these axioms imply that the universe has a (non-surjective) pairing relation whose projections are *A* and *B*. It is a theorem that every **QRA** is a **RRA** (Proof by Maddux, see Tarski & Givant 1987: 8.4(iii) ).

Every **QRA** is representable (Tarski and Givant 1987). That not every relation algebra is representable is a fundamental way **RA** differs from **QRA** and Boolean algebras, which, by Stone's representation theorem for Boolean algebras, are always representable as sets of subsets of some set, closed under union, intersection, and complement.

## Examples

1. Any Boolean algebra can be turned into a **RA** by interpreting conjunction as composition (the monoid multiplication •), i.e. *x*•*y* is defined as *x*∧*y*. This interpretation requires that converse interpret identity (*ў* = *y*), and that both residuals *y*\*x* and *x*/*y* interpret the conditional *y*→*x* (i.e., ¬*y*∨*x*).

2. The motivating example of a relation algebra depends on the definition of a binary relation *R* on a set *X* as any subset *R* ⊆ *X*², where *X*² is the Cartesian square of *X*. The power set 2^{X²} consisting of all binary relations on *X* is a Boolean algebra. While 2^{X²} can be made a relation algebra by taking *R*•*S* = *R*∧*S*, as per example (1) above, the standard interpretation of • is instead *x*(*R*•*S*)*z* = ∃*y*:*xRy.ySz*. That is, the ordered pair (*x*,*z*) belongs to the relation *R*•*S* just when there exists *y* ∈ *X* such that (*x*,*y*) ∈ *R* and (*y*,*z*) ∈ *S*. This interpretation uniquely determines *R*\*S* as consisting of all pairs (*y*,*z*) such that for all *x* ∈ *X*, if *xRy* then *xSz*. Dually, *S*/*R* consists of all pairs (*x*,*y*) such that for all *z* ∈ *X*, if *yRz* then *xSz*. The translation *ў* = ¬(y\¬**I**) then establishes the converse *R*^{} of *R* as consisting of all pairs (*y*,*x*) such that (*x*,*y*) ∈ *R*.

3. An important generalization of the previous example is the power set 2^{E} where *E* ⊆ *X*² is any equivalence relation on the set *X*. This is a generalization because *X*² is itself an equivalence relation, namely the complete relation consisting of all pairs. While 2^{E} is not a subalgebra of 2^{X²} when *E* ≠ *X*² (since in that case it does not contain the relation *X*², the top element 1 being *E* instead of *X*²), it is nevertheless turned into a relation algebra using the same definitions of the operations. Its importance resides in the definition of a *representable relation algebra* as any relation algebra isomorphic to a subalgebra of the relation algebra 2^{E} for some equivalence relation *E* on some set. The previous section says more about the relevant metamathematics.

4. If group sum or product interprets composition, group inverse interprets converse, group identity interprets **I**, and if *R* is a one-to-one correspondence, so that *R*^{}•*R* = *R•R*^{} = **I**,^{[3]} then *L* is a group as well as a monoid. **B4**-**B7** become well-known theorems of group theory, so that **RA** becomes a proper extension of group theory as well as of Boolean algebra.

## Historical remarks

DeMorgan founded **RA** in 1860, but C. S. Peirce took it much further and became fascinated with its philosophical power. The work of DeMorgan and Peirce came to be known mainly in the extended and definitive form Ernst Schröder gave it in Vol. 3 of his *Vorlesungen* (1890–1905). *Principia Mathematica* drew strongly on Schröder's **RA**, but acknowledged him only as the inventor of the notation. In 1912, Alwin Korselt proved that a particular formula in which the quantifiers were nested four deep had no **RA** equivalent.^{[4]} This fact led to a loss of interest in **RA** until Tarski (1941) began writing about it. His students have continued to develop **RA** down to the present day. Tarski returned to **RA** in the 1970s with the help of Steven Givant; this collaboration resulted in the monograph by Tarski and Givant (1987), the definitive reference for this subject. For more on the history of **RA**, see Maddux (1991, 2006).

## Software

- RelMICS / Relational Methods in Computer Science maintained by Wolfram Kahl
- Carsten Sinz: ARA / An Automatic Theorem Prover for Relation Algebras

## See also

## Footnotes

- ↑ Alfred Tarski (1948) "Abstract: Representation Problems for Relation Algebras,"
*Bulletin of the AMS*54: 80. - ↑ Chris Brink; Wolfram Kahl; Gunther Schmidt (1997).
*Relational Methods in Computer Science*. Springer. pp. 4 and 8. ISBN 978-3-211-82971-4. - ↑ Tarski, A. (1941), p. 87.
- ↑ Korselt did not publish his finding. It was first published in Leopold Loewenheim (1915) "Über Möglichkeiten im Relativkalkül,"
*Mathematische Annalen*76: 447–470. Translated as "On possibilities in the calculus of relatives" in Jean van Heijenoort, 1967.*A Source Book in Mathematical Logic, 1879–1931*. Harvard Univ. Press: 228–251.

## References

- Rudolf Carnap (1958)
*Introduction to Symbolic Logic and its Applications*. Dover Publications. - Givant, Steven (2006). "The calculus of relations as a foundation for mathematics".
*Journal of Automated Reasoning*.**37**: 277–322. doi:10.1007/s10817-006-9062-x. - Halmos, P. R., 1960.
*Naive Set Theory*. Van Nostrand. - Leon Henkin, Alfred Tarski, and Monk, J. D., 1971.
*Cylindric Algebras, Part 1*, and 1985,*Part 2*. North Holland. - Hirsch R., and Hodkinson, I., 2002,
*Relation Algebra by Games*, vol. 147 in*Studies in Logic and the Foundations of Mathematics*. Elsevier Science. - Jónsson, Bjarni; Tsinakis, Constantine (1993). "Relation algebras as residuated Boolean algebras".
*Algebra Universalis*.**30**: 469–78. doi:10.1007/BF01195378. - Maddux, Roger (1991). "The Origin of Relation Algebras in the Development and Axiomatization of the Calculus of Relations" (PDF).
*Studia Logica*.**50**(3–4): 421–455. doi:10.1007/BF00370681. - --------, 2006.
*Relation Algebras*, vol. 150 in*Studies in Logic and the Foundations of Mathematics*. Elsevier Science. - Patrick Suppes, 1960.
*Axiomatic Set Theory*. Van Nostrand. Dover reprint, 1972. Chpt. 3. - Gunther Schmidt, 2010.
*Relational Mathematics*. Cambridge University Press. - Tarski, Alfred (1941). "On the calculus of relations".
*Journal of Symbolic Logic*.**6**: 73–89. doi:10.2307/2268577. JSTOR 2268577. - ------, and Givant, Steven, 1987.
*A Formalization of Set Theory without Variables*. Providence RI: American Mathematical Society.

## External links

- Yohji AKAMA, Yasuo Kawahara, and Hitoshi Furusawa, "Constructing Allegory from Relation Algebra and Representation Theorems."
- Richard Bird, Oege de Moor, Paul Hoogendijk, "Generic Programming with Relations and Functors."
- R.P. de Freitas and Viana, "A Completeness Result for Relation Algebra with Binders."
- Peter Jipsen:
- Relation algebras. In Mathematical structures. If there are problems with LaTeX, see an old HTML version here.
- "Foundations of Relations and Kleene Algebra."
- "Computer Aided Investigations of Relation Algebras."
- "A Gentzen System And Decidability For Residuated Lattices."

- Vaughan Pratt:
- "Origins of the Calculus of Binary Relations." A historical treatment.
- "The Second Calculus of Binary Relations."

- Priss, Uta:
- "An FCA interpretation of Relation Algebra."
- "Relation Algebra and FCA" Links to publications and software

- Kahl, Wolfram, and Schmidt, Gunther, "Exploring (Finite) Relation Algebras Using Tools Written in Haskell." See homepage of the whole project.