Podobnie jak na zbiorach, na relacjach binarnych możemy wykonywać operacje teoriomnogościowe. Jeśli r' i r" są dwiema relacjami binarnymi w X´ Y, to r' È r", r' Ç r", r' \ r" są podzbiorami zbioru X ´ Y, a więc relacjami dwuczłonowymi w X ´ Y.

Jeśli do relacji binarnej określonej w produkcie X´ Y nie należy żadna para (x,y), to mówimy, że jest to relacja pusta; jeśli natomiast każda para (x,y) dla x Î X i y Î Y należy do relacji, to mówimy, że jest to relacja pełna.

Pytanie 2.4.1: Jaką relację otrzymamy sumując relacje £ i ³ określone w zbiorze N?

Pytanie 2.4.2: Jaką relację otrzymamy w wyniku przecięcia relacji £ i ³ określonych w zbiorze N?

Definicja 2.4.1

Niech r będzie relacją binarną w X ´ Y. Relacją odwrotną do relacji r nazywamy relację r ^-1 określoną w Y ´ X taką, że dla dowolnych x Î X i y Î Y,

(y, x) Î r ^-1 wttw (x, y) Î r

(2) Relacją odwrotną do relacji przedstawionej na rysunku Rys. 2.4.1 (a) jest relacja przedstawiona na rysunku 2.4.1(b).

Pytanie 2.4.3: Czy dla dowolnych relacji binarnych r' i r" określonych w X´ Y zachodzi (r' Ç r")^-1 = r' ^-1Ç r"^-1.

Definicja 2.4.2

Niech r' Í X ´ Y oraz r" Í Y´ Z. Złożeniem relacji r' z r" nazywamy relację r' ° r" będącą podzbiorem zbioru X´Z określoną dla dowolnych x Î X i z Î Z następująco:

(x, z) Î r' ° r" wttw istnieje takie yÎ Y, że (x, y) Î r' i (y, z) Î r".

Niech r, s, r' i s' będą relacjami przedstawionymi na rysunku 2.4.2a,b. Złożenia r ° s i r' ° s' zostały przedstawione na rysunku 2.4.2c.

Następujący lemat pozwala scharakteryzować w prosty sposób relacje symetryczne i przechodnie przy pomocy wprowadzonych operacji na relacjach.

Lemat 2.4.1

Niech r będzie relacją binarną w zbiorze X. Wtedy

r jest relacją symetryczną wttw r Í r ^-1,
r jest relacją przechodnią wttw r ° r Í r.

Ad. 1. Jeśli r jest relacją symetryczną i (x, y) Î r, to na mocy symetrii (y, x) Î r, a stąd (x, y) Î r ^-1. Odwrotnie, jeśli r Í r ^-1 i (x, y) Î r, to (x, y) Î r ^-1, a z definicji operacji odwracania, (y, x) Î r. Ponieważ x i y były dowolnymi elementami zbioru X, zatem r jest relacją symetryczną.

Ad. 2. Jeśli r jest relacją przechodnią i (x, y) Î r ° r, to na mocy definicji operacji składania, istnieje z takie, że (x, z) Î r i (z, y) Î r . Stąd i z przechodniości relacji r, (x, y) Î r. Zatem r ° r Í r.

Odwrotnie, jeśli r ° r Í r oraz (x, y) Î r i (y, z) Î r dla pewnych elementów x, y, z zbioru X, to (x, z) Î r ° r i w konsekwencji (x, z) Î r, co dowodzi przechodniości relacji r.

Pytanie 2.4.4: Czy relacje inkluzji występujące w sformułowaniu powyższego lematu mogą być zastąpione po prostu równością?