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}}={\mathcal {P}}(A\times A)$ aller zweistelligen Relationen auf einer Menge $A$ (d. h. auf den Teilmengen des kartesischen Produkts $A\times A=A^{2}$ ), 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.^[2]

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

$(L,\land ,\lor ,\neg ,0,1)$ ist eine Boolesche Algebra mit Konjunktion $\land$ , Disjunktion $\lor$ und Negation $\neg$ sowie Nullelement $0$ und Einselement $1$ :
$(L,\circ ,\mathrm {I} )$ ist ein Monoid mit einem eigenen Einselement $\mathrm {I}$ ,
${}^{\smile }$ ist eine Involution, genannt Konverse,
$\forall a,b\in {L}:(a\circ b)^{\smile }=b^{\smile }\circ a^{\smile }$ , d. h. die Konverse ist gegenüber der Verknüpfung $\circ$ treu,
$\forall a,b\in {L}:(a\lor b)^{\smile }=a^{\smile }\lor b^{\smile }$ ,
$\forall a,b,c\in {L}:(a\lor b)\circ {c}=(a\circ {c})\lor (b\circ {c})$ (Distributivität) und
$\forall a,b\in {L}:(a^{\smile }\circ \neg (a\circ {b}))\lor \neg {b}=\neg {b}$ , was nichts anderes bedeutet als $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 $R\subseteq A\times A$ bilden die Relationsalgebra

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

^[4]

unter Verwendung der Notationen $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 ${\mathfrak {Re}}(A)$ der homogenen zweistelligen Relationen zusammen mit Vor-/Nachbeschränkungen auf Mengen.

Siehe auch

Einzelnachweise und Bemerkungen

↑ 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
↑ Alfred Tarski (1948) "Abstract: Representation Problems for Relation Algebras," Bulletin of the AMS 54: 80.
↑ Chris Brink et al. Seite 12
↑ 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.
↑ Von den Verknüpfungen ${}^{^{-}},{}^{\smile }$ (einstellig), sowie $\cap ,\cup ,\circ$ (zweistellig) sind - genau genommen - die Einschränkungen auf $A$ bzw. $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:

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] 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 ${}^{^{-}},{}^{\smile }$ (einstellig), sowie $\cap ,\cup ,\circ$ (zweistellig) sind - genau genommen - die Einschränkungen auf $A$ bzw. $A^{2}$ gemeint.

[1]

[2]

[3]

[4]

[5]