Relationsalgebra

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

Definitionen

Identität

Wir bezeichnen mit I⁡:={(a,a)∣a∈A}\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 R⊆A×AR\subseteq A\cross A eine binäre Relation. Wir bezeichnen mit RT=R−1R^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
R∘S={(a,c):∃b∈A:(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=R∘RR^2=R\circ R und Rn=R∘R∘⋯∘R⎵n−fachR^n= \underbrace{R\circ R\circ\dots\circ R}_{n -fach}.

Satz 9ANA (Rechenregeln der Relationsalgebra)

  1. RTT=RR^{TT}=R
  2. Q∘(R∘S)=(Q∘R)∘SQ\circ (R\circ S)=(Q\circ R)\circ S (Assoziativität des Relationenproduktes)
  3. I⁡∘R=R∘I⁡=R\I\circ R=R\circ \I=R (I⁡\I ist neutrales Element des Relationenproduktes)
  4. (R∘S)T=ST∘RT(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∘(R∘S)(a,b)\in Q\circ (R\circ S)   ⟺  ∃c:(a,c)∈Q∧(c,b)∈R∘S\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)∈Q∘R∧(d,b)∈S\iff \exists d: (a,d)\in Q\circ R \and (d,b)\in S   ⟺  (a,b)∈(Q∘R)∘S\iff (a,b)\in (Q\circ R)\circ S. (iii): (a,b)∈I⁡∘R(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. R∘I⁡=RR\circ\I=R ebenso.
(iv): (c,a)∈ST∘RT(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)∈R∘S\iff (a,c)\in R\circ S   ⟺  (c,a)∈(R∘S)T\iff (c,a)\in (R\circ S)^T.

Satz 1729 (Algebraische Darstellung der Relationseigenschaften)

Sei R⊆A×AR\subseteq A\cross A eine binäre Relation. Dann gilt:
  1. RR ist reflexiv   ⟺   I⁡⊆R\iff \, \I\subseteq R,
  2. RR ist irreflexiv   ⟺   I⁡∩R=∅\iff \, \I\cap R=\OO,
  3. RR ist symmetrisch   ⟺   R=RT\iff \, R=R^T,
  4. RR ist asymmetrisch   ⟺   R∩RT=∅\iff \, R\cap R^T=\OO,
  5. RR ist antisymmetrisch   ⟺   R∩RT⊆I⁡\iff \, R\cap R^T\subseteq \I,
  6. RR ist transitiv   ⟺   R∘R⊆R\iff \, R\circ R\subseteq R, also R2⊆RR^2\subseteq R .

Beweis

(i) RR reflexiv   ⟺  \iff ∀a∈A\forall a\in A: (a,a)∈R(a,a)\in R   ⟺  \iff I⁡⊆R\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 I⁡∩R=∅\I\cap R=\OO. "⇐\Leftarrow" (indirekt): Sei nun I⁡∩R=∅\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 I⁡∩R≠∅\I\cap R\neq\OO. Widerspruch, damit ist RR irreflexiv. (iii) RR symmetrisch   ⟺  \iff ∀a,b∈A\forall a,b\in A: (a,b)∈R  ⟺  (b,a)∈R(a,b)\in R\iff (b,a)\in R   ⟺  \iff ∀a,b∈A\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 R∩RT≠∅R\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 R∩RT=∅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 R∩RT≠∅R\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)∈R∩RT  ⟹  a=b\forall (a,b): (a,b)\in R\cap R^T\implies a=b   ⟺  \iff R∩RT⊆I R\cap R^T\subseteq I.
(vi) "  ⟹  \implies": RR sei transitiv und (a,c)∈R∘R(a,c)\in R\circ R. Nach Definition gibt es b∈Rb\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 R∘R⊆RR\circ R\subseteq R "⇐\Leftarrow": Sei R∘R⊆RR\circ R\subseteq R und (a,b)∈R(a,b)\in R und (b,c)∈R(b,c)\in R, dann ist (a,c)∈R∘R⊆R(a,c)\in R\circ R\subseteq R, also RR transitiv. □\qed

Seit der Zeit der Griechen bedeutet "Mathematik" zu sagen, "Beweis" zu sagen.

N. Bourbaki

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е
Datenschutzerklärung

 

Mengenlehre