(Clôture transitive. Cet exercice utilise la notion de produit de relations) Soit \(\mathcal R\) une relation sur \(E\). Pour \(n\in \N\) et \(\mathcal R\) est une relation sur \(E\), on définit alors par récurrence la relation \(\mathcal R^n\) (en définissant \(\mathcal R^0\) comme l’égalité, puis \(\mathcal R^{n+1} = \mathcal R \mathcal R^n\)).
Montrer que toutes les relations suivantes sont égales:
1
\(\bigvee_{n\geq 0} \mathcal R^n\);
2
la relation dont le graphe est \(\bigcup_{n\geq 0} \Gamma_{\mathcal R^{n}}\);
3
la relation dont le graphe est l’intersection de tous les graphes de relations transitives qui contiennent \(\Gamma_{\mathcal R}\).
4
la plus fine relation parmi toutes les relations transitives moins fines que \(\mathcal R\).