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 ${\displaystyle 2^{A^{2}}={\mathcal {P}}(A\times A)}$ aller zweistelligen Relationen auf einer Menge ${\displaystyle A}$ (d. h. auf den Teilmengen des kartesischen Produkts ${\displaystyle A\times A=A^{2}}$), zusammen mit der Verkettung von Relationen und der Umkehrrelation (konversen Relation).

Definition

Die folgenden Axiome s​ind angelehnt a​n Givant (2006, Seite 283), u​nd wurden zuerst 1948 v​on Alfred Tarski aufgestellt.[2]

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

• ${\displaystyle (L,\land ,\lor ,\neg ,0,1)}$ ist eine Boolesche Algebra mit Konjunktion ${\displaystyle \land }$, Disjunktion ${\displaystyle \lor }$ und Negation ${\displaystyle \neg }$ sowie Nullelement und Einselement ${\displaystyle 1}$:
• ${\displaystyle (L,\circ ,\mathrm {I} )}$ ist ein Monoid mit einem eigenen Einselement ${\displaystyle \mathrm {I} }$,
• ${\displaystyle {}^{\smile }}$ ist eine Involution, genannt Konverse,
• ${\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,
• ${\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})}$ (Distributivität) und
• ${\displaystyle \forall a,b\in {L}:(a^{\smile }\circ \neg (a\circ {b}))\lor \neg {b}=\neg {b}}$, was nichts anderes bedeutet als ${\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]
  

  Veranschaulichung zum Peirceschen Gesetz, hier mit u, v, w statt a, b, c

Beispiel

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

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

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

Peirce-Algebra

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

Siehe auch

• Boolesche Algebra
• Heyting-Algebra

Einzelnachweise und Bemerkungen

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 ${\displaystyle A}$ bzw. ${\displaystyle A^{2}}$ gemeint.

Literatur

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

Weblinks

• 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