Relationsalgebra
# Relationsalgebra

In der Mathematik und abstrakten Algebra ist eine Relationsalgebra (englisch: relation algebra) eine residuierte Boolesche Algebra, 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.

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). 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 })$

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

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