Złożenie relacji

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Złożenie relacji binarnych – pewna relacja binarna zdefiniowana za pomocą dwóch innych relacji. Przypadkiem szczególnym złożenia relacji jest złożenie funkcji.

Definicja[edytuj]

Niech będą zbiorami oraz ,   .

Złożenie relacji definiujemy następująco:

Można to zapisać symbolicznie:

  wtedy i tylko wtedy, gdy dla pewnego zachodzi   

Przykład[edytuj]

Niech i będą takimi relacjami w zbiorze , że:

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

Własności[edytuj]

  • Operacja złożenia relacji jest łączna, tj.: .
  • Operacja złożenia relacji nie jest przemienna, tj.: nie dla wszystkich relacji i zachodzi .
  • Jeśli relacje i iniekcją, to złożenie relacji również jest iniekcją. W odwrocie iniekcja implikuje jedynie iniekcję .
  • Jeśli relacje i surjekcją, to złożenie relacji również jest surjekcją. W odwrocie surjekcja implikuje jedynie surjekcję .

Zobacz też[edytuj]

Półgrupa relacji binarnych