Relational algebra

In mathematics and abstract algebra is a relation algebra (English: relational algebra ) a residuierte Boolean algebra that an involution (as single digit operation ), called converse , has been expanded. The relevant example of a relational algebra for this concept formation is the algebra of all two-digit relations on a set (i.e. on the subsets of the Cartesian product ), together with the concatenation of relations and the inverse relation (converse relation). ${\ displaystyle 2 ^ {A ^ {2}} = {\ mathcal {P}} (A \ times A)}$ ${\ displaystyle A}$ ${\ displaystyle A \ times A = A ^ {2}}$

definition

The following axioms are based on Givant (2006, p. 283), and were first established in 1948 by Alfred Tarski .

A relational algebra is a 9- tuple , for which applies: ${\ displaystyle (L, \ land, \ lor, \ neg, 0,1, \ circ, \ mathrm {I}, {} ^ {\ smile})}$

${\ displaystyle (L, \ land, \ lor, \ neg, 0,1)}$ is a Boolean algebra with conjunction , disjunction and negation as well as zero element and unit element : ${\ displaystyle \ land}$ ${\ displaystyle \ lor}$ ${\ displaystyle \ neg}$ ${\ displaystyle 0}$ ${\ displaystyle 1}$
${\ displaystyle (L, \ circ, \ mathrm {I})}$ is a monoid with its own element , ${\ displaystyle \ mathrm {I}}$
${\ displaystyle {} ^ {\ smile}}$ is an involution called a converse ,
${\ displaystyle \ forall a, b \ in {L} :( a \ circ b) ^ {\ smile} = b ^ {\ smile} \ circ a ^ {\ smile}}$ , d. H. the converse is true to the link , ${\ displaystyle \ circ}$
${\ displaystyle \ forall a, b \ in {L} :( a \ lor b) ^ {\ smile} = a ^ {\ smile} \ lor b ^ {\ smile}}$ ,
${\ displaystyle \ forall a, b, c \ in {L} :( a \ lor b) \ circ {c} = (a \ circ {c}) \ lor (b \ circ {c})}$ ( Distributivity ) and
${\ displaystyle \ forall a, b \ in {L} :( a ^ {\ smile} \ circ \ neg (a \ circ {b})) \ lor \ neg {b} = \ neg {b}}$ , which means nothing else than (Peirce's law). ${\ displaystyle a \ circ {b} \ leq \ neg {c} \ Leftrightarrow a ^ {\ smile} \ circ c \ leq \ neg {b} \ Leftrightarrow c \ circ b ^ {\ smile} \ leq \ neg { a}}$

Illustration of Peirce's law, here with u, v, w instead of a, b, c

example

The homogeneous two-digit relations form the relation algebra ${\ displaystyle R \ subseteq A \ times A}$

{\ displaystyle {\ mathfrak {Re}} (A) = (2 ^ {A ^ {2}}, \ cap, \ cup, {} ^ {^ {-}}, \ emptyset, A ^ {2}, \ circ, \ mathrm {I} _ {A}, {} ^ {\ smile})}

using the notations . ${\ displaystyle A ^ {2} = A \ times A, \ \; \ 2 ^ {A ^ {2}} = {\ mathcal {P}} (A \ times A)}$

Peirce algebra

A further development of this is the ( heterogeneous ) Peirce algebra , named after Charles Sanders Peirce - an abstract description of the relational algebra of homogeneous two-digit relations together with pre / post restrictions on sets. ${\ displaystyle {\ mathfrak {Re}} (A)}$

Individual references and comments

↑ a Boolean algebra whose association structure a residuierter Association 's (English: residuated algebra ), see: Marcel Erné: Algebraic lattice theory , Department of Algebra, Number Theory and Discrete Mathematics, University of Hannover
^ Alfred Tarski (1948) "Abstract: Representation Problems for Relation Algebras," Bulletin of the AMS 54: 80.
↑ Chris Brink et al. page 12
↑ According to Robin Hirsch, Ian Hodkinson: Relation algebras page 7, on: Third Indian Conference on Logic and its Applications (ICLA), 7. – 11. January 2009, Chennai, India. The tuple has been adjusted to the above definition.
↑ Of the links (one-digit) and (two-digit) - strictly speaking - the restrictions on or are meant. ${\ displaystyle {} ^ {^ {-}}, {} ^ {\ smile}}$ ${\ displaystyle \ cap, \ cup, \ circ}$ ${\ displaystyle A}$ ${\ displaystyle A ^ {2}}$

literature

Rudolf Carnap (1958) Introduction to Symbolic Logic and its Applications . Dover Publications.
Steven Givant: The calculus of relations as a foundation for mathematics . In: Journal of Automated Reasoning . 37, 2006, pp. 277-322. doi : 10.1007 / s10817-006-9062-x .
Halmos, PR , 1960. Naive Set Theory . Van Nostrand.
Leon Henkin , Alfred Tarski , and Monk, JD, 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, Constantine Tsinakis: Relation algebras as residuated Boolean algebras . In: Algebra Universalis . 30, 1993, pp. 469-78. doi : 10.1007 / BF01195378 .
Roger Maddux: The Origin of Relation Algebras in the Development and Axiomatization of the Calculus of Relations, # 3-4 . In: Studia Logica . 50, 1991, pp. 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. Chapter 3.
Gunther Schmidt , 2010. Relational Mathematics . Cambridge University Press.
Alfred Tarski : On the calculus of relations . In: Journal of Symbolic Logic . 6, 1941, pp. 73-89. doi : 10.2307 / 2268577 .
Givant, Steven, 1987. A Formalization of Set Theory without Variables . Providence RI: American Mathematical Society.

Web links

Relational Algebra (Mathepedia) (German)
Yohji Akama, Yasuo Kawahara, Hitoshi Furusawa: Constructing Allegory from Relation Algebra and Representation Theorems "(WayBack)
Richard Bird, Oege de Moor, Paul Hoogendijk: Generic Programming with Relations and Functors
RP de Freitas, JP Viana: A Completeness Result for Relation Algebra with Binders
Chris Brink, Katarina Britz, Renate A. Schmidt: Peirce Algebras

Peter Jipsen :

Vaughan Pratt :
- Origins of the Calculus of Binary Relations.
- The Second Calculus of Binary Relations.

Uta Priss :
- An FCA interpretation of Relation Algebra
- Relation algebra and FCA

Wolfram Kahl , Gunther Schmidt
- Exploring (Finite) Relation Algebras Using Tools Written in Haskell
- RATH - Relation Algebra Tools in Haskell

[1] Boolean algebra whose association structure a residuierter Association 's (English: residuated algebra ), see: Marcel Erné: Algebraic lattice theory , Department of Algebra, Number Theory and Discrete Mathematics, University of Hannover

[2] Alfred Tarski (1948) "Abstract: Representation Problems for Relation Algebras," Bulletin of the AMS 54: 80.

[3] Chris Brink et al. page 12

[4] According to Robin Hirsch, Ian Hodkinson: Relation algebras page 7, on: Third Indian Conference on Logic and its Applications (ICLA), 7. – 11. January 2009, Chennai, India. The tuple has been adjusted to the above definition.

[5] Of the links (one-digit) and (two-digit) - strictly speaking - the restrictions on or are meant. ${\ displaystyle {} ^ {^ {-}}, {} ^ {\ smile}}$ ${\ displaystyle \ cap, \ cup, \ circ}$ ${\ displaystyle A}$ ${\ displaystyle A ^ {2}}$