Loading AI tools
Relation binaire transitive, réflexive et antisymétrique, permettant de comparer des éléments, des ensembles De Wikipédia, l'encyclopédie libre
Une relation d'ordre dans un ensemble est une relation binaire dans cet ensemble qui permet de comparer ses éléments 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.
Une relation d'ordre est une relation binaire réflexive, antisymétrique et transitive : soit un ensemble ; une relation interne sur est une relation d'ordre si pour tous :
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
À toute relation d'ordre est donc associée une relation d'ordre opposée sur le même ensemble ; les formules et se lisent indifféremment : « est inférieur à », ou « est plus petit que », ou « est supérieur à », ou « est plus grand que » (ou parfois « est au plus égal à », ou « est au moins égal à »)[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 :
La formule s'écrit aussi , et se lit : « est strictement inférieur à », ou « est strictement plus petit que », « est strictement supérieur à », ou « est strictement plus grand que »[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 sont toujours comparables : pour tous . On dit alors que est une relation d'ordre total, et que l'ensemble est totalement ordonné par cette relation. Une relation d'ordre sur est dite partielle si elle n'est pas totale, et 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.
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.
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 :
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 :
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 :
(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.
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.
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 :
Par conséquent, réciproquement, à toute relation d'ordre strict < sur E, on peut associer une relation d'ordre ≤ sur E en 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 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.
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.
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 :
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}.
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.
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é.
La compatibilité d'une relation d'ordre avec une structure algébrique ne se définit qu'au cas par cas[13].
Un ensemble ordonné est dit bien ordonné si tout sous-ensemble non vide de cet ensemble possède un plus petit élément.
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.
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.
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é.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.