Fiche de révision : Relations et structures d’ordre

📋 Plan du Cours

1. Définition et représentations des relations
2. Relations inverses et compositions
3. Propriétés des relations binaires
4. Fermetures des relations
5. Relations d’équivalence
6. Classes et ensemble quotient
7. Définition des relations d’ordre
8. Diagrammes de Hasse et éléments remarquables

📖 1. Définition et représentations des relations

🔑 Notions clés & Définitions

• Relation : Sous-ensemble de A × B qui relie certains éléments de A à certains éléments de B.
• Graphe d’une relation : Le graphe d’une relation R est l’ensemble $G_R = \{(a,b) \in A \times B \mid a\ R\ b\}$ des couples en relation.

★ À maîtriser

• Une relation peut être représentée par:
  • un graphe
  • un diagramme cartésien
  • une matrice booléenne
  • un diagramme sagittal
  • un graphe orienté

Compléments

• Dans une relation de A dans B, A est l’ensemble de départ, B est l’ensemble d’arrivée, et lorsque A = B il s’agit d’une relation binaire dans A.

• Pour la relation définie sur {1, 3, 5, 7} vers {2, 4, 6} par x R y si et seulement si x < y, le graphe est {(1,2), (1,4), (1,6), (3,4), (3,6), (5,6)}.

💡 Astuce mémo

Imaginez un tableau de couples reliés par des flèches entre A et B.

📖 2. Relations inverses et compositions

🔑 Notions clés & Définitions

• Relation inverse : Relation de B dans A définie par b R⁻¹ a si et seulement si a R b.
• Composition de relations : Relation de A vers C telle que a R₂ ∘ R₁ c si et seulement s’il existe b ∈ B tel que a R₁ b et b R₂ c.

📝 Points essentiels

📐 Formule — Le graphe de la relation inverse vérifie $G_{R^{-1}} = \{(b,a) \mid (a,b) \in G_R\} \subset B \times A$.

📐 Formule — La matrice booléenne de la composée de deux relations est obtenue par le produit matriciel booléen des matrices des deux relations, $A = A_1 A_2$.

💡 Astuce mémo

Inverser les flèches, puis enchaîner A → B → C.

📖 3. Propriétés des relations binaires

🔑 Notions clés & Définitions

• Réflexivité : Une relation R sur A est réflexive si, pour tout x ∈ A, on a x R x.
• Symétrie : Relation sur A telle que, pour tous x,y ∈ A, x R y implique y R x.
• Transitivité : Relation sur A telle que, pour tous x,y,z ∈ A, x R y et y R z impliquent x R z.
• Antisymétrie : Relation sur A telle que, pour tous x,y ∈ A, x R y et y R x impliquent x = y.

💡 Astuce mémo

RST-A : Réflexivité, Symétrie, Transitivité, Antisymétrie.

📖 4. Fermetures des relations

🔑 Notions clés & Définitions

• Fermeture d’une relation : Plus petite relation contenant R et satisfaisant P.

★ À maîtriser

• Pour construire une fermeture, on ajoute à R les couples nécessaires jusqu’à satisfaire la propriété visée, sans ajouter de couples superflus.

Compléments

• Dans l’exemple donné, la fermeture réflexive ajoute (2,2) et (3,3), tandis que la fermeture symétrique ajoute (2,1) et (3,2).

• La fermeture transitive d’un graphe de dépendance permet de déterminer toutes les variables nécessaires directement ou indirectement au calcul d’une variable.

💡 Astuce mémo

Ajouter les couples nécessaires → obtenir la plus petite relation possédant la propriété.

📖 5. Relations d’équivalence

🔑 Notions clés & Définitions

• Relation d’équivalence : Relation binaire sur un ensemble E qui est réflexive, symétrique et transitive.

📝 Points essentiels

• La relation « avoir le même âge » sur l’ensemble des personnes est une relation d’équivalence.

• La relation sur ℤ* définie par x R y si et seulement si xy > 0 est une relation d’équivalence qui relie les entiers relatifs de même signe.

💡 Astuce mémo

RST : une équivalence est Réflexive, Symétrique et Transitive.

📖 6. Classes et ensemble quotient

🔑 Notions clés & Définitions

• Classe d’équivalence : Ensemble des éléments de E liés à x.
• Ensemble quotient : Ensemble de toutes les classes d’équivalence d’un ensemble E muni de la relation R.

★ À maîtriser

📌 Deux classes d’équivalence distinctes sont disjointes ; de façon équivalente, deux classes qui ont une intersection non vide sont égales.

Compléments

📌 Toute classe d’équivalence est non vide, car elle contient au moins son propre élément grâce à la réflexivité.

• Pour la congruence modulo 3 sur ℤ, les trois classes sont Cl(0), Cl(1) et Cl(2), et l’ensemble quotient est noté ℤ/3ℤ = {0,1,2}.

💡 Astuce mémo

Les classes forment des cases disjointes qui partitionnent l’ensemble.

📖 7. Définition des relations d’ordre

🔑 Notions clés & Définitions

• Relation d’ordre : Relation binaire sur un ensemble E qui est réflexive, transitive et antisymétrique.
• Ordre total : Ordre tel que, pour tous x,y ∈ E, x R y ou y R x ; sinon, il est dit partiel pour souligner que certains éléments peuvent être incomparables.

📝 Points essentiels

• Les relations ≤ et ≥ sont des ordres totaux sur ℕ et s’étendent à ℤ, ℚ et ℝ, tandis que < et > ne sont pas des relations d’ordre car elles ne sont pas réflexives.

• La relation « être préfixe de » sur l’ensemble des mots est un ordre non total, alors que l’ordre lexicographique est un ordre total.

💡 Astuce mémo

Ordre total : tout couple est comparable ; ordre partiel : certains peuvent ne pas l’être.

📖 8. Diagrammes de Hasse et éléments remarquables

🔑 Notions clés & Définitions

• Successeur immédiat : Dans un ordre, y est un successeur immédiat de x si x R y et s’il n’existe aucun z tel que x R z et z R y.
• Diagramme de Hasse : Représentation d’un ordre fini supprimant les boucles de réflexivité et les arcs déductibles par transitivité afin de conserver les relations entre successeurs immédiats.
• Plus petit et plus grand éléments : Un plus petit élément m vérifie m R x pour tout x ∈ E, tandis qu’un plus grand élément M vérifie x R M pour tout x ∈ E.
• Éléments minimal et maximal : Un élément minimal n vérifie que x R n implique x = n, tandis qu’un élément maximal N vérifie que N R x implique x = N.

📝 Points essentiels

• Dans l’ordre de divisibilité sur {1,2,3,6,12,18}, 12 et 18 sont des éléments maximaux sans plus grand élément, tandis que 1 est le plus petit élément.

💡 Astuce mémo

Supprimer boucles et raccourcis, puis garder les successeurs immédiats.

📊 Tableaux de synthèse

Équivalence et ordre