Chiusura riflessiva e transitiva di una relazione

[thedarkhero]

Sia $R$ una relazione binaria sull'insieme $A$.

Definizione 1:
Si definisce la chiusura riflessiva e transitiva di $R$ come $\barR=nn_{R\subeS, "S riflessiva", "S transitiva"}S$.

Definizione 2:
Si definisce la chiusura riflessiva e transitiva di $R$ come la (più piccola) relazione definita per induzione mediante le regole:
- $\barR(a,a)$ $AAa\inA$;
- se $R(a,b)$ allora $\barR(a,b)$;
- se $\barR(a,b)$ e $\barR(b,c)$ allora $\barR(a,c)$.

Voglio dimostrare che le due definizioni sono equivalenti.

Sia $\barR$ come da definizione 1. Allora:
- $\barR$ è riflessiva perchè è intersezione di relazioni riflessive (quindi vale la prima regola della definizione 2);
- $R\sube\barR$ perchè è intersezione di relazioni contenenti $R$ (quindi vale la seconda regola della definizione 2);
- $\barR$ è transitiva perchè è intersezione di relazioni transitive (quindi vale la terza regola della definizione 2).
Se $T$ è una relazione riflessiva, transitiva e contenente $R$ allora $\barR=nn_{R\subeS, "S riflessiva", "S transitiva"}S\subeT$, dunque $\barR$ è la più piccola relazione riflessiva, transitiva e contenente $\barR$.

Ho così dimostrato che $\barR$ come è definita in definizione 1 soddisfa la definizione 2.

Come posso dimostrare il viceversa?

[killing_buddha]

Scrivo \(\overline{R}^{(1)} = \bigcap_{S\supseteq R} S\), e \(\overline{R}^{(2)} \) come la seconda relazione.

E' ora chiaro che $\overline{R}^{(2)} \supseteq \overline{R}^{(1)}$. Ti basta mostrare l'implicazione inversa: per farlo, mostra che se $S$ è riflessiva e transitiva contenente $R$, allora contiene $\overline{R}^{(2)}$.

[thedarkhero]

Se $S$ è riflessiva, transitiva e continiene $R$ allora contiene $\barR^{(2)}$ perchè $\barR^{(2)}$ è la più piccola relazione riflessiva, transitiva e contenente $R$.
Dunque $\barR^{(2)}\sube\barR^{(1)}$ perchè $\barR^{(2)}\subeS$ per ogni relazione $S$ riflessiva, transitiva e contenente $R$.
Può andare?