Relationsalgebra

In der Mathematik und abstrakten Algebra ist eine Relationsalgebra (englisch: relation algebra) eine residuierte Boolesche Algebra,^[1] die um eine Involution (als einstellige Operation), genannt Konverse, erweitert wurde. Das für diese Begriffsbildung maßgebliche Beispiel einer Relationsalgebra ist die Algebra 2 A 2 = P ( A × A ) {\displaystyle 2^{A^{2}}={\mathcal {P}}(A\times A)} aller zweistelligen Relationen auf einer Menge A {\displaystyle A} (d. h. auf den Teilmengen des kartesischen Produkts A × A = A 2 {\displaystyle A\times A=A^{2}} ), zusammen mit der Verkettung von Relationen und der Umkehrrelation (konversen Relation).

Die folgenden Axiome sind angelehnt an Givant (2006, Seite 283) und wurden zuerst 1948 von Alfred Tarski aufgestellt.^[2]

Eine Relationsalgebra ist ein 9-Tupel ( L , ∧ , ∨ , ¬ , 0 , 1 , ∘ , I , ⌣ ) {\displaystyle (L,\land ,\lor ,\neg ,0,1,\circ ,\mathrm {I} ,{}^{\smile })} , für das gilt:

• ( L , ∧ , ∨ , ¬ , 0 , 1 ) {\displaystyle (L,\land ,\lor ,\neg ,0,1)} ist eine Boolesche Algebra mit Konjunktion ∧ {\displaystyle \land } , Disjunktion ∨ {\displaystyle \lor } und Negation ¬ {\displaystyle \neg } sowie Nullelement 0 {\displaystyle 0} und Einselement 1 {\displaystyle 1} :
• ( L , ∘ , I ) {\displaystyle (L,\circ ,\mathrm {I} )} ist ein Monoid mit einem eigenen Einselement I {\displaystyle \mathrm {I} } ,
• ⌣ {\displaystyle {}^{\smile }} ist eine Involution, genannt Konverse,
• ∀ a , b ∈ L : ( a ∘ b ) ⌣ = b ⌣ ∘ a ⌣ {\displaystyle \forall a,b\in {L}:(a\circ b)^{\smile }=b^{\smile }\circ a^{\smile }} , d. h. die Konverse ist gegenüber der Verknüpfung ∘ {\displaystyle \circ } treu,
• ∀ a , b ∈ L : ( a ∨ b ) ⌣ = a ⌣ ∨ b ⌣ {\displaystyle \forall a,b\in {L}:(a\lor b)^{\smile }=a^{\smile }\lor b^{\smile }} ,
• ∀ a , b , c ∈ L : ( a ∨ b ) ∘ c = ( a ∘ c ) ∨ ( b ∘ c ) {\displaystyle \forall a,b,c\in {L}:(a\lor b)\circ {c}=(a\circ {c})\lor (b\circ {c})} (Distributivität) und
• ∀ a , b ∈ L : ( a ⌣ ∘ ¬ ( a ∘ b ) ) ∨ ¬ b = ¬ b {\displaystyle \forall a,b\in {L}:(a^{\smile }\circ \neg (a\circ {b}))\lor \neg {b}=\neg {b}} , was nichts anderes bedeutet als a ∘ b ≤ ¬ c ⇔ a ⌣ ∘ c ≤ ¬ b ⇔ c ∘ b ⌣ ≤ ¬ a {\displaystyle a\circ {b}\leq \neg {c}\Leftrightarrow a^{\smile }\circ c\leq \neg {b}\Leftrightarrow c\circ b^{\smile }\leq \neg {a}} (Peircesches Gesetz).^[3]

  

Die homogenen zweistelligen Relationen R ⊆ A × A {\displaystyle R\subseteq A\times A} bilden die Relationsalgebra

R e ( A ) = ( 2 A 2 , ∩ , ∪ , − , ∅ , A 2 , ∘ , I A , ⌣ ) {\displaystyle {\mathfrak {Re}}(A)=(2^{A^{2}},\cap ,\cup ,{}^{^{-}},\emptyset ,A^{2},\circ ,\mathrm {I} _{A},{}^{\smile })}  ^[4]

unter Verwendung der Notationen A 2 = A × A ,     2 A 2 = P ( A × A ) {\displaystyle A^{2}=A\times A,\ \;\ 2^{A^{2}}={\mathcal {P}}(A\times A)} .^[5]

• Eine Weiterentwicklung davon ist die (heterogene) Peirce-Algebra, benannt nach Charles Sanders Peirce – eine abstrakte Beschreibung der Relationsalgebra R e ( A ) {\displaystyle {\mathfrak {Re}}(A)} der homogenen zweistelligen Relationen zusammen mit Vor-/Nachbeschränkungen auf Mengen.

• Boolesche Algebra
• Heyting-Algebra

1. ↑ eine Boolesche Algebra, deren Verbandsstruktur ein residuierter Verband ist (englisch: residuated Algebra), siehe: Marcel Erné: Algebraische Verbandstheorie, Institut für Algebra, Zahlentheorie und Diskrete Mathematik, Leibniz Universität Hannover
2. ↑ Alfred Tarski (1948) "Abstract: Representation Problems for Relation Algebras," Bulletin of the AMS 54: 80.
3. ↑ Chris Brink et al. Seite 12
4. ↑ Nach Robin Hirsch, Ian Hodkinson: Relation algebras Seite 7, auf: Third Indian Conference on Logic and its Applications (ICLA), 7.–11. Januar 2009, Chennai, India. Das Tupel wurde an die obige Definition angeglichen.
5. ↑ Von den Verknüpfungen − , ⌣ {\displaystyle {}^{^{-}},{}^{\smile }} (einstellig), sowie ∩ , ∪ , ∘ {\displaystyle \cap ,\cup ,\circ } (zweistellig) sind - genau genommen - die Einschränkungen auf A {\displaystyle A} bzw. A 2 {\displaystyle A^{2}} gemeint.

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

• Relationsalgebra (Mathepedia) (deutsch)
• 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
• R.P. de Freitas, J.P. Viana: A Completeness Result for Relation Algebra with Binders
• Chris Brink, Katarina Britz, Renate A. Schmidt: Peirce Algebras

• Peter Jipsen:
  • Relation algebras (WayBack)
  • 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.
  • 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