5600235765

1 Relacje 3

1.3    Relacje

Relacja binarna (dwuargumentowa) to podzbiór iloczynu kartezjańskiego dwóch zbiorów.

Jeśli weźmiemy A = X xY, to Wa, podobnie jak wyżej, oznacza pewną własność, a zarazem podzbiór, iloczynu kartezjańskiego X xY. Ten podzbiór, czyli zbiór par o pewnej własności, to właśnie relacja — relacja pomiędzy pierwszą a drugą zmienną w iloczynie kartezjańskim.

Poza relacjami standardowymi, które mają swoje własne oznaczenia, relacje zwykle będziemy oznaczać grecką literą p. Także jeśli rozpatrujemy relację p pomiędzy elementami zbioru X a elementami zbioru Y, czyli relację w iloczynie kartezjańskim X x 7, to formalnie

pCX xY.

Piszemy

•    (x, y) G p i mówimy, że para (x, y) należy do relacji p, albo piszemy

•    x p y i wtedy mówimy, że element x jest w relacji p z elementem y, dla x G X oraz y &Y.

Przykład 1.3. Niech X = {1,4,5}, Y = {2,3} oraz

p = {(x, y): x + y jest liczbą parzystą}.

Wówczas

XXY= {(1,2), (4,2), (5,2), (1, 3), (4,3), (5,3)} oraz p= {(4,2), (1,3), (5,3)}.

Mówimy, że relacja p C X x Y jest określona na zbiorze X x Y. Jeśli Y = X, to wówczas p C X² i mówimy krótko, że relacja p jest określona na zbiorze X.

1.4    Własności relacji

Rozważamy relację p C X x X dla dowolnego zbioru X.

zwrotność Relacja p jest zwrotna, wtw., gdy dla każdego x G X zachodzi x p x. Innymi słowy, zwrotność relacji oznacza, że każdy element jest w relacji ze sobą.

symetria Relacja p jest symetryczna, wtw., gdy dla dowolnych x, y G X jeśli x p y, to y p x. Intuicyjnie, symetria relacji oznacza, że możemy zamienić x z y w parze (x,y) o ile w ogóle (x,y) G p. Tak więc kolejność występowania elementów w relacji nie ma tutaj znaczenia.

antysymetria Relacja p jest antysymetryczna, wtw., gdy dla dowolnych x,y G X jeśli x p y oraz y p x, to x = y. Tak więc antysymetria relacji oznacza, że kolejność występowania różnych elementów w relacji jest istotna. To znaczy, że dla x ^ y albo x p y, albo y p x, albo nie zachodzi ani jedno, ani drugie.

przechodniość Relacja p jest przechodnia, wtw., gdy dla dowolnych x,y,z G X jeśli x p y oraz y p z, to również x p z.