Aspects Algébriques

Les relations

Soit ${\tt E}=\{1,2,3,4\}$ et soient ${\cal R}$ et ${\cal S}$ des relations sur ${\tt E}$ définies par :

• ${\cal R}=\{(1,2),(2,3),(4,4)\}$
• ${\cal S}=\{(1,2),(2,4),(4,3),(3,4)\}$

1.

Représenter ${\cal R}$ et ${\cal S}$ par leur graphe et leur matrice d'adjacence.

2.

${\cal R}$ et ${\cal S}$ sont-elles reflexives, symétriques, transitives, antireflexives et antisymétriques ?

3.

Calculer ${\cal R}\cup{\cal S}$, ${\cal R}\cap{\cal S}$, ${\cal R}\circ{\cal S}$, ${\cal S}\circ{\cal R}$.

4.

Calculer les clôtures reflexives de ${\cal R}$ et ${\cal S}$.

5.

Calculer les clôtures transitives de ${\cal R}$ et ${\cal S}$.

6.

Calculer les équivalences engendrées par ${\cal R}$ et ${\cal S}$.

7.

${\cal R}$ et ${\cal S}$ sont-elles prolongeables en des ordres totaux ?

8.

On pose :

$${\cal R}^\star=\bigcup_{i\geq 0}{\cal R}^i$$

où :

$$\left\{\begin{tabular}{l} ${\cal R}^0=\{(x,x)/x\in {\tt E}\}... ...cal R}^i={\cal R}^{i-1}\circ{\cal R}$ \\ \end{tabular}\right.$$

Montrer :

(a)

$\forall x,y\in {\tt E},(x,y)\in {\cal R}^\star \Leftrightarrow (\exists i\geq ... ...\in {\tt E} \mbox{ et }\forall 0\leq l<i\Rightarrow (x_l,x_{l+1})\in{\cal R})$

(b)

${\cal R}^\star$ est la relation la plus fine qui contient ${\cal R}$ et est reflexive et transitive