Sammansättning av relationer

I matematiken för binära relationer är sammansättningen av relationer bildandet av en ny binär relation R ; S från två givna binära relationer R och S . I relationskalkylen kallas sammansättningen av relationer relativ multiplikation och dess resultat kallas relativ produkt . Funktionssammansättning är specialfallet av sammansättning av relationer där alla inblandade relationer är funktioner .

Ordet farbror indikerar ett sammansatt förhållande: för att en person ska vara en farbror måste han vara bror till en förälder. I algebraisk logik sägs det att relationen till farbror ( $xUz$ ) är sammansättningen av relationer "är en bror till" ( ${\displaystyle xBy} )$ och "är en förälder till" ( $yPz$ ).

$$U=BP\quad {\text{ motsvarar: }}\quad xByPz{\text{ if and only if }}xUz.$$

Från och med Augustus De Morgan har den traditionella formen av resonemang av syllogism subsumerats av relationella logiska uttryck och deras sammansättning.

Definition

Om $R\subseteq X\times Y$ och $S\subseteq Y\times Z$ är två binära relationer, då är deras sammansättning $R;S$ är relationen

$$R;S=\{(x,z)\i X\ gånger Z:{\text{ det finns }}y\i Y{\text{ så att }}(x,y)\i R{ \text{ och }}(y,z)\i S\}.$$

Med andra ord, $R;S\subseteq X\times Z$ definieras av regeln som säger $(x,z)\in R;S$ om och endast om det finns ett element $y\in Y$ så att $x\,R\, y\,S\,z$ (det vill säga $(x,y)\in R$ och $(y,z)\in S$ ).

Notationsvariationer

Semikolonet som infixnotation för sammansättning av relationer går tillbaka till Ernst Schroders lärobok från 1895. Gunther Schmidt har förnyat användningen av semikolon, särskilt i Relational Mathematics (2011) . Användningen av semikolon sammanfaller med notationen för funktionssammansättning som används (mest av datavetare) i kategoriteorin , samt notationen för dynamisk konjunktion inom språklig dynamisk semantik .

En liten cirkel $(R\circ S)$ har använts för infixet notation av sammansättning av relationer av John M. Howie i hans böcker om semigrupper av relationer. Den lilla cirkeln används dock ofta för att representera sammansättningen av funktioner $g(f(x))=(g\circ f)(x)$ som vänder textsekvensen från operationssekvensen. Den lilla cirkeln användes i de inledande sidorna av Graphs and Relations tills den togs bort till förmån för juxtaposition (ingen infix notation). Juxtaposition $(RS)$ används vanligtvis i algebra för att beteckna multiplikation, så även det kan beteckna relativ multiplikation.

Vidare med cirkelnotationen kan abonnemang användas. Vissa författare föredrar att skriva $\circ _{l}$ och $\circ _{r}$ explicit när det behövs, beroende på om den vänstra eller den högra relationen är den första som tillämpas. En ytterligare variant som påträffas inom datavetenskap är Z-notationen : $\circ$ används för att beteckna den traditionella (höger) kompositionen, men ⨾ ( U+ 2A3E ⨾ Z NOTATION RELATIONELL KOMPOSITION) betecknar vänster komposition.

De binära relationerna $R\subseteq X\times Y$ betraktas ibland som morfismerna $R:X\to Y$ i en kategori Rel som har mängderna som objekt . I Rel är sammansättning av morfismer exakt sammansättning av relationer som definierats ovan. Kategorin Set of sets är en underkategori till Rel som har samma objekt men färre morfismer.

Egenskaper

• Sammansättningen av relationer är associativ : $R;(S;T)=(R;S);T.$
• Det omvända förhållandet av ${\displaystyle R\,;S$${\displaystyle (R\,;S)^{\textsf {T}}=S^{\textsf {T}}\,;R^{\textsf {T}}.} Den här egenskapen gör uppsättningen av alla$ är binära relationer på en uppsättning en halvgrupp med involution .
• Sammansättningen av (partiella) funktioner (det vill säga funktionella relationer) är återigen en (partiell) funktion.
• Om $R$ och $S$ är injektiva , då $R\,;S$ är injektiv, vilket omvänt endast antyder injektiviteten hos $R.$
• Om $R$ och $S$ är surjektiva , då $R\,;S$ är surjektiv, vilket omvänt endast antyder surjektiviteten hos $S.$
• Mängden binära relationer på en mängd $X$ (det vill säga relationer från $X$ till $X$ ) tillsammans med (vänster eller höger) relationssammansättning bildar en monoid med noll, där identitetskartan på $X$ är det neutrala elementet och den tomma mängden är nollelementet .

Sammansättning i termer av matriser

Finita binära relationer representeras av logiska matriser . Inmatningarna i dessa matriser är antingen noll eller ett, beroende på om den representerade relationen är falsk eller sann för raden och kolumnen som motsvarar jämförda objekt. Att arbeta med sådana matriser involverar den booleska aritmetiken med $1+1=1$ och $1\times 1=1.$ En post i matrisprodukten av två logiska matriser blir då 1 endast om raden och kolumnen multiplicerad har motsvarande 1. Den logiska matrisen för en sammansättning av relationer kan således hittas genom att beräkna matrisprodukten av matriserna som representerar kompositionens faktorer. "Matriser utgör en metod för att beräkna de slutsatser som traditionellt dras med hjälp av hypotetiska syllogismer och soriter."

Heterogena relationer

Betrakta ett heterogent samband $R\subseteq A\times B;$ det vill säga där $A$ och $B$ är distinkta mängder. Om man sedan använder sammansättningen av relationen $R$ med dess omvända $R^{\textsf {T}},$ finns det homogena relationer $RR^{\textsf {T}}$ (på $A$ ) och $R^{\textsf {T}}R$ (på $B$ ).

Om det för alla $x\in A$ finns några $y\in B,$ så att $xRy$ (det vill säga $R$ är en (vänster-)total relation ), då för alla $x,xRR^{\textsf {T}}x$ så att $RR^{\textsf { T}}$ är en reflexiv relation eller $I\subseteq RR^{\textsf {T}}$ där I är identitetsrelationen $\{xIx:x\in A\}.$ På liknande sätt, om $R$ är en surjektiv relation då

$$R^{\textsf {T}}R\supseteq I=\{xIx:x\in B\}.$$

I detta fall $R\subseteq RR^{\textsf {T}}R.$ Den motsatta inkluderingen inträffar för en difunktionell relation.

Sammansättningen ${\bar {R}}^{\textsf {T}}R$ används för att urskilja relationer av Ferrers typ, som uppfyller $R{\bar {R}}^{\textsf {T}}R=R.$

Exempel

Låt $A=$ { Frankrike, Tyskland, Italien, Schweiz } och $B=$ { franska, tyska, italienska } med relationen $R$ som ges av ${\ displaystyle aRb}$ när $b$ är ett nationellt språk för $a.$ Eftersom både $A$ och $B$ är ändlig, kan $R$ representeras av en logisk matris , med antagande av rader (uppifrån och ned) och kolumner (vänster till höger) är ordnade i alfabetisk ordning:

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

Den omvända relationen $R^{\textsf {T}}$ motsvarar den transponerade matrisen och relationssammansättningen $R^{\textsf {T}};R$ motsvarar matrisprodukten R $\displaystyle R^{\textsf {T}}R}$ när summering implementeras med logisk disjunktion . Det visar sig att $3\times 3$ -matrisen $R^{\textsf {T}}R$ innehåller en 1 vid varje position, medan den omvända matrisprodukten beräknas som:

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

Denna matris är symmetrisk och representerar en homogen relation på $A.$

På motsvarande sätt, $R^{\textsf {T}}\,;R$ är den universella relationen på $B,$ , alltså delar två språk en nation där de båda talas (i själva verket: Schweiz). Vice versa, frågan om två givna nationer delar ett språk kan besvaras med $R\,;R^{\textsf {T}}.$

Schröder styr

För en given mängd ${\displaystyle V,} bildar$ samlingen av alla binära relationer på $V$ ett booleskt gitter ordnat efter inkludering $(\subseteq ).$ Kom ihåg att komplementering omvänder inkludering: $A\subseteq B{\text{ implies }}B^{\complement }\subseteq A^{\complement }.$ I relationskalkylen är det vanligt att representera komplementet till en mängd med en överstapel: ${\bar {A}}=A^{\komplement }.$

Om $S$ är en binär relation, låt $S^{\textsf {T}}$ representera den omvända relationen , även kallad transponering . Då är Schröderreglerna

$$QR\subseteq S\quad {\text{ motsvarar }}\quad Q^{\textsf {T}}{\bar {S}}\subseteq {\bar {R}}\quad {\text { motsvarar }}\quad {\bar {S}}R^{\textsf {T}}\subseteq {\bar {Q}}.$$

Verbalt kan en ekvivalens erhållas från en annan: välj den första eller andra faktorn och transponera den; komplettera sedan de andra två relationerna och förvandla dem.

Även om denna omvandling av en inkludering av en sammansättning av relationer beskrevs av Ernst Schröder , formulerade faktiskt Augustus De Morgan transformationen först som teorem K 1860. Han skrev

$$LM\subseteq N{\text{ innebär }}{\bar {N}}M^{\textsf {T}}\subseteq {\bar {L}}.$$

Med Schröder-regler och komplementering kan man lösa en okänd relation $X$ i relationsinklusioner som t.ex.

$$RX\subseteq S\quad {\text{and}}\quad XR\subseteq S.$$

Till exempel, enligt Schröders regel $RX\subseteq S{\text{ antyder }}R^{\textsf {T}}{\bar {S}}\ subseteq {\bar {X}},$ och komplementering ger $X\subseteq {\overline {R^{\textsf {T}}{\bar {S}}}},$ som kallas den vänstra residualen av $S$ av $R$ .

Kvotienter

Precis som sammansättning av relationer är en typ av multiplikation som resulterar i en produkt, så jämförs vissa operationer med division och producerar kvoter. Tre kvoter visas här: vänster residual, höger residual och symmetrisk kvot. Den vänstra residualen av två relationer definieras förutsatt att de har samma domän (källa), och den högra residualen förutsätter samma kodomän (intervall, mål). Den symmetriska kvoten förutsätter att två relationer delar en domän och en kodomän.

Definitioner:

• Vänster rest: $A\backslash B\mathrel {:=} {\overline {A^{\textsf {T}}{\bar {B}}}}$
• Höger residual: $D/C\mathrel {:=} {\overline {{\bar {D}}C^{\textsf {T}}}}$
• Symmetrisk kvot: $\operatorname {syq} (E,F)\mathrel {:=} {\overline {E^{\ textsf {T}}{\bar {F}}}}\cap {\overline {{\bar {E}}^{\textsf {T}}F}}$

Med Schröders regler är $AX\subseteq B$ ekvivalent med $X\subseteq A\setminus B.$ Den vänstra residualen är alltså den största relationen som uppfyller $AX\subseteq B.$ På liknande sätt är inkluderingen $YC\subseteq D$ ekvivalent med $Y\subseteq D\setminus C,$ och den högra residualen är den största relationen som uppfyller $YC\subseteq D.$

Man kan öva på logiken hos rester med Sudoku .

Gå med: en annan form av komposition

En gaffeloperator $(<)$ har introducerats för att förena två relationer $c:H\to A$ och $d:H\to B$ till $c\,(<)\,d:H\to A\times B.$ Konstruktionen beror på projektioner $a:A\times B\to A$ och $b:A\times B\to B,$ förstås som relationer, vilket betyder att det finns omvända relationer $a^{\textsf {T}}$ och $b^{\textsf {T}}.$ Sedan ges gaffeln av $c$ och ${\displaystyle d} av$

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

En annan form av sammansättning av relationer, som gäller generella $n$ -platsrelationer för $n\geq 2,$ är sammanfogningen av relationalgebra . Den vanliga sammansättningen av två binära relationer som definieras här kan erhållas genom att ta deras sammanfogning, vilket leder till en ternär relation, följt av en projektion som tar bort den mellersta komponenten. Till exempel, i frågespråket SQL finns operationen Join (SQL) .

Se även

• Demonisk komposition
• Vän till en vän – Mänsklig kontakt som finns på grund av en gemensam vän

Anteckningar

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