Les classes d’équivalence, ordre lexicographique et fermeture transitive jouent un rôle fondamental dans l’étude des structures algébriques et des ensembles ordonnés. Ces concepts sont largement utilisés en mathématiques discrètes et en théorie des ensembles pour organiser et classer les éléments.
Classes d’équivalence, Ordre lexicographique et fermeture transitive
Une relation binaire \( R \) sur un ensemble \( E \) est une partie de \( E \times E \). Voici quelques définitions clés :
- Classe d’équivalence : Si \( R \) est une relation d’équivalence, l’ensemble des éléments reliés à \( x \) constitue la classe d’équivalence de \( x \), notée \( [x] \).
- Ordre lexicographique : Un ordre défini sur des paires \( (x,y) \) par \( (x_1, y_1) \leq (x_2, y_2) \) si et seulement si \( x_1 < x_2 \) ou \( (x_1 = x_2 \) et \( y_1 \leq y_2) \).
- Fermeture transitive : La plus petite relation transitive contenant \( R \). Si \( x R y \) et \( y R z \), alors \( x R z \).
Formellement, pour une relation \( R \) :
\[ R^+ = \bigcup_{i=1}^{\infty} R^i \] où \( R^i \) est la composition itérée de \( R \).
Exemples sur Classes d’équivalence, Ordre lexicographique et fermeture transitive
Exemple 1 : Soit \( E = \{a, b, c, d\} \) et la relation \( R \) définie par :
\[ R = \{(a,a), (b,b), (c,c), (d,d), (a,b), (b,c), (c,d)\} \]
Solution :
La fermeture transitive de cette relation ajoute l’arc \( (a,c) \) et \( (a,d) \). On obtient :
\[ R^+ = \{(a,a), (b,b), (c,c), (d,d), (a,b), (b,c), (c,d), (a,c), (a,d), (b,d)\} \]
Exemple 2 : Considérons l’ordre lexicographique sur l’ensemble \( E = \{(1,1), (1,2), (2,1), (2,2)\} \).
Solution :
La relation d’ordre lexicographique produit :
\[ (1,1) \leq (1,2) \leq (2,1) \leq (2,2) \]