« Relation d'ordre » : différence entre les versions

Navigation interactive dans l’historique

← Modification précédente Modification suivante →

Contenu supprimé Contenu ajouté

Intégrés

Version du 8 mars 2016 à 22:30

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, transitive et antisymétrique : soit E un ensemble et une relation binaire sur cet ensemble notée « ≤ », cette relation 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é)

De par la forme même de ces axiomes, ceux-ci sont vérifiés par la relation binaire réciproque ≥, qui est 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].

Une relation d'ordre au sens de la définition ci-dessus est parfois qualifiée d’ordre large.

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

x ≤ y ou y ≤ x.

On dit alors que la relation d'ordre est totale, 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

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.
La relation « est strictement inférieur à », par exemple sur l'ensemble des entiers naturels, n'est pas une relation d'ordre car elle n'est pas réflexive (une relation d'ordre strict n'est jamais un ordre large, sauf sur l'ensemble vide).
La relation d'inclusion, « est un sous-ensemble de » ou « est contenu dans », est une relation d'ordre partiel sur l'ensemble des parties d'un ensemble. Si l'ensemble donné est fini, son ensemble des parties est fini (plus précisément si un ensemble contient n éléments, son ensemble des parties en contient 2ⁿ). La figure ci-dessous représente le diagramme de Hasse d'un ensemble à 3 éléments.

La relation de divisibilité est une relation d'ordre partiel sur les entiers naturels, mais ce n'est pas une relation d'ordre sur les entiers relatifs car elle n'est pas antisymétrique : 1 divise –1 et –1 divise 1. La figure ci-dessous représente le diagramme de Hasse de la relation de divisibilité entre les entiers de 0 à 9.

L'ensemble des fonctions de ℝ dans ℝ, muni de la relation d'ordre f ≤ g si pour tout réel x, f(x) ≤ g(x), est un ensemble partiellement ordonné infini. Intuitivement, une fonction est plus petite qu'une autre si sa courbe est toujours en dessous de l'autre courbe. On peut généraliser cet exemple aux fonctions d'un ensemble X dans un ensemble ordonné P.
L'ensemble des partitions d'un ensemble donné est partiellement ordonné, avec la relation d'ordre donnée par le raffinement des partitions : par définition, une partition est plus fine qu'une autre si elle fractionne les parties de l'autre en de plus petites parties.
Étant donnés deux ensembles ordonnés E et F, il y a au moins deux façons naturelles de définir un ordre sur E×F.
- L'ordre produit : (x, y) ≤ (x’, y’) si et seulement si x ≤ x’ et y ≤ y’.
- L'ordre lexicographique : (x, y) ≤ (x’, y’) si et seulement si [x < x’ ou [x = x’ et y ≤ y’]].Si les ordres initiaux sont totaux, l'ordre lexicographique est aussi total (mais pas en général l'ordre produit). Par exemple la relation ≤ définie sur l'ensemble des complexes parx ≤ y si et seulement si Re(x) < Re(y) ou Re(x) = Re(y) et Im(x) ≤ Im(y)est une relation d'ordre total. Elle n'est cependant pas compatible avec la structure de corps de l'ensemble des complexes.
On peut munir l'ensemble ℝ[X₁, … , X_n] des polynômes à n variables d'une relation d'ordre partielle. On commence par comparer les monômes unitaires à n variables via l'ordre lexicographique induit par X₁ < X₂ < … < X_n (cet ordre lexicographique est total). On compare deux polynômes P et Q en disant que P est strictement plus petit que Q si tout monôme non nul de P est strictement plus petit que tout monôme non nul de Q.^{[réf. souhaitée]} Cette relation d'ordre sur les polynômes est partielle.
On ne peut définir de façon satisfaisante une relation d'ordre sur le cercle qui signifierait « est placé avant ». Par exemple, sur l'ensemble des points du cercle trigonométrique (de centre O), la relation entre deux points M et N définie par « la mesure principale de l'angle ([OM),[ON)) est positive ou nulle » n'est pas une relation d'ordre car elle n'est pas transitive.
La relation « est le père de » sur un ensemble de personnes n'est pas une relation d'ordre car elle n'est ni transitive ni réflexive.

Notions associées

Applications croissantes

Si (E, ≤_E) et (F, ≤_F) sont deux ensembles ordonnés, une application f de E dans F est dite croissante (ou parfois croissante au sens large) quand elle conserve l'ordre, décroissante (au sens large) quand elle inverse celui-ci, c'est-à-dire que :

f est croissante quand pour tous x et y de E, x ≤_E y ⇒ f(x) ≤_F f(y).

f est décroissante quand pour tous x et y de E, x ≤_E y ⇒ f(x) ≥_F f(y).

Quand elle conserve l'ordre strict elle est strictement croissante : pour tous x et y de E, x <_E y ⇒ f(x) <_F f(y),

et strictement décroissante quand elle l'inverse : pour tous x et y de E, x <_E y ⇒ f(x) >_F f(y).

À noter qu'une application injective croissante est nécessairement strictement croissante.

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).

Un isomorphisme entre deux ensembles ordonnés $(E, \leq)$ et $(F, \leq)$ est une bijection $φ$ de $E$ dans $F$ qui est croissante et dont la réciproque est croissante, ce qui revient à dire que $φ$ est bijective et vérifie pour tous x et y de E :

x \leq y \Leftrightarrow φ(x) \leq φ(y)

^[3]

Un plongement d'ensembles ordonnés de $(E, \leq)$ dans $(F, \leq)$ est une injection $φ$ vérifiant pour tous x et y de E :

x \leq y \Leftrightarrow φ(x) \leq φ(y)

(une application φ vérifiant cette propriété est forcément injective). Un plongement surjectif est alors évidemment un isomorphisme d'ordres^[3].

La catégorie des ensembles ordonnés a pour morphismes les applications croissantes entre deux ensembles ordonnés^[4], dit autrement une application croissante et alors un morphisme d'ordres.

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 donné, on associait naturellement une relation « < », dite d’ordre strict, définie sur le même ensemble, et obtenue en restreignant celle-ci aux couples d'éléments distincts. Il est tout à fait possible d'axiomatiser directement la notion d'ordre strict. Cela peut même s'avérer plus naturel dans certains cas.

Une relation d'ordre strict est une relation binaire irréflexive, et transitive : soit E un ensemble et une relation binaire sur cet ensemble notée <, cette relation est une relation d'ordre strict si et seulement si pour tous x, y et z éléments de E :

non (x < x) (irréflexivité)
(x < y et y < z) ⇒ x < z (transitivité)

On déduit immédiatement de ces deux propriétés qu'une relation d'ordre strict est antisymétrique. À dire vrai une relation d'ordre strict est antisymétrique en un sens plus fort qu'une relation d'ordre large, c’est-à-dire que pour tous x et y de l'ensemble support E :

x < y ⇒ non (y < x) (antisymétrie « forte »)

Cependant pour une relation irréflexive, comme les ordres stricts, cette propriété est équivalente à la propriété d'antisymétrie définie pour les ordres larges. Il n'y a donc pas d'inconvénient à parler d'antisymétrie dans les deux cas.

De même qu'à une relation d'ordre (large) on associait une relation d'ordre strict, à une relation d'ordre strict, soit « < », on associe naturellement une relation d'ordre large, soit « ≤ », définie par :

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

Choisir l'une ou l'autre des axiomatisations n'a pas d'importance en soi. Dans les deux cas on a défini un ordre large et un ordre strict associés. En effet on vérifie facilement, en utilisant les propriétés de l'égalité, que :

La relation d'ordre strict associée à une relation d'ordre large (transitive, réflexive et antisymétrique) vérifie bien les axiomes d'ordre stricts (elle est transitive et irréflexive).
La relation d'ordre large associée à une relation d'ordre strict (transitive et irréflexive) vérifie bien les axiomes d'ordre large (elle est transitive, réflexive et antisymétrique).
Il y a bien symétrie : étant données une relation d'ordre strict « < », et une relation d'ordre large « ≤ », « < » est associée à « ≤ » si et seulement si « ≤ » est associée à « < ».

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

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

et on dit alors que c'est une relation d'ordre strict total^[5]. Il n'y a pas de confusion possible avec le sens précédent de relation totale, car une relation d'ordre strict, qui est irréflexive, ne peut être totale au sens où l'est un ordre large.

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.

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

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

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 $\leqslant \,$ entre :

$\leqslant \,$ est total ;
$x\not \leqslant y\iff y<x$

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 opposé) d'un ensemble ordonné P = (E, ≤) est l'ensemble ordonné P^op = (E, ≤^op), où ≤^op est la relation d'ordre opposée de ≤, c'est-à-dire la relation ≥ (on utilise parfois * au lieu de ^op)^[6]^,^[7].

Le bidual (P^op)^op de P est égal à P.

Préordre

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

On peut le considérer comme une relation d’ordre dans laquelle on autoriserait les cycles non triviaux (c’est-à-dire des cycles de plus d’un élément). Ajouter la condition d'antisymétrie rend impossible la présence de ces cycles non triviaux.

Tout quotient d'un préordre par la relation d'équivalence qu'il engendre est un ordre.

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^[8].

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é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

↑ N. Bourbaki, Éléments de mathématique : Théorie des ensembles [détail des éditions], p. III.4.
↑ Bourbaki, p. III.5.
↑ ^{a et b} Steve Roman, Lattices and Ordered Sets, Springer, 2008 (ISBN 978-0-387-78900-2), p 13.
↑ Roman 2008, p. 286.
↑ Par exemple J. Riguet, « Relations binaires, fermetures, correspondances de Galois », Bulletin de la Société Mathématique de France, vol. 76,‎ 1948, p. 114-155 (lire en ligne) p 139.
↑ (en) George BergmanGeorge Bergman, An Invitation to General Algebra and Universal Constructions, Springer, 2015, 2^e éd. (1^re éd. 1988) (ISBN 978-3-31911478-1, présentation en ligne, lire en ligne), p. 121.
↑ Bourbaki, p. III.4 et III.77.
↑ Jean-Pierre Ramis, André Warusfel et al., Mathématiques Tout-en-un pour la Licence - Niveau L1, Dunod, 2013, 2^e éd. (lire en ligne), p. 37.

Voir aussi

Sur les autres projets Wikimedia :

comparabilité, sur le Wiktionnaire
Relations en mathématiques, sur Wikiversity

Articles connexes

Antichaîne
Corps ordonné
Correspondance de Galois
Idéal (théorie des ordres)
Ordre cycliqueOrdre cyclique
Ordre partiel complet
Section commençante
Théorème d'extension de SzpilrajnThéorème d'extension de Szpilrajn

Bibliographie

Nathalie Caspard, Bruno Leclerc et Bernard Monjardet, Ensembles ordonnés finis : concepts, résultats et usages, Springer, 2007 (lire en ligne)
(en) Richard P. Stanley, Enumerative Combinatorics, vol. 1 [détail des éditions] (présentation en ligne)
(en) Efe A. Ok, Order Theory and its Applications (lire en ligne)

Portail des mathématiques

[1] N. Bourbaki, Éléments de mathématique : Théorie des ensembles [détail des éditions], p. III.4.

[2] Bourbaki, p. III.5.

[Roman13-3] {a et b} Steve Roman, Lattices and Ordered Sets, Springer, 2008 (ISBN 978-0-387-78900-2), p 13.

[4] Roman 2008, p. 286.

[5] Par exemple J. Riguet, « Relations binaires, fermetures, correspondances de Galois », Bulletin de la Société Mathématique de France, vol. 76,‎ 1948, p. 114-155 (lire en ligne) p 139.

[6] (en) George BergmanGeorge Bergman, An Invitation to General Algebra and Universal Constructions, Springer, 2015, 2^e éd. (1^re éd. 1988) (ISBN 978-3-31911478-1, présentation en ligne, lire en ligne), p. 121.

[7] Bourbaki, p. III.4 et III.77.

[8] Jean-Pierre Ramis, André Warusfel et al., Mathématiques Tout-en-un pour la Licence - Niveau L1, Dunod, 2013, 2^e éd. (lire en ligne), p. 37.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Ligne 53 : / Ligne 53 : @@
 À noter qu'une application injective croissante est nécessairement strictement croissante.
-Les [[Morphisme|morphismes]] d'ordres sont les applications croissantes.
 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).
+Un isomorphisme entre deux ensembles ordonnés {{math|(''E'', ≤)}} et  {{math|(''F'', ≤)}} est une [[bijection]] {{math|φ}} de {{math|''E''}} dans {{math|''F''}} qui est croissante et dont la réciproque est croissante, ce qui revient à dire que {{math|φ}} est bijective et vérifie pour tous ''x'' et ''y'' de ''E'' :
+: {{math|''x''  ≤ ''y'' ⇔ φ(''x'') ≤ φ(''y'')}}<ref name="Roman13">{{ouvrage|prénom=Steve|nom=Roman|titre=Lattices and Ordered Sets|année=2008|éditeur=Springer|isbn=978-0-387-78900-2}}, p 13.</ref>
+Un plongement d'ensembles ordonnés  de{{math|(''E'', ≤)}} dans {{math|(''F'', ≤)}} est une [[injection (mathématiques)|injection]] {{math|φ}} vérifiant pour tous ''x'' et ''y'' de ''E'' :
+: {{math|''x''  ≤ ''y'' ⇔ φ(''x'') ≤ φ(''y'')}}
+(une application φ vérifiant cette propriété est forcément injective). Un plongement [[surjection|surjectif]] est alors évidemment un isomorphisme d'ordres<ref name="Roman13"/>.
+La [[théorie des catégories|catégorie]] des  ensembles ordonnés a pour [[Morphisme|morphismes]] les applications croissantes entre deux ensembles ordonnés<ref>{{harvsp|Roman|2008|p=286}}.</ref>, dit autrement une application croissante et alors un morphisme d'ordres.
 ===[[Plus grand élément]] et [[élément maximal]]===