c ⃝Christophe Bertault - MPSI Relations d’ordre 1 Relations d’ordre Dans toute

c ⃝Christophe Bertault - MPSI Relations d’ordre 1 Relations d’ordre Dans toute cette partie, E est un ensemble. 1.1 Relations binaires Définition (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 flé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 flèche indique qu’on a à la fois xRy et yRx. Par exemple, le graphe ci-contre représente la relation binaire R sur J1, 6K définie par : 1R2, 2R1, 2R2, 2R5, 2R6, 3R3, 3R5, 3R6 et 5R3. 1 2 3 4 5 6 Exemple Vous connaissez depuis toujours certaines relations binaires : • la relation d’égalité = sur E ; ici, Γ = n (x, x) o x∈E ; • la relation ⩽sur R ; ici, Γ = n (x, y) ∈R × R/ x ⩽y o ; • la relation ⩽sur l’ensemble RR, définie par : ∀f, g ∈RR, f ⩽g ⇐ ⇒  ∀x ∈R, f(x) ⩽g(x)  ; • la relation de divisibilité | sur Z, définie par : ∀m, n ∈Z, m|n ⇐ ⇒ ∃k ∈Z/ n = km. Définition (Propriétés des relations binaires) Soit R une relation binaire sur E. • On dit que R est réflexive 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é. 1 2 3 4 5 6 Réflexivité : Une boucle à chaque sommet. 1 3 4 5 6 Transitivité. 1 2 3 4 5 6 Symétrie : Que des flèches doubles (sauf pour les flèches qui « bouclent »). 1 2 3 4 5 6 Antisymétrie : Aucune flèche double. 1 c ⃝Christophe Bertault - MPSI Exemple • La relation d’égalité = sur E est réflexive, transitive, symétrique et antisymétrique. • Les relations ⩽sur R et RR sont réflexives, transitives et antisymétriques. Elles ne sont pas symétriques car par exemple : 1 ⩽2 mais 2 1, et (x 7− →x) ⩽(x 7− →x + 1) mais (x 7− →x + 1) (x 7− →x). • La relation < sur R est transitive et antisymétrique, mais elle n’est ni réflexive, ni symétrique. • La relation | de divisibilité sur Z est réflexive et transitive, mais elle n’est pas antisymétrique car par exemple −2|2 et 2| −2 alors que −2 ̸= 2. • La relation d’inclusion ⊆sur P(E) est réflexive, transitive et antisymétrique. • La relation S sur R× définie par : ∀x, y ∈R×, xS y ⇐ ⇒ x et y ont le même signe est réflexive, transitive et symétrique. 1.2 Relations d’ordre Définition (Relation d’ordre) Soit R une relation binaire sur E. On dit que R est une relation d’ordre sur E si R est à la fois réflexive, transitive et antisymétrique. Les relations d’ordre sont souvent notées ⩽ou ≼ou ≲ou ≾. . . Exemple • Les relations ⩽sur R et RR sont des relations d’ordre — il en est de même des relations ⩾. • La relation d’inclusion ⊆sur P(E) est une relation d’ordre. Exemple La relation de divisibilité | sur Z n’est pas une relation d’ordre — on a vu qu’elle n’est pas antisymétrique ; la relation de divisibilité | sur N en revanche en est une. En effet • Réflexivité : Soit n ∈N. Alors n|n car n = 1 × n. • Transitivité : Soient n, n′, n′′ ∈N tels que n|n′ et n′|n′′. Montrons que n|n′′. Or puisque n|n′, il existe k ∈N tel que n′ = kn ; et puisque n′|n′′, il existe k′ ∈N tel que n′′ = k′n′. Du coup n′′ = k′n′ = kk′n, et donc n|n′′. • Antisymétrie : Soient n, n′ ∈N tels que n|n′ et n′|n. Montrons que n = n′. Or puisque n|n′, il existe k ∈N tel que n′ = kn ; et puisque n′|n, il existe k′ ∈N tel que n = k′n′. Alors n = k′n′ = kk′n. Deux cas doivent être distingués ici : 1) Si n = 0, alors n′ = kn = k × 0 = 0 et donc n = n′ comme voulu. 2) Si n ̸= 0, on obtient kk′ = 1 en simplifiant par n. Or k et k′ sont deux entiers naturels, donc k = k′ = 1. Ici aussi, n = k′n′ = n′.    Explication Une relation d’ordre sur E est, comme son nom l’indique, une relation qui met de l’ordre entre les éléments de E. « Ordre » s’entend ici au sens de « hiérarchie » : il y a un haut et un bas, des plus petits et des plus grands. Si ≼est une relation d’ordre sur E, la relation x ≼y s’interprète généralement en disant que x est plus petit que y ; cela dit, cette interprétation est purement conventionnelle et on pourrait considérer que la relation x ≼y signifie que x est plus grand que y — c’est une question de goût. Dans le graphe associé à une relation d’ordre ≼sur E, les seules « boucles » présentes sont liées à la réflexivité de ≼. Il n’est pas possible d’avoir une boucle de la forme x1 ≼x2, x2 ≼x3, . . . , xn−1 ≼xn, xn ≼x1 où x1, x2, . . . , xn sont des éléments distincts de E. Si en effet on avait une telle boucle, alors on aurait x2 ≼x1 par transitivité de ≼, puis x1 = x2 par antisymétrie, contrairement à l’hypothèse. Cette propriété des relations d’ordre a un impact géométrique sur les graphes qui leur sont associés. Les graphes de relations d’ordre ont comme une orientation naturelle : en les parcourant on va toujours de l’avant, on ne revient jamais en arrière, on ne tourne jamais en rond. C’est un peu comme les réseaux fluviaux : les fleuves et les rivières coulent tous en direction de la mer et ne bouclent jamais. C’est précisément cette orientation ou « sens de lecture » qui nous invite à considérer que certains éléments sont plus petits/grands que d’autres. 1 2 3 4 5 1 2 3 4 1 2 3 « Boucle » 2 c ⃝Christophe Bertault - MPSI Définition (Eléments comparables, relation d’ordre total/partiel) Soit ≼une relation d’ordre sur E. • Soient x, y ∈E. On dit que x et y sont comparables par ≼si on a x ≼y ou y ≼x — éventuellement les deux et dans ce cas x = y par antisymétrie. • On dit que ≼est totale si deux éléments quelconques de E sont toujours comparables par ≼, i.e. : ∀x, y ∈E, x ≼y ou y ≼x. Une relation non totale est dite partielle. Exemple • La relation ⩽sur R est une relation d’ordre totale. En particulier tous les réels sont comparables à 0 — positifs ou négatifs — et c’est pourquoi, par exemple, on a eu le droit de définir la fonction valeur absolue |x| sur R en distinguant deux cas : x ⩾0 et x < 0. • La relation ⩽sur RR est une relation d’ordre partielle. Par exemple, les fonctions sinus et cosinus ne sont pas comparables : on n’a ni sin ⩽cos ni cos ⩽sin. • La relation de divisibilité | sur N est une relation d’ordre partielle car 2 et 3 sont incomparables pour cette relation : on n’a ni 2|3 ni 3|2. • La relation d’inclusion ⊆sur P(E) est une relation d’ordre partielle dès que uploads/Geographie/ cours-relations-d-x27-ordre.pdf

Tags
Administrationrelation borne élément partie alors
Documents similaires
  • 25
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager