In der Mathematik und abstrakten Algebra ist eine Relationsalgebra (englisch: relation algebra) eine residuierte Boolesche Algebra,<ref>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</ref> die um eine Involution (als einstellige 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 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, 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> (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.GIFVeranschaulichung 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: 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>
unter Verwendung der Notationen <math>A^2 = A \times A,\ \;\ 2^{A^2} = \mathcal P(A \times A)</math>.<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) 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.
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. Band37, 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.
Roger Maddux: The Origin of Relation Algebras in the Development and Axiomatization of the Calculus of Relations. In: Studia Logica. Band50, 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. Band6, 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.
