Zusammensetzung der Beziehungen - Composition of relations

In der Mathematik von binären Beziehungen , die Zusammensetzung der Beziehungen ist die Bildung einer neuen binäre Relation R  ; S aus zwei gegebenen binären Relationen R und S . In der Relationsrechnung wird die Zusammensetzung von Relationen als relative Multiplikation bezeichnet und ihr Ergebnis als relatives Produkt . Funktionskomposition ist der Spezialfall der Komposition von Relationen, bei dem alle beteiligten Relationen Funktionen sind .

Die Wörter Onkel und Tante weisen auf eine zusammengesetzte Beziehung hin: Damit eine Person Onkel sein kann, muss sie ein Bruder eines Elternteils (oder eine Schwester für eine Tante) sein. In der algebraischen Logik heißt es, dass die Relation des Onkels ( xUz ) die Zusammensetzung der Relationen "ist ein Bruder von" ( xBy ) und "ist ein Elternteil von" ( yPz ) ist.

${\displaystyle U=BP\quad\equiv\quad xByPz\iff xUz.}$

Beginnend mit Augustus De Morgan wurde die traditionelle Form der Schlußfolgerung durch den Syllogismus von relationalen logischen Ausdrücken und deren Zusammensetzung subsumiert.

Definition

Wenn und sind zwei binäre Relationen, dann ist ihre Zusammensetzung die Relation ${\displaystyle R\subseteq X\times Y}$${\displaystyle S\subseteq Y\times Z}$${\displaystyle R;S}$

${\displaystyle R;S=\{(x,z)\in X\times Z\mid\exists y\in Y:(x,y)\in R\land (y,z)\in S\}. }$

Mit anderen Worten, wird durch die Regel definiert, die besagt, ob und nur wenn es ein Element gibt, so dass (dh und ). ${\displaystyle R;S\subseteq X\times Z}$${\displaystyle (x,z)\in R;S}$${\displaystyle y\in Y}$${\displaystyle x\,R\,y\,S\,z}$${\displaystyle (x,y)\in R}$${\displaystyle (y,z)\in S}$

Notationelle Variationen

Das Semikolon als Infix-Notation für die Komposition von Relationen geht auf Ernst Schroders Lehrbuch von 1895 zurück. Gunther Schmidt hat die Verwendung des Semikolons insbesondere in Relational Mathematics (2011) erneuert . Die Verwendung von Semikolon fällt mit der in der Kategorientheorie verwendeten Notation für Funktionskomposition (meist von Informatikern) sowie der Notation für dynamische Konjunktionen innerhalb der linguistisch- dynamischen Semantik zusammen .

Ein kleiner Kreis wurde von John M. Howie in seinen Büchern über Halbgruppen von Beziehungen für die Infix-Notation der Zusammensetzung von Beziehungen verwendet. Der kleine Kreis wird jedoch häufig verwendet, um eine Zusammenstellung von Funktionen darzustellen , die die Textsequenz von der Operationssequenz umkehrt . Der kleine Kreis wurde auf den Einführungsseiten von Graphs and Relations verwendet, bis er zugunsten der Nebeneinanderstellung (keine Infix-Notation) weggelassen wurde. Nebeneinanderstellung wird in der Algebra häufig verwendet, um Multiplikation anzuzeigen, kann also auch relative Multiplikation bedeuten. ${\displaystyle (R\circ S)}$ ${\displaystyle g(f(x))=(g\circ f)(x)}$ ${\displaystyle (RS)}$

Weiterhin können bei der Kreisnotation tiefgestellte Zeichen verwendet werden. Manche Autoren schreiben lieber und bei Bedarf explizit, je nachdem, ob die linke oder die rechte Relation zuerst angewendet wird. Eine weitere in der Informatik anzutreffende Variation ist die Z-Notation : wird verwendet, um die traditionelle (rechte) Komposition zu bezeichnen, aber ⨾ (ein fettes offenes Semikolon mit Unicode-Codepunkt +2A3E ) bezeichnet die linke Komposition. ${\displaystyle \circ _{l}}$${\displaystyle \circ_{r}}$${\displaystyle \circ}$

Die binären Relationen werden manchmal als Morphismen in einer Kategorie Rel angesehen, die die Mengen als Objekte hat. In Rel ist die Zusammensetzung von Morphismen genau die Zusammensetzung von Beziehungen wie oben definiert. Die Kategorie Menge von Mengen ist eine Unterkategorie von Rel , die die gleichen Objekte, aber weniger Morphismen hat. ${\displaystyle R\subseteq X\times Y}$${\displaystyle R\colon X\to Y}$

Eigenschaften

• Die Zusammensetzung der Beziehungen ist assoziativ :${\displaystyle R;(S;T)=(R;S);T.}$
• Die umgekehrte Beziehung von R  ; S ist ( R  ; S ) ^T = S ^T  ; R ^T . Diese Eigenschaft macht die Menge aller binären Beziehungen einer Menge zu einer Halbgruppe mit Involution .
• Die Zusammensetzung von (Teil-)Funktionen (dh Funktionsbeziehungen) ist wiederum eine (Teil-)Funktion.
• Wenn R und S ist injektiv , dann R  ; S ist injektiv, was umgekehrt nur die Injektivität von R impliziert .
• Wenn R und S ist surjektiv , dann R  ; S ist surjektiv, was umgekehrt nur die Surjektivität von S impliziert .
• Die Menge binärer Relationen auf einer Menge X (dh Relationen von X nach X ) bildet zusammen mit (links oder rechts) Relationskomposition ein Monoid mit Null, wobei die Identitätsabbildung auf X das neutrale Element ist und die leere Menge die Null ist Element .

Zusammensetzung in Bezug auf Matrizen

Endliche binäre Beziehungen werden durch logische Matrizen dargestellt . Die Einträge dieser Matrizen sind entweder null oder eins, je nachdem, ob die dargestellte Beziehung für die Zeile und Spalte, die den verglichenen Objekten entsprechen, falsch oder wahr ist. Das Arbeiten mit solchen Matrizen erfordert die Boolesche Arithmetik mit 1 + 1 = 1 und 1 × 1 = 1. Ein Eintrag in das Matrixprodukt zweier logischer Matrizen ist dann 1, nur wenn die multiplizierte Zeile und Spalte eine entsprechende 1 haben die logische Matrix einer Zusammensetzung von Beziehungen kann durch Berechnen des Matrixprodukts der Matrizen gefunden werden, die die Faktoren der Zusammensetzung darstellen. "Matrizen stellen eine Methode zur Berechnung der Schlussfolgerungen dar, die traditionell mittels hypothetischer Syllogismen und Soriten gezogen werden."

Heterogene Beziehungen

Betrachten Sie eine heterogene Beziehung R ⊆ A × B ; dh wobei A und B unterschiedliche Mengen sind. Unter Verwendung der Zusammensetzung der Relation R mit ihrer Umkehrung R ^T gibt es dann homogene Relationen RR ^T (auf A ) und R ^T R (auf B ).

Ist ∀ x ∈ A ∃ y ∈ B xRy (also R eine (links-)totale Relation ), dann ist ∀ x xRR ^T x so dass RR ^T eine reflexive Relation ist oder I ⊆ RR ^T wobei I die Identitätsrelation ist { x I x  : x ∈ A }. Wenn R eine surjektive Relation ist, dann gilt

R ^T R ⊇ I = { x I x  : x ∈ B }. In diesem Fall R ⊆ RR ^T R . Der umgekehrte Einschluss tritt für eine difunktionale Beziehung auf.

Die Komposition wird verwendet, um Relationen vom Typ Ferrer zu unterscheiden, die${\displaystyle {\bar {R}}^{\textsf {T}}R}$${\displaystyle R{\bar{R}}^{\textsf {T}}R=R.}$

Beispiel

Seien A = { Frankreich, Deutschland, Italien, Schweiz } und B = { Französisch, Deutsch, Italienisch } mit der durch aRb gegebenen Relation R , wenn b eine Nationalsprache von a ist . Da sowohl A als auch B endlich sind, kann R durch eine logische Matrix dargestellt werden , unter der Annahme, dass Zeilen (von oben nach unten) und Spalten (von links nach rechts) alphabetisch geordnet sind:

${\displaystyle {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\1&1&1\end{pmatrix}}.}$

Die umgekehrte Relation R ^T entspricht der transponierten Matrix , und die Relationszusammensetzung entspricht dem Matrixprodukt, wenn die Summation durch logische Disjunktion implementiert wird . Es stellt sich heraus, dass die 3×3-Matrix an jeder Position eine 1 enthält, während das umgekehrte Matrixprodukt wie folgt berechnet wird: ${\displaystyle R^{\textsf {T}};R}$ ${\displaystyle R^{\textsf {T}}R}$${\displaystyle R^{\textsf {T}}R}$

${\displaystyle RR^{\textsf {T}}={\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\\1&1&1&1\end{pmatrix}}.}$

Diese Matrix ist symmetrisch und repräsentiert eine homogene Beziehung auf A .

Entsprechend ist die universelle Relation auf B , also teilen sich zwei beliebige Sprachen eine Nation, in der beide gesprochen werden (eigentlich: Schweiz). Umgekehrt kann die Frage, ob zwei Nationen eine gemeinsame Sprache haben, mit beantwortet werden . ${\displaystyle R^{\textsf {T}};R}$${\displaystyle R;R^{\textsf {T}}}$

Schröder-Regeln

Für eine gegebene Menge V bildet die Sammlung aller binären Beziehungen auf V ein boolesches Gitter , das nach Inklusion (⊆) geordnet ist . Denken Sie daran, dass die Komplementation die Inklusion umkehrt: In der Relationsrechnung ist es üblich, das Komplement einer Menge durch einen Überstrich darzustellen:${\displaystyle A\subset B\implies B^{\complement}\subset A^{\complement}.}$${\displaystyle {\bar{A}}=A^{\complement}.}$

Wenn S eine binäre Beziehung ist, stellen Sie die umgekehrte Beziehung dar , auch Transponieren genannt . Dann lauten die Schröder-Regeln ${\displaystyle S^{\textsf {T}}}$

${\displaystyle QR\subseteq S\quad \equiv \quad Q^{\textsf {T}}{\bar {S}}\subseteq {\bar {R}}\quad \equiv \quad {\bar {S} }R^{\textsf{T}}\subseteq {\bar{Q}}.}$

Verbal kann eine Äquivalenz von einer anderen erhalten werden: Wählen Sie den ersten oder zweiten Faktor und transponieren Sie ihn; dann ergänzen Sie die beiden anderen Relationen und permutieren sie.

Obwohl diese Transformation einer Einbeziehung einer Relationskomposition von Ernst Schröder detailliert beschrieben wurde , formulierte Augustus De Morgan die Transformation erstmals 1860 als Theorem K. Er schrieb:

${\displaystyle LM\subseteq N\implies {\bar{N}}M^{\textsf {T}}\subseteq {\bar{L}}.}$

Mit Schröder-Regeln und Komplementation kann man nach einer unbekannten Relation X in Relationseinschlüssen auflösen wie

${\displaystyle RX\subseteq S\quad {\text{und}}\quad XR\subseteq S.}$

Zum Beispiel ergibt sich nach Schröder-Regel und Komplementation, was das linke Residuum von S nach R genannt wird . ${\displaystyle RX\subseteq S\implies R^{\textsf {T}}{\bar {S}}\subseteq {\bar {X}},}$${\displaystyle X\subseteq {\overline {R^{\textsf {T}}{\bar {S}}}},}$

Quotienten

So wie die Komposition von Relationen eine Art Multiplikation ist, die zu einem Produkt führt, so vergleichen sich einige Kompositionen mit der Division und erzeugen Quotienten. Hier werden drei Quotienten dargestellt: linkes Residuum, rechtes Residuum und symmetrischer Quotient. Das linke Residuum zweier Relationen wird unter der Annahme definiert, dass sie dieselbe Domäne (Quelle) haben, und das rechte Residuum setzt dieselbe Kodomäne (Bereich, Ziel) voraus. Der symmetrische Quotient geht davon aus, dass zwei Relationen eine Domäne und eine Kodomäne teilen.

Definitionen:

• Rest übrig: ${\displaystyle A\backslash B\mathrel {:=} {\overline {A^{\textsf {T}}{\bar {B}}}}}$
• Rechter Rest: ${\displaystyle D/C\mathrel {:=} {\overline {{\bar {D}}C^{\textsf {T}}}}}}$
• Symmetrischer Quotient: ${\displaystyle \operatorname {syq} (E,F)\mathrel {:=} {\overline {E^{\textsf {T}}{\bar {F}}}}\cap {\overline {{\bar {E}}^{\textsf {T}}F}}}$

Nach den Schröderschen Regeln ist AX ⊆ B äquivalent zu X ⊆ A B . Somit ist das linke Residuum die größte Beziehung, die AX ⊆ B erfüllt . Ähnlich ist die Inklusion YC ⊆ D ist äquivalent zu Y ⊆ D / C , und die rechte Rest ist die größte Beziehung erfüllt YC ⊆ D . ${\displaystyle \backslash }$

On kann die Logik der Residuen mit Sudoku üben .

Join: eine andere Kompositionsform

Ein Gabeloperator (<) wurde eingeführt, um zwei Beziehungen c : H → A und d : H → B zu c (<) d : H → A × B zu verschmelzen . Die Konstruktion hängt von den Projektionen a : A × B → A und b : A × B → B ab , verstanden als Relationen, dh es gibt umgekehrte Relationen a ^T und b ^T . Dann ist die Gabel von c und d gegeben durch

${\displaystyle c(<)d\mathrel {:=} c;a^{\textsf {T}}\cap \ d;b^{\textsf {T}}.}$

Eine andere Form der Relationenzusammenstellung, die für allgemeine n- stellige Relationen für n 2 gilt, ist die Join- Operation der relationalen Algebra . Die übliche Zusammensetzung zweier binärer Relationen, wie sie hier definiert ist, kann erhalten werden, indem man ihre Verknüpfung bildet, die zu einer ternären Relation führt, gefolgt von einer Projektion, die die mittlere Komponente entfernt. In der Abfragesprache SQL gibt es beispielsweise die Operation Join (SQL) .

Siehe auch

• Dämonische Zusammensetzung
• Freund eines Freundes

Anmerkungen

Verweise

• M. Kilp, U. Knauer, AV Mikhalev (2000) Monoids, Acts and Categories with Applications to Wreath Products and Graphs , De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter , ISBN  3-11-015248-7 .