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 warunkiemSzablon:Odn:

$S\circ R:=\{(x,z)\in X\times Z:\mathrm{\exists }{\mathrm{\backslash limits}}_{y\in Y}xRy\wedge ySz\};$

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

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:=\{(x,z)\in X\times Z:\mathrm{\exists }{\mathrm{\backslash limits}}_{y\in Y}xRy\wedge ySz\};$

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 łączneSzablon:Odn; 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\ne 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$Szablon:Fakt.
• 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$Szablon:Fakt.
• 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

• Szablon:Cytuj książkę