Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cours relations d x27 ordre

c Christophe Bertault - MPSI Relations d ? ordre Relations d ? ordre Dans toute cette partie E est un ensemble Relations binaires Dé ?nition Relation binaire On appelle relation binaire sur E tout triplet R E E ? o? ? est une partie de E ? E Au lieu de noter x y ?? ? on notera généralement xRy ce qui se lit x est en relation avec y par R ? Explication Tout cela a l ? air bien compliqué Pourtant une relation binaire sur E n ? est qu ? une façon de relier entre eux certains éléments de E Il faut bien noter qu ? en général la relation xRy n ? implique pas la relation yRx On peut trouver cela contre-intuitif à première vue car le français ne distingue pas bien les phrases x est en relation avec y ? et y est en relation avec x ? mais cela para? t plus clair si on a l ? exemple suivant en tête A aime B mais B n ? aime pas A ? On peut représenter les relations binaires au moyen de ce qu ? on appelle des graphes orientés un graphe orienté est un ensemble de points appelés les sommets du graphe reliés par des arètes échées Pour comprendre cela donnons-nous une relation binaire R sur E Les sommets du graphe orienté associé à R sont tous les points de E Deux sommets x et y sont liés par une arète orientée de x vers y si la relation xRy est vraie une double èche indique qu ? on a à la fois xRy et yRx Par exemple le graphe ci-contre représente la relation binaire R sur dé ?nie par R R R R R R R R et R Exemple Vous connaissez depuis toujours certaiÒnes relaÓtions binaires ? la relation d ? égalité sur E ici ? x x Ò Ó x ??E ? la relation sur R ici ? x y ?? R ? R x y ? la relation sur l ? ensemble RR dé ?nie par ??f g ?? RR ? la relation de divisibilité sur Z dé ?nie par ??m n ?? Z f g ? ?? ??x ?? R f x g x m n ? ?? ?? k ?? Z n km Dé ?nition Propriétés des relations binaires Soit R une relation binaire sur E ? On dit que R est ré exive si ??x ?? E xRx ? On dit que R est transitive si ??x y z ?? E xRy et yRz ?? xRz ? On dit que R est symétrique si ??x y ?? E xRy ? ?? yRx ? On dit que R est antisymétrique si ??x y ?? E xRy et yRx ?? x y Explication Ces propriétés éventuelles des relations binaires se voient ? particulièrement bien sur les représentations sous forme de graphes ?? c ? est un peu moins clair pour la transitivité Ré exivité Une boucle à chaque