- Relation algebra
:"Relation algebra is different from

relational algebra , a framework developed byEdgar Codd in 1970 forrelational databases ."In

mathematics , a**relation algebra**is aresiduated Boolean algebra supporting an involutaryunary operation called converse. The motivating example of a relation algebra is the algebra 2^{"X"²}of allbinary relation s on a set "X", with "R"•"S" interpreted as the usual composition of binary relations. Early forms of relation algebra emerged in the 19th century with the work ofAugustus De Morgan ,Charles Peirce , andErnst Schröder . Its present-day purely equational form was developed byAlfred Tarski and his students starting in the 1940s.**Definition**A

**relation algebra**("L", ∧, ∨, ¬, 0, 1, •,**I**, ▷, ◁,^{$reve\{\; \}$}) is an algebraic structure such that:(i) ("L", ∧, ∨, •,**I**, , ) is aresiduated Boolean algebra , and:(ii) the unary operation "x"^{$reve\{\; \}$}satisfies "x"^{$reve\{\; \}$}**I**= "x" =**I**"x"^{$reve\{\; \}$}.Since "x"▷"y" can be defined in terms of composition and converse as "x"

^{$reve\{\; \}$}•"y", and dually "x"◁"y" as "x"•"y"^{$reve\{\; \}$}, it is not necessary to include ▷ or ◁ in the signature, which can therefore be simplified to ("L", ∧, ∨, ¬, 0, 1, •,**I**,^{$reve\{\; \}$}), the more usual form of the signature for relation algebras. On the other hand "x"^{$reve\{\; \}$}is definable as either "x"▷**I**or**I**◁"x", whence 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**◁ areinvolution s. 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 aninvolution ."When "x"◁"y" is viewed as a form of quotient of "x" by "y", with

**I**as the corresponding multiplicative unit, "x"^{$reve\{\; \}$}=**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.**Examples**1. Any Boolean algebra is made a relation algebra by taking composition (the monoid multiplication) to be conjunction. This interpretation of composition uniquely determines converse to be identity ("ў" = "y") and the residuals "y""x" and "x"/"y" both to be implication "y"→"x", that is, ¬"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 it 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"^{$reve\{\; \}$}of "R" as consisting of all pairs ("y","x") such that ("x","y") ∈ "R".3. An important generalization of this example is the power set 2

^{"E"}where "E" ⊆ "X"² is anyequivalence 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. It is straightforward to show that the class**RRA**of all representable relation algebras is thequasivariety generated by the relation algebras of the form 2^{"X"²}for some "X". Less obvious is that**RRA**is in fact a variety, shown by Tarski in 1955. Earlier (1950) Lyndon had shown that**RRA**was a proper subclass of the variety**RA**(or in logical language, the**RA**axioms do not completely axiomatize concrete or representable relation algebras). Whereas**RA**is by definition finitely axiomatizable,**RRA**was shown by Monk in 1964 not to be finitely axiomatizable.**Expressing properties of binary relations in****RA**Many properties of binary relations can be succinctly expressed as equations or inequalities using

**RA**operations, as illustrated by the following."R" is total iff

**I**≤ "R"•"R"^{$^reve\{\; \}$}."R" is deterministic iff "R"

^{$^reve\{\; \}$}•"R" ≤**I**.A function is a binary relation that is total and deterministic. The next two properties generalize to all binary relations properties that are normally applied just to functions.

"R" is surjective iff

**I**≤ "R"^{$reve\{\; \}$}•R(equivalently if "R"^{$reve\{\; \}$}is total)."R" is injective iff "R"•"R"

^{$^reve\{\; \}$}≤**I**(equivalently if "R"^{$reve\{\; \}$}is deterministic)."R" is reflexive iff

**I**≤ "R"."R" is transitive iff "R"•"R" ≤ "R". A "preorder" is a reflexive transitive binary relation.

"R" is antisymmetric iff "R" ∧ "R"

^{$^reve\{\; \}$}≤**I**. A "partial order" is an antisymmetric preorder."R" is symmetric iff "R" ≤ "R"

^{$^reve\{\; \}$}. An "equivalence relation" is a symmetric preorder.**Expressive power**The

metamathematics of**RA**are discussed at length in Tarski and Givant (1987).**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 fromabstract algebra generally. Hence**RA**proofs are carried out in a manner familiar to all mathematicians, unlike the case inmathematical 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). Surprisingly, this fragment of FOL suffices to expressPeano 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 itsconnective s,quantifier s, turnstiles, andmodus ponens . Because**RA**can express Peano arithmetic and set theory, the classic theorems of Gödel apply to it;**RA**isincomplete , incompletable, andundecidable . (N.B. None of these properties describe the Boolean algebra fragment of**RA**.)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 ofpseudoelementary class es, 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 1955Alfred 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 one of the fundamental differences from Boolean algebras, all of which are representable as sets of subsets of some set closed under union, intersection, and complement.**Software*** [

*http://relmics.mcmaster.ca/html/index.html RelMICS / Relational Methods in Computer Science*] maintained by [*http://www.cas.mcmaster.ca/~kahl/ Wolfram Kahl*]

* Carsten Sinz: [*http://www-sr.informatik.uni-tuebingen.de/~sinz/ARA/ ARA / An Automatic Theorem Prover for Relation Algebras*]**Historical remarks**DeMorgan founded**RA**in 1860, butCharles 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 formErnst Schröder gave it in his "Vorlesungen" (1890-1905).Principia Mathematica drew strongly on Schröder's**RA**, but acknowledged him only as the inventor of the notation. The foundational paper for**RA**as presented here is Tarski (1941); he devised the above axioms, and he and his students have continued to write on**RA**down to the present day. Much of the content of Tarski and Givant (1987) was worked out by Tarski alone in the 1940s, who returned to the subject in the 1970s with the help of Steven Givant. For more on the history of**RA**, see Maddux (2006).**ee also***

Allegory (category theory)

*Binary relation

*Cartesian product

*Cartesian square

*Charles Peirce

* Converse of a relation

* Extension in logic

*Logic of relatives

* Relation

*Relation construction

*Relative product of relations

*Relation reduction

*Relational calculus

*Relational algebra

* Relative product of relations

*Spatial-temporal reasoning

*Theory of relations

*Triadic relation

*Residuated lattice s

*Cylindric algebra s**References*** Carnap, Rudolf, 1958. "Introduction to Symbolic Logic with Applications", Dover.

* Halmos, P. R., 1960. "Naive Set Theory". Van Nostrand.

*Bjarni Jónsson and Constantine Tsinakis, Relation algebras as residuated Boolean algebras, Algebra Universalis, 30 (1993) 469-478.

*Lucas, John Randolph, 1999. "Conceptual Roots of Mathematics". Routledge.

*Roger Maddux , 2006. "Relation Algebras", vol. 150 in "Studies in Logic and the Foundations of Mathematics". Elsevier Science.

*Leon Henkin ,Alfred Tarski , and Monk, J. D., "Cylindric Algebras Part 1" (1971) and "Part 2" (1985). North Holland.

* Hirsch R., and Hodkinson, I., 2002 "Relation Algebra by Games," v. 147 in "Studies in Logic and the Foundations of Mathematics". Elsevier Science.

*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.**External links***Yohji AKAMA, Yasuo Kawahara, and Hitoshi Furusawa, " [

*http://nicosia.is.s.u-tokyo.ac.jp/pub/staff/akama/repr.ps Constructing Allegory from Relation Algebra and Representation Theorems.*] "

*Richard Bird, Oege de Moor, Paul Hoogendijk, " [*http://citeseer.ist.psu.edu/bird99generic.html Generic Programming with Relations and Functors.*] "

* R.P. de Freitas and Viana, " [*http://www.cos.ufrj.br/~naborges/fv02.ps A Completeness Result for Relation Algebra with Binders.*] "

* [*http://www1.chapman.edu/~jipsen/ Peter Jipsen*] :

** [*http://math.chapman.edu/structuresold/files/Relation_algebras.pdf Relation algebras*] . In [*http://math.chapman.edu/cgi-bin/structures Mathematical structures.*] If there are problems with LaTeX, see an old HTML version [*http://math.chapman.edu/cgi-bin/structures.pl?Relation_algebras here.*]

** " [*http://math.chapman.edu/~jipsen/talks/RelMiCS2006/JipsenRAKAtutorial.pdf Foundations of Relations and Kleene Algebra.*] "

** " [*http://www1.chapman.edu/~jipsen/dissertation/ Computer Aided Investigations of Relation Algebras.*] "

** " [*http://citeseer.ist.psu.edu/337149.html A Gentzen System And Decidability For Residuated Lattices."*]

*Vaughan Pratt :

** " [*http://boole.stanford.edu/pub/ocbr.pdf Origins of the Calculus of Binary Relations.*] " A historical treatment.

** " [*http://boole.stanford.edu/pub/scbr.pdf The Second Calculus of Binary Relations.*] "

* Priss, Uta, " [*http://citeseer.ist.psu.edu/739624.html An FCA interpretation of Relation Algebra.*] "

* [*http://www.cas.mcmaster.ca/~kahl/ Kahl, Wolfram,*] and [*http://ist.unibw-muenchen.de/People/schmidt/ Schmidt, Gunther,*] " [*http://relmics.mcmaster.ca/~kahl/Publications/TR/2000-02/ Exploring (Finite) Relation Algebras Using Tools Written in Haskell.*] " See [*http://relmics.mcmaster.ca/tools/RATH/index.html homepage*] of the whole project.

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Relation (mathematics)**— This article sets out the set theoretic notion of relation. For a more elementary point of view, see binary relations and triadic relations. : For a more combinatorial viewpoint, see theory of relations. In mathematics, especially set theory, and … Wikipedia**Algebra**— This article is about the branch of mathematics. For other uses, see Algebra (disambiguation). Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from… … Wikipedia**Relation**— may refer to:*Relation, a person to whom one is related, i.e. a family member (see also Kinship) *Relation (mathematics), a generalization of arithmetic relations, such as = and … Wikipedia**Relation (Begriffsklärung)**— Relation (latein. relatio „das Zurücktragen“) steht für: Relation, eine bestimmte Beziehung zwischen Objekten Relation (Mathematik), die Behandlung einer eindeutigen Beziehung zwischen Dingen Relation (Datenbank), eine zweidimensionale Tabelle… … Deutsch Wikipedia**Relation (Datenbanktechnik)**— Formale Grundlage der Relation im Sinne einer Datenbankrelation ist die mathematische Definition. Die Relation ist die Basis der relationalen Algebra, die von Edgar F. Codd entwickelt wurde. Eine Relation besteht aus Attributen und Tupeln. Ein… … Deutsch Wikipedia**Algebra of sets**— The algebra of sets develops and describes the basic properties and laws of sets, the set theoretic operations of union, intersection, and complementation and the relations of set equality and set inclusion. It also provides systematic procedures … Wikipedia**Relation (Mengentheorie)**— Eine Relation ist allgemein eine Beziehung, die zwischen Dingen bestehen kann. Relationen im Sinne der Mathematik sind ausschließlich diejenigen Beziehungen, bei denen stets klar ist, ob sie bestehen oder nicht. Zwei Gegenstände können also nicht … Deutsch Wikipedia**algebra**— /al jeuh breuh/, n. 1. the branch of mathematics that deals with general statements of relations, utilizing letters and other symbols to represent specific sets of numbers, values, vectors, etc., in the description of such relations. 2. any of… … Universalium**Relation (Datenbank)**— Formale Grundlage der Relation im Sinne einer Datenbankrelation ist die mathematische Definition. Die Relation ist die Basis der relationalen Algebra, die von Edgar F. Codd entwickelt wurde. Eine Relation besteht aus Attributen und Tupeln. Ein… … Deutsch Wikipedia**Relation (Mathematik)**— Eine Relation ist allgemein eine Beziehung, die zwischen Dingen bestehen kann. Relationen im Sinne der Mathematik sind ausschließlich diejenigen Beziehungen, bei denen stets klar ist, ob sie bestehen oder nicht. Zwei Gegenstände können also nicht … Deutsch Wikipedia