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 ${\displaystyle X,Y,Z}$ i relacji ${\displaystyle R\subseteq X\times Y,}$ ${\displaystyle S\subseteq Y\times Z}$ złożenie tej dwójki to zbiór ${\displaystyle S\circ R}$ zdefiniowany warunkiem^[1][2]:

${\displaystyle 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 ${\displaystyle x\ (S\circ R)\ z}$ wtedy i tylko wtedy, gdy dla pewnego ${\displaystyle y}$ zachodzi ${\displaystyle x\ R\ y\ S\ z}$^[3].

Przykłady

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

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

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

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

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

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

Własności

 Zobacz też: własności relacji dwuargumentowych.

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

  ${\displaystyle S\circ (R\circ T)=(S\circ R)\circ T.}$

• Operacja złożenia relacji nie jest przemienna,

  istnieją relacje ${\displaystyle S}$ i ${\displaystyle R,}$ dla których ${\displaystyle S\circ R\neq R\circ S.}$

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

${\displaystyle (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^[1]:

${\displaystyle (R\cap S)\circ T\subseteq (R\circ T)\cap (S\circ T).}$

Przypisy

Bibliografia

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