AccueilđŸ‡«đŸ‡·Chercher

Relation d'ordre

Une relation d’ordre dans un ensemble est une relation binaire dans cet ensemble qui permet de comparer ses Ă©lĂ©ments entre eux de maniĂšre cohĂ©rente. Un ensemble muni d’une relation d’ordre est un ensemble ordonnĂ©. On dit aussi que la relation dĂ©finit sur cet ensemble une structure d'ordre ou tout simplement un ordre.

DĂ©finitions et exemples

Relation d'ordre

Une relation d'ordre est une relation binaire rĂ©flexive, antisymĂ©trique et transitive : soit E un ensemble ; une relation interne ≀ sur E est une relation d'ordre si pour tous x, y et z Ă©lĂ©ments de E :

  • x ≀ x (rĂ©flexivitĂ©)
  • (x ≀ y et y ≀ x) ⇒ x = y (antisymĂ©trie)
  • (x ≀ y et y ≀ z) ⇒ x ≀ z (transitivitĂ©)

La forme mĂȘme de ces axiomes permet d'affirmer que ces derniers sont Ă©galement vĂ©rifiĂ©s par la relation binaire rĂ©ciproque ≄, dĂ©finie par

y ≄ x si et seulement si x ≀ y.

À toute relation d'ordre est donc associĂ©e une relation d'ordre opposĂ©e sur le mĂȘme ensemble ; les formules x ≀ y et y ≄ x se lisent indiffĂ©remment : « x est infĂ©rieur Ă  y », ou « x est plus petit que y », ou « y est supĂ©rieur Ă  x », ou « y est plus grand que x » (ou parfois « x est au plus Ă©gal Ă  y », ou « y est au moins Ă©gal Ă  x»)[1].

On associe Ă©galement Ă  toute relation d'ordre ≀, une relation dite d’ordre strict notĂ©e alors < (qui n'est pas une relation d'ordre au sens dĂ©fini prĂ©cĂ©demment puisque la rĂ©flexivitĂ© n'est pas satisfaite), qui est la restriction de la relation d'ordre aux couples d'Ă©lĂ©ments distincts :

x < y si et seulement si x ≀ y et x ≠ y.

La formule x < y s'écrit aussi y > x, et se lit : « x est strictement inférieur à y », ou « x est strictement plus petit que y », « y est strictement supérieur à x », ou « y est strictement plus grand que x »[2].

Pour Ă©viter toute confusion, une relation d'ordre au sens de la dĂ©finition gĂ©nĂ©rale (rĂ©flexive et antisymĂ©trique) est parfois qualifiĂ©e d’ordre large.

Certaines relations d'ordre sont des relations totales, c'est-à-dire que deux éléments de E sont toujours comparables : pour tous x, y de E :

x ≀ y ou y ≀ x.

On dit alors que ≀ est une relation d'ordre total, et que l'ensemble E est totalement ordonnĂ© par cette relation. Une relation d'ordre sur E est dite partielle si elle n'est pas totale, et E est alors partiellement ordonnĂ©. Il est Ă  noter qu'en anglais, on dĂ©signe par ordre partiel un ordre quelconque, qui peut donc ĂȘtre total. Cette terminologie est parfois Ă©galement utilisĂ©e en français.

Ensemble ordonné

Un ensemble ordonnĂ© est un ensemble muni d'une relation d'ordre. Si un ensemble ordonnĂ© est fini, il peut ĂȘtre reprĂ©sentĂ© graphiquement sous la forme d'un diagramme de Hasse, de façon similaire Ă  la reprĂ©sentation habituelle d'un graphe sur papier, ce qui peut permettre de travailler plus aisĂ©ment dessus. S'il est infini, on peut dessiner une partie de son diagramme de Hasse.

Exemples et contre-exemples

Fig. 1. Diagramme de Hasse de l'inclusion, sur l'ensemble des parties d'un ensemble à 3 éléments.
Fig. 2. Diagramme de Hasse de la relation de divisibilité pour les entiers entre 0 et 9.
  • La relation « est infĂ©rieur (ou Ă©gal) Ă  » est une relation d'ordre total sur l'ensemble des entiers (naturels ou relatifs), sur l'ensemble des rationnels ou l'ensemble des rĂ©els.
  • Étant donnĂ© un ensemble ordonnĂ© (E, ≀), l'ordre lexicographique sur l'ensemble des n-uplets d'Ă©lĂ©ments de E est l'« ordre du dictionnaire », plus simple Ă  dĂ©finir par son ordre strict associĂ© : (x1, 
 , xn) < (y1, 
 , yn) si xi = yi pour tous les indices i jusqu'Ă  un certain k < n et xk+1 < yk+1.
  • La relation d'inclusion, « est un sous-ensemble de » ou « est contenu dans », est une relation d'ordre sur l'ensemble E des parties d'un ensemble X. Si X est fini, E est fini (plus prĂ©cisĂ©ment si X contient n Ă©lĂ©ments, E en contient 2n). La figure 1 reprĂ©sente le diagramme de Hasse de (E, ⊂) pour n = 3.
  • Toute restriction Ă  une partie F de E d'un ordre sur E est un ordre sur F. En particulier (d'aprĂšs le point prĂ©cĂ©dent) : sur n'importe quel ensemble F de parties d'un ensemble X, l'inclusion est une relation d'ordre — cet « exemple » est en fait gĂ©nĂ©rique : tout ordre est isomorphe Ă  un ordre de cette forme[3] ;
  • La relation de divisibilitĂ© est une relation d'ordre partiel sur les entiers naturels. La figure 2 reprĂ©sente le diagramme de Hasse de sa restriction aux entiers de 0 Ă  9.
  • L'ordre d'inclusion (cf. ci-dessus), sur l'ensemble des parties d'un produit cartĂ©sien U×V, est la finesse relative des relations binaires de U dans V. Pour V = U, cette relation permet par exemple (par restriction, cf. ci-dessus) de comparer entre elles :
  • Étant donnĂ© une famille (Ei)i∈I d'ensembles ordonnĂ©s, l'ordre naturel sur l'ensemble produit ∏i∈IEi est l'ordre produit, dĂ©fini par :(xi)i∈I ≀ (yi)i∈I si et seulement si pour tout indice i, xi ≀ yi.Par exemple sur l'ensemble EI des fonctions de I dans un ensemble ordonnĂ© E, l'ordre produit est donnĂ© par : f ≀ g si pour tout i ∈ I, f(i) ≀ g(i). Pour l'ordre produit sur ℝℝ, une fonction est plus petite qu'une autre si sa courbe est toujours en dessous de l'autre courbe.
  • On peut gĂ©nĂ©raliser l'ordre lexicographique (mentionnĂ© en dĂ©but de liste) de la façon suivante[4] : si I est bien ordonnĂ©, on dĂ©finit un ordre sur ∏i∈IEi par :(xi)i∈I < (yi)i∈I si et seulement s'il existe des indices i pour lesquels xi ≠ yi et si, pour le plus petit d'entre eux, on a xi < yi.Si les ordres sur les Ei sont totaux, l'ordre lexicographique sur ∏i∈IEi l'est aussi (mais pas en gĂ©nĂ©ral l'ordre produit).
  • Une relation de prĂ©ordre n'est pas une relation d'ordre en gĂ©nĂ©ral car il manque la propriĂ©tĂ© d'antisymĂ©trie. Mais tout quotient d'un prĂ©ordre par la relation d'Ă©quivalence associĂ©e est un ordre.
  • Une relation d'ordre strict sur un ensemble non vide n'est pas une relation d'ordre car elle n'est pas rĂ©flexive. Mais si < est un ordre strict sur E, la relation « x < y ou x = y » est un ordre sur E.
  • Une relation d'ordre cyclique n'est pas une relation d'ordre car c'est une relation ternaire. Mais les relations binaires obtenues en fixant l'un de ses trois arguments sont des relations d'ordre strict.
  • Un arbre enracinĂ© est un graphe orientĂ© acyclique associĂ© Ă  une relation d'ordre partiel particuliĂšre, importante en informatique.

Notions associées

Applications monotones

Si (E, ≀) et (F, ≌) sont deux ensembles ordonnĂ©s, une application f de E dans F est dite croissante (ou parfois croissante au sens large, ou isotone[5]) quand elle conserve l'ordre, dĂ©croissante (au sens large), ou antitone[5] quand elle inverse celui-ci, c'est-Ă -dire que :

f est croissante quand pour tous x et y de E, x ≀ y ⇒ f(x) ≌ f(y) ;
f est dĂ©croissante quand pour tous x et y de E, x ≀ y ⇒ f(x) ≜ f(y).

Elle est dite strictement croissante quand elle conserve l'ordre strict : pour tous x et y de E, x < y ⇒ f(x) â‰ș f(y),

et strictement dĂ©croissante quand elle l'inverse : pour tous x et y de E, x < y ⇒ f(x) ≻ f(y).

À noter que si une application croissante de (E, ≀) dans (F, ≌) est injective alors elle est strictement croissante, mais que la rĂ©ciproque est fausse en gĂ©nĂ©ral (elle est vraie cependant si l'ordre sur E est total)[6].

Une application monotone ou monotone au sens large (resp. strictement monotone) est une application croissante ou décroissante (resp. strictement croissante ou strictement décroissante).

La bijection rĂ©ciproque d'une bijection croissante f : (E, ≀) → (F, ≌) n'est pas nĂ©cessairement croissante (prendre par exemple[7] l'application identitĂ©, de E = ℝ muni de l'ordre d'Ă©galitĂ© dans F = ℝ muni de l'ordre usuel). Elle l'est cependant si ≀ est total (si f−1(y1) ≄ f−1(y2) alors, par croissance de f, y1 ≜ y2. Donc par contraposĂ©e : si y1 â‰ș y2 et si ≀ est total alors f−1(y1) < f−1(y2)).

Un isomorphisme entre deux ensembles ordonnĂ©s (E, ≀) et (F, ≌) est une bijection f de E dans F qui est croissante et dont la rĂ©ciproque est croissante, ce qui revient Ă  dire que f est bijective et vĂ©rifie pour tous x et y de E :

x ≀ y ⇔ f(x) ≌ f(y)[8].

Un plongement d'ensembles ordonnĂ©s de (E, ≀) dans (F, ≌) est une application f de E dans F vĂ©rifiant pour tous x et y de E :

x ≀ y ⇔ f(x) ≌ f(y)

(une telle application est forcément injective). Les isomorphismes d'ordres sont donc les plongements surjectifs[8].

Dans la catégorie des ensembles ordonnés, les morphismes sont par définition les applications croissantes[9], et les isomorphismes sont, par conséquent, ceux introduits ci-dessus.

Plus grand élément et élément maximal

Dans un ensemble ordonné E, il n'existe pas forcément de plus grand élément. Si E est fini, il contiendra (au moins) un élément maximal. Si E est un ensemble inductif infini, le lemme de Zorn garantit encore l'existence d'un élément maximal.

Relation d'ordre strict

On a vu qu'Ă  une relation d'ordre ≀ sur un ensemble E, on associait naturellement une relation < sur E, qui est alors une relation d'ordre strict, c'est-Ă -dire antirĂ©flexive (x < x n'est vrai pour aucun Ă©lĂ©ment x de E) et transitive.

Or toute relation d'ordre strict est antisymĂ©trique et mĂȘme asymĂ©trique (ce qui Ă©quivaut Ă  : antisymĂ©trique et antirĂ©flexive), c'est-Ă -dire que pour tous x et y :

x < y ⇒ non (y < x).

Par consĂ©quent, rĂ©ciproquement, Ă  toute relation d'ordre strict < sur E, on peut associer une relation d'ordre ≀ sur E en posant :

x ≀ y si et seulement si x < y ou x = y.

On vérifie facilement qu'en mettant bout à bout ces deux constructions, à partir d'un ordre ou d'un ordre strict, on retrouve la relation de départ. Choisir l'une ou l'autre des axiomatisations n'a donc pas d'importance en soi.

Pour un ordre strict, la totalité s'exprime ainsi :

∀ x, y ∈ E ( x < y ou x = y ou y < x ).

et l'on dit alors que c'est une relation d'ordre strict total[10]. Il n'y a pas de confusion possible avec la notion de relation totale, car les relations d'ordre strict sont antiréflexives, tandis que les relations totales sont réflexives.

Pour un ordre strict total, les trois possibilitĂ©s — x < y, x = y et y < x — sont exclusives, et l'on parle parfois, Ă  la suite de Cantor, de propriĂ©tĂ© de trichotomie.

Relation acyclique

La clĂŽture rĂ©flexive transitive d'une relation R est une relation d'ordre — ou encore : la clĂŽture transitive de R est antisymĂ©trique — si et seulement si R est acyclique.

La clĂŽture transitive de R est un ordre strict si et seulement si R est strictement acyclique, c'est-Ă -dire si son graphe est acyclique.

Négation (ou complémentaire) d'une relation d'ordre

La négation d'une relation binaire définie sur un ensemble est la relation de graphe le complémentaire de celui de dans . On la note . Dit autrement, deux éléments sont en relation par si et seulement s'ils ne le sont pas par .

Dire qu'un ordre est total, c'est dire que sa nĂ©gation est l'ordre strict inverse. C’est-Ă -dire qu'il y a Ă©quivalence pour un ordre entre :

  • est total ;
  • .

Par contre, dĂšs qu'il existe deux Ă©lĂ©ments distincts non comparables par un ordre, sa nĂ©gation ne peut ĂȘtre un ordre (strict ou large), car elle n'est pas antisymĂ©trique. La nĂ©gation d'un ordre non total n'est donc jamais un ordre.

Par exemple, la nĂ©gation de l'inclusion ⊄ sur l'ensemble des parties d'un ensemble d'au moins deux Ă©lĂ©ments n'est pas un ordre, car, si a ≠ b, on a toujours {a}≠{b} avec cependant {a}⊄{b} et {b}⊄{a}.

Ordre dual

L'ordre dual (ou ordre opposĂ©[11]) d'un ensemble ordonnĂ© P = (E, ≀) est l'ensemble ordonnĂ© Pop = (E, ≀op), oĂč ≀op est la relation d'ordre opposĂ©e de ≀, c'est-Ă -dire la relation ≄ (on utilise parfois * au lieu de op)[11] - [12].

Le bidual (Pop)op de P est Ă©gal Ă  P.

Préordre

Un préordre est une relation binaire réflexive et transitive.

Tout prĂ©ordre ℛ sur un ensemble E induit une relation d'ordre sur l'ensemble E quotientĂ© par la relation d'Ă©quivalence ~ dĂ©finie par « x~y si et seulement si (xℛy et yℛx) ».

Pour plus de précisions et des exemples, voir l'article détaillé.

Propriétés complémentaires

Compatibilité

La compatibilité d'une relation d'ordre avec une structure algébrique ne se définit qu'au cas par cas[13].

  • Un ordre ≀ sur un demi-groupe (G, +) est dit compatible si, pour tous x, y et z dans G tels que x ≀ y, on a x + z ≀ y + z et z + x ≀ z + y.
    Lorsque (G, +) est un groupe, on dit alors que (G, +, ≀) est un groupe ordonnĂ©, et qu'un Ă©lĂ©ment est positif s'il est supĂ©rieur Ă  l'Ă©lĂ©ment neutre.
    Tout groupe totalement ordonnĂ© archimĂ©dien est abĂ©lien et se plonge dans (ℝ, +, ≀).
  • Un anneau ou un corps (A, +, ×) est dit ordonnĂ© s'il est muni d'un ordre ≀ tel que (A, +, ≀) soit un groupe ordonnĂ© et que le produit de deux Ă©lĂ©ments positifs soit positif.
    Tout corps totalement ordonnĂ© archimĂ©dien se plonge dans (ℝ, +, ×, ≀).
    Dans un corps totalement ordonnĂ©, –1 n'est jamais un carrĂ© ni mĂȘme une somme de carrĂ©s.
  • Un espace vectoriel ordonnĂ© est un espace vectoriel rĂ©el (E, +, ∙) muni d'un ordre ≀ tel que (E, +, ≀) soit un groupe ordonnĂ© et que tout vecteur produit d'un rĂ©el positif par un vecteur positif soit positif.

Ensemble bien ordonné

Un ensemble ordonné est dit bien ordonné si tout sous-ensemble non vide de cet ensemble possÚde un plus petit élément.

Treillis

Un ensemble est appelé treillis s'il est ordonné et si tout couple d'éléments possÚde une borne supérieure et une borne inférieure.

Applications

Topologie de l'ordre

Un ensemble ordonnĂ© peut ĂȘtre muni de plusieurs topologies issues de l'ordre : la topologie de l'ordre, la topologie de l'ordre Ă  droite et la topologie de l'ordre Ă  gauche.

Liens avec les complexes simpliciaux

Une classe importante de complexes simpliciaux provient d'ensembles ordonnés finis. On définit le complexe d'ordre D(P) d'un ensemble ordonné fini P comme étant l'ensemble des chaßnes de P. Le complexe d'ordre est trivialement un complexe simplicial.

L'Ă©tude de l'ensemble ordonnĂ© en lui-mĂȘme donne des informations sur son complexe d'ordre, et il est donc intĂ©ressant d'Ă©tudier un complexe simplicial comme le complexe d'ordre d'un ensemble ordonnĂ©.

Notes et références

  1. N. Bourbaki, ÉlĂ©ments de mathĂ©matique : ThĂ©orie des ensembles [dĂ©tail des Ă©ditions], p. III.4.
  2. Bourbaki, p. III.5.
  3. (en) A. G. Kurosh, Lectures in General Algebra, Pergamon Press, (lire en ligne), p. 11.
  4. Bourbaki, p. III.22-23.
  5. Nathalie Caspard, Bruno Leclerc et Bernard Monjardet, Ensembles ordonnés finis : concepts, résultats et usages, Springer, (lire en ligne), p. 73.
  6. Bourbaki, p. III.7 et III.14.
  7. Gustave Choquet, Cours d'analyse, 1966, p. 23.
  8. (en) Steven Roman, Lattices and Ordered Sets, Springer, , 305 p. (ISBN 978-0-387-78900-2, lire en ligne), p. 13.
  9. Roman 2008, p. 284.
  10. Par exemple J. Riguet, « Relations binaires, fermetures, correspondances de Galois », Bull. Soc. Math. Fr., vol. 76,‎ , p. 114-155 (lire en ligne).
  11. (en) George Bergman, An invitation to general algebra and universal constructions, Cham, Springer, , 2e Ă©d. (1re Ă©d. 1988), 572 p. (ISBN 978-3-319-11478-1, lire en ligne), p. 113.
  12. Bourbaki, p. III.4 et III.77.
  13. Jean-Pierre Ramis, André Warusfel et al., Mathématiques Tout-en-un pour la Licence : Niveau L1, Dunod, , 2e éd. (lire en ligne), p. 37.

Voir aussi

Articles connexes

Bibliographie

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.