Relation algebra

From Wikipedia, the free encyclopedia

In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra equipped with an involution called "converse". The motivating example of a relation algebra is the algebra 2^X² of all binary relations on a set X, with R•S interpreted as the usual composition of binary relations and the converse of R 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 present-day purely equational form or relation algebra was developed by Alfred Tarski and his students, starting in the 1940s.

Contents 1 Definition 1.1 Axioms 2 Expressing properties of binary relations in RA 3 Expressive power 4 Examples 5 Historical remarks 6 Software 7 See also 8 Footnotes 9 References 10 External links

[edit] Definition

A relation algebra (L, ∧, ∨, ¬, 0, 1, •, I, ▷, ◁, ) is an algebraic structure such that

(i) (L, ∧, ∨, •, I, ▷, ◁) is a residuated Boolean algebra, and

(ii) the unary operation x satisfies x▷I = x = I◁x.

Since x▷y can be defined in terms of composition and converse as x•y, and dually x◁y as x•y, it is not necessary to include ▷ or ◁ in the signature, which can therefore be simplified to (L, ∧, ∨, ¬, 0, 1, •, I, ), the more usual form of the signature for relation algebras. On the other hand x is definable as either x▷I or I◁x, in which case a relation algebra can have the same signature as a residuated Boolean algebra. With that definition the axioms become (x▷I)▷I = x = I◁(I◁x). But this simply asserts that ▷I and I◁ are involutions. Jónsson and Tsinakis have shown that if either one is an involution then so is the other and they are then the same operation, namely converse. This leads to a particularly straightforward definition:

A relation algebra is a residuated Boolean algebra (L, ∧, ∨, ¬, 0, 1, •, I, ▷, ◁) such that I◁ is an involution.

When x◁y is viewed as a form of quotient of x by y, with I as the corresponding multiplicative unit, x = I◁x can be understood as the reciprocal of x by syntactic analogy with 1/x, a term some authors use synonymously with converse.

Since residuated Boolean algebras are axiomatized with finitely many equations, so are relation algebras, which therefore form a finitely axiomatized variety called RA, the variety of relation algebras.

[edit] Axioms

The axioms B1-B10 below are adapted from Givant (2006: 283), and were first set out by Tarski in 1948.^[1] This axiomatization is predicated on a relation algebra being an algebraic structure over some Cartesian square L, having signature 〈L,∨,•,^–, , I〉 of type 〈2,2,1,1,0〉.

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).

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

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.

[edit] 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 inequalities or equalities using RA operations. Below, an inequality of the form A≤B is shorthand for a Boolean equation of the form 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 those of this entry. Chpt. 3.2 of Suppes (1960) contains fewer results, but they are presented as ZFC theorems, using a notation that more resembles that of this entry. Neither Carnap nor Suppes formulate their results using the RA of this entry, or in an equational manner.

R is	If and only if:
Surjective	R•R ≤ I
Injective (R surjective)	R•R ≤ I
1-to-1	R is surjective and injective.
Total or Connected	I ≤ R∨R
Functional
Function	R is functional and total.
1-1 Function	R•R = I and R•R = I. R is total, functional, and injective.
Reflexive	I ≤ R
Irreflexive	R ∧ I = 0. (0 = I–)
Transitive	R•R ≤ R
Preorder	R is reflexive and transitive.
Antisymmetric	R ∧ R ≤ I
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 total strict partial order.
Symmetric	R = R
Equivalence	R•R = R. R is a symmetric preorder.
Asymmetric	R ≠ R
Dense	R∧0 ≤ (R∧0)•(R∧0).

[edit] 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 as long as the quantifiers do not nest more than 3 deep.) 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 comprised of binary relations on some set, and closed under the standard interpretations 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, that is, the variety generated by RRA is a proper subvariety of the variety RA. In 1955, Alfred Tarski showed that RRA is itself a variety, which however, as shown by Donald Monk in 1964, has no finite axiomatization, unlike RA which is finitely axiomatized by definition. That not every relation algebra is representable is a fundamental way relation algebras differ from Boolean algebras, which are always representable as sets of subsets of some set closed under union, intersection, and complement.

[edit] Examples

1. Any Boolean algebra can be turned into a relation algebra 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². 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 for the preceding example, the standard interpretation of • is instead given by x(R•S)z = ∃y.xRySz. That is, the 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 to consist 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 made 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. Refer to the previous section for more on 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,^[2] then L is a group as well as a monoid. B4-B7 become well-known theorems of group theory, so that relation algebra becomes a proper extension of group theory as well as of Boolean algebra, a fact indicative of its great expressive power.

[edit] 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 4 deep had no RA equivalent.^[3] 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 Tarski and Givant (1987), the definitive reference for this subject. For more on the history of RA, see Maddux (1991, 2006).

[edit] Software

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

[edit] See also

Algebraic logic Allegory (category theory) Binary relation Cartesian product Cartesian square Composition of relations Converse of a relation

Cylindric algebras Extension in logic Involution Logic of relatives Relation Relation construction Relation reduction

Relational calculus Relational algebra Relative product of relations Residuated Boolean algebra Spatial-temporal reasoning Theory of relations Triadic relation

[edit] Footnotes

1. ^ Alfred Tarski (1948) "Abstract: Representation Problems for Relation Algebras," Bulletin of the AMS 54: 80.
2. ^ Tarski, A. (1941), p. 87.
3. ^ 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.

[edit] References

• Rudolf Carnap (1958) Introdution 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.
• 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.
• Bjarni Jónsson and Constantine Tsinakis, 1993, "Relation algebras as residuated Boolean algebras," Algebra Universalis 30: 469-78.
• Roger Maddux, 1991, "The Origin of Relation Algebras in the Development and Axiomatization of the Calculus of Relations," Studia Logica 50(3/4): 421-55.
• --------, 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.
• Alfred Tarski, 1941, "On the calculus of relations," Journal of Symbolic Logic 6: 73-89.
• ------, and Givant, Steven, 1987. A Formalization of Set Theory without Variables. Providence RI: American Mathematical Society.

[edit] 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 versionhere.
  • "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."
• Kahl, Wolfram, and Schmidt, Gunther, "Exploring (Finite) Relation Algebras Using Tools Written in Haskell." See homepage of the whole project.