Scan0045

56 Iloczyn kartezjański. Relacje

Własności

1.	zwrotność	A xRx x€X
2.	przeciwzwrotność	A ~ xRx
3.	symetryczność^1	A (xRy yRx) x,yeX
4.	przeciwsymetryczność (asymetryczność)	A {xRy => ~ yRx) x,y£X
5.	antysymetryczność	A [(xRy A yRx) a x,ySX	' = y]
6.	przechodniość	A [{xRy A yRz) => x,y,z£X	xRz]
7.	spójność	A (xRy V yRx) x,y£X
Uwaga	5.4

•    w podanych definicjach dopuszczamy równość elementów x i y,

•    jeżeli relacja jest zwrotna, to nie jest przeciwzwrotna, i na odwrót,

•    relacja może nie być ani zwrotna, ani przeciwzwrotna,

•    jeżeli relacja jest symetryczna, to nie jest przeciwsymetryczna, i na odwrót,

•    relacja może nie być ani symetryczna, ani przeciwsymetryczna.

Relację zwrotną, symetryczną i przechodnią nazywamy relacją równoważności (własność 8.), tzn. bycia takim samym pod pewnym względem. Przykładem jest relacja rówieśnictwa. Dzieli ona zbiór ludzi na podzbiory (tzw. klasy abstrakcji) ludzi w tym samym wieku. Mówi się wówczas o podziale logicznym zbioru.

Przykład 5.7 Relacja ”x jest ojcem y” nie jest zwrotna, jest przeciwzwrotna, nie jest symetryczna, jest przeciwsymetryczna, nie jest anty symetryczna, nie jest przechodnia i nie jest spójna. Nie jest równoważnością.

1

Symbol    rozumiemy tutaj jako ”pociąga za sobą”.