Domknięcie tranzytywne relacji

[polonus]

Prosiłbym o rozwiązanie z komentarzem następującego zadania.
Znajdź domknięcie tranzytywne określonej na \(\displaystyle{ X=\left\{ a,b,c,d,e\right\}}\) relacji \(\displaystyle{ R=\left\{ (a,a), (b,d), (e,d), (c,a), (e,c), (d,a)\right\}}\).

[Qń]

A z czym dokładnie masz problem?

Q.

[polonus]

Definicja tranzytywnego domknięcia relacji jest dla mnie nieczytelna, toteż prosiłbym o omówienie jej na tym przykładzie.

[Qń]

Żeby domknąć relację tranzytywnie, musisz dorzucić do niej takie pary (możliwie mało takich par), żeby była przechodnia.

Na przykład - do relacji należą pary \(\displaystyle{ (b,d)}\) i \(\displaystyle{ (d,a)}\), więc trzeba też dorzucić \(\displaystyle{ (b,a)}\). Spróbuj znaleźć resztę tego co trzeba dorzucić.

Q.

[polonus]

Aha, czyli jeśli mamy \(\displaystyle{ R=\left\{(a,a), (b,d), (e,d), (c,a), (e,c), (d,a)\right\}}\), to dopełnienie wyznaczamy szukając par, które mogą być przechodnie, czyli będzie:
\(\displaystyle{ (e,c), (c,a) =(e,a) \\
(b,d), (d,a) = (b,a) \\
(e,d), (d,a) = (e,a) \\
(c,a),(a,a) = (c,a) \\
(d,a),(a,a) = (d,a)}\).
A zatem ostatecznie domknięciem tranzytywnym relacji \(\displaystyle{ R=\left\{(a,a), (b,d), (e,d), (c,a), (e,c), (d,a)\right\}}\) jest zbiór \(\displaystyle{ \left\{ (e,a), (b,a)\right\}}\). Bo usuwamy te elementy, które występują już w \(\displaystyle{ R}\). Czy tak?