imported>SchlurcherBot: Bot: http → https

2025-10-18T10:57:24Z

Bot: http → https

Neue Seite

{{Dieser Artikel |behandelt den Begriff aus der Theorie der Booleschen Algebren. Zum ähnlich lautenden Begriff aus der Theorie der Datenbanken siehe [[Relationale Algebra]].}}

In der [[Mathematik]] und [[Abstrakte Algebra|abstrakten Algebra]] ist eine '''Relationsalgebra''' (englisch: ''relation algebra'') eine [[residuierte Boolesche Algebra]],<ref>eine [[Boolesche Algebra]], deren [[Verband (Mathematik)|Verbandsstruktur]] ein [[residuierter Verband]] ist (englisch: ''residuated Algebra''), siehe: Marcel Erné: [http://www2.iazd.uni-hannover.de/~erne/OrdVerb/AlgVerbandstheorie.pdf Algebraische Verbandstheorie], Institut für Algebra, Zahlentheorie und Diskrete Mathematik, Leibniz Universität Hannover</ref> die um eine [[Involution (Mathematik)|Involution]] (als einstellige [[Verknüpfung (Mathematik)|Operation]]), genannt ''Konverse'', erweitert wurde. Das für diese Begriffsbildung maßgebliche Beispiel einer Relationsalgebra ist die Algebra <math>2^{A^2} = \mathcal P(A \times A)</math> aller [[Relation (Mathematik)#Homogene Relationen|zweistelligen Relationen]] auf einer Menge <math>A</math> (d. h. auf den Teilmengen des kartesischen Produkts <math>A \times A = A^2</math>), zusammen mit der Verkettung von Relationen und der Umkehrrelation (konversen Relation).

== Definition ==

Die folgenden Axiome sind angelehnt an Givant (2006, Seite 283) und wurden zuerst 1948 von [[Alfred Tarski]] aufgestellt.<ref>[[Alfred Tarski]] (1948) "Abstract: Representation Problems for Relation Algebras," ''Bulletin of the AMS'' 54: 80.</ref>

Eine Relationsalgebra ist ein 9-[[Tupel]] <math>(L,\land,\lor,\neg,0,1,\circ,\mathrm I,{}^\smile)</math>, für das gilt:
*<math>(L,\land,\lor,\neg,0,1)</math> ist eine Boolesche Algebra mit Konjunktion <math>\land</math>, Disjunktion <math>\lor</math> und Negation <math>\neg</math> sowie Nullelement <math>0</math> und Einselement <math>1</math>:
*<math>(L,\circ,\mathrm I)</math> ist ein [[Monoid]] mit einem eigenen Einselement <math>\mathrm I</math>,
*<math>{}^\smile</math> ist eine [[Involution (Mathematik)|Involution]], genannt ''Konverse'',
*<math>\forall a,b\in{L}: (a \circ b)^\smile = b^\smile \circ a^\smile</math>, d. h. die Konverse ist gegenüber der Verknüpfung <math>\circ</math> treu,
*<math>\forall a,b\in{L}: (a \lor b )^\smile = a^\smile \lor b^\smile</math>,
*<math>\forall a,b,c\in{L}: (a \lor b)\circ{c} = (a\circ{c}) \lor (b\circ{c})</math> ([[Distributivgesetz|Distributivität]]) und
*<math>\forall a,b\in{L}: (a^\smile \circ \neg(a\circ{b})) \lor \neg{b} = \neg{b}</math>, was nichts anderes bedeutet als <math>a\circ{b} \le \neg{c} \Leftrightarrow a^\smile \circ c \le \neg{b} \Leftrightarrow c \circ b^\smile \le \neg{a}</math> (Peircesches Gesetz).<ref>Chris Brink et al. Seite 12</ref> [[Datei:Vetorial space P.GIF|mini|200px|Veranschaulichung zum Peirceschen Gesetz, hier mit ''u, v, w'' statt ''a, b, c'']]
:

== Beispiel ==

Die homogenen zweistelligen Relationen <math>R \subseteq A \times A</math> bilden die Relationsalgebra
:<math>\mathfrak{Re}(A) = (2^{A^2},\cap,\cup,{}^{^-},\empty,A^2, \circ, \mathrm I_A, {}^\smile)</math> <ref>Nach Robin Hirsch, Ian Hodkinson: [http://ali.cmi.ac.in/icla2009/slides/jan07/alogic/0900.pdf 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.</ref><br />
<small>unter Verwendung der Notationen <math>A^2 = A \times A,\ \;\ 2^{A^2} = \mathcal P(A \times A)</math>.</small><ref>Von den Verknüpfungen <math>{}^{^-},{}^\smile</math> (einstellig), sowie <math>\cap,\cup,\circ</math> (zweistellig) sind - genau genommen - die Einschränkungen auf <math>A</math> bzw. <math>A^2</math> gemeint.</ref>

== Peirce-Algebra ==

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

== Siehe auch ==
* [[Boolesche Algebra]]
* [[Heyting-Algebra]]

== Einzelnachweise und Bemerkungen ==

<references />

== Literatur ==

* [[Rudolf Carnap]]: ''Introduction to Symbolic Logic and its Applications.'' Dover Publications, 1958.
* {{Literatur |Autor=Steven Givant |Titel=The calculus of relations as a foundation for mathematics |Sammelwerk=Journal of Automated Reasoning |Band=Band 37 |Datum=2006 |Seiten=277–322 |DOI=10.1007/s10817-006-9062-x}}
* [[Paul Richard Halmos|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: ''[https://www.elsevier.com/wps/find/bookdescription.cws_home/625473/description#description Relation Algebra by Games].'' (= ''Studies in Logic and the Foundations of Mathematics''. vol. 147). Elsevier Science, 2002, ISBN 0-444-50932-1.
* {{Literatur |Autor=Bjarni Jónsson, Constantine Tsinakis |Titel=Relation algebras as residuated Boolean algebras |Sammelwerk=Algebra Universalis |Band=30 |Datum=1993 |Seiten=469–478 |DOI=10.1007/BF01195378}}
* {{Literatur |Autor=Roger Maddux |Titel=The Origin of Relation Algebras in the Development and Axiomatization of the Calculus of Relations |Sammelwerk=Studia Logica |Band=50 |Nummer=3–4 |Datum=1991 |Seiten=421–455 |Online=https://orion.math.iastate.edu/maddux/papers/Maddux1991.pdf |DOI=10.1007/BF00370681}}
* 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 (Mathematiker)|Gunther Schmidt]]: ''Relational Mathematics.'' Cambridge University Press, 2010.
* {{Literatur |Autor=Alfred Tarski |Titel=On the calculus of relations |Sammelwerk=Journal of Symbolic Logic |Band=6 |Datum=1941 |Seiten=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 ==

* [https://mathepedia.de/Relationenalgebra.html Relationsalgebra] (Mathepedia) (deutsch)
* Yohji Akama, Yasuo Kawahara, Hitoshi Furusawa: [https://web.archive.org/web/19980713070139/http://nicosia.is.s.u-tokyo.ac.jp/pub/staff/akama/repr.ps Constructing Allegory from Relation Algebra and Representation Theorems]" (WayBack)
* Richard Bird, Oege de Moor, Paul Hoogendijk: [https://www.cs.ox.ac.uk/richard.bird/online/BirdHoogendijkDeMoor1996Generic.pdf Generic Programming with Relations and Functors]
* R.P. de Freitas, J.P. Viana: [https://www.sciencedirect.com/science/article/pii/S1571066104805498 A Completeness Result for Relation Algebra with Binders]
* Chris Brink, Katarina Britz, Renate A. Schmidt: [https://link.springer.com/chapter/10.1007/978-1-4471-3227-1_15 Peirce Algebras]

* [http://www1.chapman.edu/~jipsen/ Peter Jipsen]:
** [https://web.archive.org/web/20110614180042/http://math.chapman.edu/structuresold/files/Relation_algebras.pdf Relation algebras] (WayBack)
** [https://math.chapman.edu/~jipsen/talks/RelMiCS2006/JipsenRAKAtutorial.pdf Foundations of Relations and Kleene Algebra]
** [https://www1.chapman.edu/~jipsen/dissertation/ Computer Aided Investigations of Relation Algebras]
** [https://www1.chapman.edu/~jipsen/reslat/gentzenrl.pdf A Gentzen System And Decidability For Residuated Lattices]

*[http://boole.stanford.edu/pratt.html Vaughan Pratt]:
** [http://boole.stanford.edu/pub/ocbr.pdf Origins of the Calculus of Binary Relations.]
** [http://boole.stanford.edu/pub/scbr.pdf The Second Calculus of Binary Relations.]

* [http://www.upriss.org.uk/ Uta Priss]:
** [https://www.upriss.org.uk/papers/fcaic06.pdf An FCA interpretation of Relation Algebra]
** [http://www.upriss.org.uk/fca/relalg.html Relation Algebra and FCA]

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

[[Kategorie:Boolesche Algebra| ]]
[[Kategorie:Algebra]]
[[Kategorie:Algebraische Struktur|!]]

[[en:Relation Algebra]]

Relationsalgebra - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https