Relation d'ordre

Unerelation d'ordredans unensembleest unerelation binairedans cet ensemble qui permet de comparer sesélémentsde 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 unestructured'ordre ou tout simplement un ordre.
Une relation d'ordre est unerelation binaireréflexive,antisymétriqueettransitive:
soitE{\displaystyle E}un ensemble ; unerelation interne≤{\displaystyle \leq }surE{\displaystyle E}est une relation d'ordre si pour tousx,y,z∈E{\displaystyle x,y,z\in E}:
La forme même de ces axiomes permet d'affirmer que ces derniers sont également vérifiés par larelation binaire réciproque≥{\displaystyle \geq }, définie par
À toute relation d'ordre est donc associée une relation d'ordre opposée sur le même ensemble ; les formulesx≤y{\displaystyle x\leq y}ety≥x{\displaystyle y\geq x}se lisent indifféremment : «x{\displaystyle x}est inférieur ày{\displaystyle y}», ou «x{\displaystyle x}est plus petit quey{\displaystyle y}», ou «y{\displaystyle y}est supérieur àx{\displaystyle x}», ou «y{\displaystyle y}est plus grand quex{\displaystyle x}» (ou parfois «x{\displaystyle x}est au plus égal ày{\displaystyle y}», ou «y{\displaystyle y}est au moins égal àx{\displaystyle x}»).
On associe également à toute relation d'ordre≤{\displaystyle \leq }, une relation dite d’ordre strictnotée alors<{\displaystyle <}(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 :
La formulex<y{\displaystyle x<y}s'écrit aussiy>x{\displaystyle y>x}, et se lit : «x{\displaystyle x}est strictement inférieur ày{\displaystyle y}», ou «x{\displaystyle x}est strictement plus petit quey{\displaystyle y}», «y{\displaystyle y}est strictement supérieur àx{\displaystyle x}», ou «y{\displaystyle y}est strictement plus grand quex{\displaystyle x}».
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’ordrelarge.
Certaines relations d'ordre sont desrelationstotales, c'est-à-dire que deux éléments deE{\displaystyle E}sont toujourscomparables: pour tousx,y∈E,x≤y∨y≤x{\displaystyle x,y\in E,x\leq y\lor y\leq x}.
On dit alors que≤{\displaystyle \leq }est une relation d'ordre total, et que l'ensembleE{\displaystyle E}esttotalement ordonnépar cette relation. Une relation d'ordre surE{\displaystyle E}est ditepartiellesi elle n'est pas totale, etE{\displaystyle E}est alorspartiellement ordonné. Il est à noter qu'en anglais, on désigne parordre partielun ordre quelconque, qui peut donc être total. Cette terminologie est parfois également utilisée en français.
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'undiagramme de Hasse, de façon similaire à la représentation habituelle d'ungraphesur 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.
Si(E, ≤)et(F, ≼)sont deux ensembles ordonnés, une applicationfdeEdansFest ditecroissante(ou parfois croissante au sens large, ou isotone) quand elle conserve l'ordre,décroissante(au sens large), ou antitonequand elle inverse celui-ci, c'est-à-dire que :
Elle est ditestrictement croissantequand elle conserve l'ordre strict : pour tousxetydeE,x<y⇒f(x) ≺f(y),
etstrictement décroissantequand elle l'inverse : pour tousxetydeE,x<y⇒f(x) ≻f(y).
À noter que si une application croissante de(E, ≤)dans(F, ≼)estinjectivealors elle est strictement croissante, mais que laréciproqueest fausse en général (elle est vraie cependant si l'ordre surEest total).
Une applicationmonotoneou monotone au sens large (resp. strictement monotone) est une application croissante ou décroissante (resp. strictement croissante ou strictement décroissante).
Labijection réciproqued'unebijectioncroissantef: (E, ≤) → (F, ≼)n'est pas nécessairement croissante (prendre par exemplel'application identité, deE= ℝ muni de l'ordre d'égalitédansF= ℝ muni de l'ordre usuel). Elle l'est cependant si ≤ est total (sif(y1) ≥f(y2)alors, par croissance def,y1≽y2. Donc parcontraposée: siy1≺y2et si ≤ est total alorsf(y1) <f(y2)).
Unisomorphisme entre deux ensembles ordonnés(E, ≤)et(F, ≼)est une bijectionfdeEdansFqui est croissante et dont la réciproque est croissante, ce qui revient à dire quefest bijective et vérifie pour tousxetydeE:
Unplongementd'ensembles ordonnés de(E, ≤)dans(F, ≼)est une applicationfdeEdansFvérifiant pour tousxetydeE:
(une telle application est forcémentinjective). Les isomorphismes d'ordres sont donc les plongementssurjectifs.
Dans lacatégoriedes ensembles ordonnés, lesmorphismessont par définition les applications croissantes, et lesisomorphismessont, par conséquent, ceux introduits ci-dessus.
Dans un ensemble ordonnéE, il n'existe pas forcément deplus grand élément. SiEest fini, il contiendra (au moins) unélément maximal. SiEest unensemble inductifinfini, lelemme de Zorngarantit encore l'existence d'un élément maximal.
On a vu qu'à une relation d'ordre ≤ sur un ensembleE, on associait naturellement une relation < surE, qui est alors unerelation d'ordre strict, c'est-à-direantiréflexive(x<xn'est vrai pour aucun élémentxdeE) et transitive.
Or toute relation d'ordre strict estantisymétriqueet mêmeasymétrique(ce qui équivaut à : antisymétrique et antiréflexive), c'est-à-dire que pour tousxety:
Par conséquent, réciproquement, à toute relation d'ordre strict < surE, on peut associer une relation d'ordre ≤ surEen posant :
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 :
et l'on dit alors que c'est unerelation d'ordre strict total. Il n'y a pas de confusion possible avec la notion derelation 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=yety<x— sont exclusives, et l'on parle parfois, à la suite deCantor, depropriété detrichotomie.
Laclôture réflexive transitived'une relationRest une relation d'ordre — ou encore : laclôture transitivedeRest antisymétrique — si et seulement siRestacyclique.
La clôture transitive deRest un ordre strict si et seulement siRest strictement acyclique, c'est-à-dire si songraphe est acyclique.
La négation d'une relation binaireR{\displaystyle R}définie sur un ensembleA{\displaystyle A}est la relation de graphe lecomplémentairede celui deR{\displaystyle R}dansA×A{\displaystyle A\times A}. On la note⧸R{\displaystyle \not \!R}.
Dit autrement, deux éléments sont en relation par⧸R{\displaystyle \not \!R}si et seulement s'ils ne le sont pas parR{\displaystyle 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⩽{\displaystyle \leqslant }entre :
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, sia≠b, on a toujours {a}≠{b} avec cependant {a}⊄{b} et {b}⊄{a}.
L'ordre dual(ouordre opposé) d'un ensemble ordonnéP= (E, ≤) est l'ensemble ordonnéP= (E, ≤), où ≤est larelation d'ordre opposée de ≤, c'est-à-dire la relation ≥(on utilise parfois * au lieu de).
Le bidual (P)dePest égal àP.
Unpréordreest une relation binaireréflexiveettransitive.
Tout préordre ℛ sur un ensembleEinduit une relation d'ordre sur l'ensembleEquotientépar larelation d'équivalence~ définie par «x~ysi et seulement si (xℛyetyℛx)».
Pour plus de précisions et des exemples, voir l'article détaillé.
La compatibilité d'une relation d'ordre avec unestructure algébriquene se définit qu'au cas par cas.
Un ensemble ordonné est ditbien ordonnési toutsous-ensemblenonvidede cet ensemble possède unplus petit élément.
Un ensemble est appelétreilliss'il est ordonné et si tout couple d'éléments possèdeune borne supérieure et une borne inférieure.
Un ensemble ordonné peut être muni deplusieurs topologies issues de l'ordre: la topologie de l'ordre, la topologie de l'ordre à droite et la topologie de l'ordre à gauche.
Une classe importante decomplexes simpliciauxprovient d'ensembles ordonnés finis. On définit le complexe d'ordre D(P) d'un ensemble ordonné fini P comme étant l'ensemble deschaînesde P. Le complexe d'ordre esttrivialementun 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é.