Relationsalgebra

Man kann die Eigenschaften von binären Relationen rein mengentheoretisch charakterisieren.

Definitionen

Identität

Wir bezeichnen mit \(\displaystyle \I:=\{(a,a)|a\in A\}\) die identische Relation oder Identität. Da in einer Matrixdarstellung nur die Hauptdiagonale besetzt ist, spricht man auch von eine Diagonalrelation.Mit \(\displaystyle \OO\) bezeichnen wir die leere Relation und mit \(\displaystyle \bm 1:=A\cross A\), die Relation bei der alle Elemente miteinander in Beziehung stehen.
 
 

Transponierte Relation

Sei \(\displaystyle R\subseteq A\cross A\) eine binäre Relation. Wir bezeichnen mit \(\displaystyle R^T=R^\me\) die inverse Relation oder transponierte Relation genau wenn gilt
\(\displaystyle (b,a)\in R^T\;\iff\;(a,b)\in R\).
Die Bezeichnung transponierte Relation rührt daher, dass ihre Matrixdarstellung genau der transponierten Matrix entspricht.

Relationenprodukt

Sind \(\displaystyle R\) und \(\displaystyle S\) binäre Relationen auf \(\displaystyle A\), so ist auch
\(\displaystyle R\circ S=\{(a,c): \exist b\in A: (a,b)\in R \) und \(\displaystyle (b,c)\in S\}\)
eine binäre Relation. Sie heißt die Komposition oder das Relationenprodukt von \(\displaystyle R\) und \(\displaystyle S\). Bei dieser Schreibweise ist die Reihenfolge genau umgekehrt zu der bei der Hintereinanderausführung von Abbildungen ist.
In Anlehnung an die Potenzschreibweise \(\displaystyle R^2=R\circ R\) und \(\displaystyle R^n= \underbrace{R\circ R\circ\dots\circ R}_{n -fach}\).

Satz 9ANA (Rechenregeln der Relationsalgebra)

  1. \(\displaystyle R^{TT}=R\)
  2. \(\displaystyle Q\circ (R\circ S)=(Q\circ R)\circ S\) (Assoziativität des Relationenproduktes)
  3. \(\displaystyle \I\circ R=R\circ \I=R\) (\(\displaystyle \I\) ist neutrales Element des Relationenproduktes)
  4. \(\displaystyle (R\circ S)^T=S^T\circ R^T\)

Beweis

(i): \(\displaystyle (a,b)\in R^{TT}\) \(\displaystyle \iff (b,a)\in R^T\) \(\displaystyle \iff (a,b) \in R\) (ii): \(\displaystyle (a,b)\in Q\circ (R\circ S)\) \(\displaystyle \iff \exists c: (a,c)\in Q\and (c,b)\in R\circ S\) \(\displaystyle \iff \exists c,d: (a,c)\in Q\and (c,d)\in R \and (d,b)\in S\) \(\displaystyle \iff \exists d: (a,d)\in Q\circ R \and (d,b)\in S\) \(\displaystyle \iff (a,b)\in (Q\circ R)\circ S\). (iii): \(\displaystyle (a,b)\in \I\circ R\) \(\displaystyle \iff \exists c: (a,c)\in I\and (c,b)\in R\), also \(\displaystyle a=c\) und damit \(\displaystyle \iff (a,b)\in R\). \(\displaystyle R\circ\I=R\) ebenso.
(iv): \(\displaystyle (c,a)\in S^T\circ R^T\) \(\displaystyle \iff \exists b\) mit \(\displaystyle (c,b)\in S^T \) und \(\displaystyle (b,a)\in R^T\) \(\displaystyle \iff \exists b\) mit \(\displaystyle (b,c)\in S\) und \(\displaystyle (a,b) \in R\) \(\displaystyle \iff (a,c)\in R\circ S\) \(\displaystyle \iff (c,a)\in (R\circ S)^T\).

Satz 1729 (Algebraische Darstellung der Relationseigenschaften)

Sei \(\displaystyle R\subseteq A\cross A\) eine binäre Relation. Dann gilt:
  1. \(\displaystyle R\) ist reflexiv \(\displaystyle \iff \, \I\subseteq R\),
  2. \(\displaystyle R\) ist irreflexiv \(\displaystyle \iff \, \I\cap R=\OO\),
  3. \(\displaystyle R\) ist symmetrisch \(\displaystyle \iff \, R=R^T\),
  4. \(\displaystyle R\) ist asymmetrisch \(\displaystyle \iff \, R\cap R^T=\OO\),
  5. \(\displaystyle R\) ist antisymmetrisch \(\displaystyle \iff \, R\cap R^T\subseteq \I\),
  6. \(\displaystyle R\) ist transitiv \(\displaystyle \iff \, R\circ R\subseteq R\), also \(\displaystyle R^2\subseteq R\) .

Beweis

(i) \(\displaystyle R\) reflexiv \(\displaystyle \iff\) \(\displaystyle \forall a\in A\): \(\displaystyle (a,a)\in R\) \(\displaystyle \iff\) \(\displaystyle \I\subseteq R\).(ii) "\(\displaystyle \implies\)": \(\displaystyle R\) irreflexiv bedeutet es gibt kein \(\displaystyle (a,a)\in R\), aus diesen Paaren besteht aber genau \(\displaystyle \I\), also \(\displaystyle \I\cap R=\OO\)."\(\displaystyle \Leftarrow\)" (indirekt): Sei nun \(\displaystyle \I\cap R=\OO\) und \(\displaystyle R\) nicht irreflexiv, also gibt es ein \(\displaystyle (a,a)\in R\) für dies gilt natürlich auch \(\displaystyle (a,a)\in I\), also \(\displaystyle \I\cap R\neq\OO\). Widerspruch, damit ist \(\displaystyle R\) irreflexiv. (iii) \(\displaystyle R\) symmetrisch \(\displaystyle \iff\) \(\displaystyle \forall a,b\in A\): \(\displaystyle (a,b)\in R\iff (b,a)\in R\) \(\displaystyle \iff\) \(\displaystyle \forall a,b\in A\): \(\displaystyle (a,b)\in R\iff (a,b)\in R^T\) \(\displaystyle \iff\) \(\displaystyle R=R^T\).(iv) "\(\displaystyle \implies\)" (indirekt): \(\displaystyle R\) asymmetrisch und \(\displaystyle R\cap R^T\neq\OO\), also gibt es ein \(\displaystyle (a,b)\) mit \(\displaystyle (a,b)\in\R\) und \(\displaystyle (a,b)\in R^T\), also \(\displaystyle (b,a)\in R\), Widerspruch. "\(\displaystyle \Leftarrow\)" (indirekt): Sei \(\displaystyle R\cap R^T=\OO\) und \(\displaystyle R\) nicht asymmetrisch, dann gibt es ein \(\displaystyle (a,b)\) mit \(\displaystyle (a,b)\in R\) und \(\displaystyle (b,a)\in R\), also \(\displaystyle (a,b)\in R^T\) und \(\displaystyle R\cap R^T\neq\OO\). Widerspruch.
(v) Mit \(\displaystyle a=b\iff (a,b)\in I\) erhalten wir:\(\displaystyle R\) antisymmetrisch\(\displaystyle \iff\) \(\displaystyle \forall (a,b): (a,b)\in R \and (b,a)\in R\implies a=b\)\(\displaystyle \iff\) \(\displaystyle \forall (a,b): (a,b)\in R \and (a,b)\in R^T\implies a=b\) \(\displaystyle \iff\) \(\displaystyle \forall (a,b): (a,b)\in R\cap R^T\implies a=b\) \(\displaystyle \iff\) \(\displaystyle R\cap R^T\subseteq I\).
(vi) "\(\displaystyle \implies\)": \(\displaystyle R\) sei transitiv und \(\displaystyle (a,c)\in R\circ R\). Nach Definition gibt es \(\displaystyle b\in R\) mit \(\displaystyle (a,b)\in R\) und \(\displaystyle (b,c)\in R\), da \(\displaystyle R\) transitiv ist also \(\displaystyle (a,c)\in R\) und damit \(\displaystyle R\circ R\subseteq R\) "\(\displaystyle \Leftarrow\)": Sei \(\displaystyle R\circ R\subseteq R\) und \(\displaystyle (a,b)\in R\) und \(\displaystyle (b,c)\in R\), dann ist \(\displaystyle (a,c)\in R\circ R\subseteq R\), also \(\displaystyle R\) transitiv. \(\displaystyle \qed\)

Es ist unmöglich, die Schönheiten der Naturgesetze angemessen zu vermitteln, wenn jemand die Mathematik nicht versteht. Ich bedaure das, aber es ist wohl so.

Richard Feynman

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе