Relationsalgebra

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

Definitionen

Identität

Wir bezeichnen mit I:={(a,a)aA}\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 \OO bezeichnen wir die leere Relation und mit 1:=A×A\bm 1:=A\cross A, die Relation bei der alle Elemente miteinander in Beziehung stehen.
 
 

Transponierte Relation

Sei RA×AR\subseteq A\cross A eine binäre Relation. Wir bezeichnen mit RT=R1R^T=R^\me die inverse Relation oder transponierte Relation genau wenn gilt
(b,a)RT        (a,b)R(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 RR und SS binäre Relationen auf AA, so ist auch
RS={(a,c):bA:(a,b)RR\circ S=\{(a,c): \exist b\in A: (a,b)\in R und (b,c)S}(b,c)\in S\}
eine binäre Relation. Sie heißt die Komposition oder das Relationenprodukt von RR und SS. Bei dieser Schreibweise ist die Reihenfolge genau umgekehrt zu der bei der Hintereinanderausführung von Abbildungen ist.
In Anlehnung an die Potenzschreibweise R2=RRR^2=R\circ R und Rn=RRRnfachR^n= \underbrace{R\circ R\circ\dots\circ R}_{n -fach}.

Satz 9ANA (Rechenregeln der Relationsalgebra)

  1. RTT=RR^{TT}=R
  2. Q(RS)=(QR)SQ\circ (R\circ S)=(Q\circ R)\circ S (Assoziativität des Relationenproduktes)
  3. IR=RI=R\I\circ R=R\circ \I=R (I\I ist neutrales Element des Relationenproduktes)
  4. (RS)T=STRT(R\circ S)^T=S^T\circ R^T

Beweis

(i): (a,b)RTT(a,b)\in R^{TT}     (b,a)RT \iff (b,a)\in R^T     (a,b)R \iff (a,b) \in R (ii): (a,b)Q(RS)(a,b)\in Q\circ (R\circ S)     c:(a,c)Q(c,b)RS\iff \exists c: (a,c)\in Q\and (c,b)\in R\circ S     c,d:(a,c)Q(c,d)R(d,b)S\iff \exists c,d: (a,c)\in Q\and (c,d)\in R \and (d,b)\in S     d:(a,d)QR(d,b)S\iff \exists d: (a,d)\in Q\circ R \and (d,b)\in S     (a,b)(QR)S\iff (a,b)\in (Q\circ R)\circ S. (iii): (a,b)IR(a,b)\in \I\circ R     c:(a,c)I(c,b)R\iff \exists c: (a,c)\in I\and (c,b)\in R, also a=ca=c und damit     (a,b)R\iff (a,b)\in R. RI=RR\circ\I=R ebenso.
(iv): (c,a)STRT(c,a)\in S^T\circ R^T     b\iff \exists b mit (c,b)ST (c,b)\in S^T und (b,a)RT(b,a)\in R^T     b\iff \exists b mit (b,c)S(b,c)\in S und (a,b)R(a,b) \in R     (a,c)RS\iff (a,c)\in R\circ S     (c,a)(RS)T\iff (c,a)\in (R\circ S)^T.

Satz 1729 (Algebraische Darstellung der Relationseigenschaften)

Sei RA×AR\subseteq A\cross A eine binäre Relation. Dann gilt:
  1. RR ist reflexiv     IR\iff \, \I\subseteq R,
  2. RR ist irreflexiv     IR=\iff \, \I\cap R=\OO,
  3. RR ist symmetrisch     R=RT\iff \, R=R^T,
  4. RR ist asymmetrisch     RRT=\iff \, R\cap R^T=\OO,
  5. RR ist antisymmetrisch     RRTI\iff \, R\cap R^T\subseteq \I,
  6. RR ist transitiv     RRR\iff \, R\circ R\subseteq R, also R2RR^2\subseteq R .

Beweis

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

Jede Wissenschaft bedarf der Mathematik, die Mathematik bedarf keiner.

Jakob I. Bernoulli

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е