Relationsalgebra

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 ${\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 ${\displaystyle 0}$ 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]

  

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]

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

• Boolesche Algebra
• Heyting-Algebra