Złożenie relacji

Złożenie relacji dwuargumentowych – uogólnienie złożenia funkcji na dowolne relacje dwuargumentowe; sposób konstrukcji relacji dwuargumentowej z dwóch innych, a zarazem wynik tej konstrukcji. Formalnie dla zbiorów $X,Y,Z$ i relacji $R\subseteq X\times Y,$ $S\subseteq Y\times Z$ złożenie tej dwójki to zbiór $S\circ R$ zdefiniowany warunkiem:

$S\circ R:={\big \{}(x,z)\in X\times Z:\mathop {\exists } \limits _{y\in Y}\;x\ R\ y\land y\ S\ z{\big \}};$

innymi słowy $x\ (S\circ R)\ z$ wtedy i tylko wtedy, gdy dla pewnego $y$ zachodzi $x\ R\ y\ S\ z$.

Uwaga. Powyższa definicja sprawia, że w przypadku kiedy relacja dwuargumentowa jest też funkcją, złożenie funkcji jest szczególnym przypadkiem złożenia relacji. W niektórych źródłach, zwłaszcza z pograniczy informatyki i teorii baz danych, można spotkać definicję relacji różniącą się kolejnością składanych relacji.

$R\circ S:={\big \{}(x,z)\in X\times Z:\mathop {\exists } \limits _{y\in Y}\;x\ R\ y\land y\ S\ z{\big \}};$

Przykłady

Niech $R$ i $S$ będą takimi relacjami w zbiorze $\mathbb {N} ,$ że:

$R=\{(2,1),(3,1),(4,2),(4,5),(5,3)\}$

$S=\{(1,3),(4,1),(3,6),(6,8),(6,7)\}$

Wtedy odpowiednio złożeniem relacji będą:

$S\circ R=\{(2,3),(3,3),(5,6)\}$

$R\circ S=\{(1,1)\}$

Własności

• Jest to działanie łączne; relacje dwuczłonowe na ustalonym zbiorze tworzą z nim półgrupę:

  $S\circ (R\circ T)=(S\circ R)\circ T.$

• Operacja złożenia relacji nie jest przemienna – istnieją relacje $S$ i $R,$ dla których

  $S\circ R\neq R\circ S.$

• Jeśli relacje $R$ i $S$ są jednoznaczne lewostronnie (iniektywne), to złożenie relacji $S\circ R$ również jest jednoznaczne lewostronnie (iniektywne). W drugą stronę jednoznaczność lewostronna (iniektywność) $S\circ R$ pociąga jedynie jednoznaczność lewostronną (iniektywność) $R$.
• Jeśli relacje $R$ i $S$ są całkowite prawostronnie (surjektywne), to złożenie relacji $S\circ R$ również jest całkowite prawostronnie (surjektywne). Odwrotnie całkowitość prawostronna (surjektywność) $S\circ R$ pociąga tylko całkowitość prawostronną (surjektywność) $S$.
• Składanie relacji jest prawostronnie rozdzielne względem sumy zbiorów:

$(R\cup S)\circ T=(R\circ T)\cup (S\circ T).$

• Działanie to nie jest rozdzielne względem przekroju zbiorów, jednak zachodzi słabszy fakt:

$(R\cap S)\circ T\subseteq (R\circ T)\cap (S\circ T).$

Bibliografia

• Antoni Smoluk: Algebra liniowa. Wrocław: Wydawnictwo Uniwersytetu Ekonomicznego we Wrocławiu, 2017. ISBN 978-83-7695-635-0.