Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Ordre total
Résumé
En mathématiques, on appelle relation d'ordre total sur un ensemble E toute relation d'ordre ≤ pour laquelle deux éléments de E sont toujours comparables, c'est-à-dire que
On dit alors que E est totalement ordonné par ≤.
Une relation binaire ≤ sur un ensemble E est un ordre total si (pour tous éléments x, y et z de E) :
x ≤ x (réflexivité) ;
si x ≤ y et y ≤ x, alors x = y (antisymétrie) ;
si x ≤ y et y ≤ z, alors x ≤ z (transitivité) ;
x ≤ y ou y ≤ x (totalité).
Les trois premières propriétés sont celles faisant de ≤ une relation d'ordre. La quatrième fait de cet ordre un ordre total.
L'ensemble des lettres d'un alphabet est totalement ordonné par un ordre alphabétique.
Tout corps euclidien, comme le corps R des réels, est muni d'un ordre total naturel : x ≤ y si et seulement si y – x est un carré.
Soient f : X → Y une injection, ≤ un ordre sur Y, et ≼ l'ordre induit sur X en posant : x1 ≼ x2 si et seulement si f(x1) ≤ f(x2). Si ≤ est total alors ≼ aussi. En particulier : toute restriction à une partie X de Y d'un ordre total sur Y est un ordre total sur X. Par exemple, toute partie de R est totalement ordonnée par la relation d'ordre usuelle.
Si un ordre ≤ sur E est total, alors l'ordre opposé ≥ sur E est total (la réciproque en résulte).
L'ordre lexicographique sur le produit cartésien d'un ensemble bien ordonné d'ensembles totalement ordonnés, est lui-même un ordre total ; par exemple, tout ensemble de mots est totalement ordonné par l'ordre alphabétique, et tout bon ordre est un ordre total.
Une chaîne d'un ensemble partiellement ordonné (E, ≤) est une partie de E sur laquelle l'ordre ≤ est total. Cette notion joue un rôle important en théorie des ensembles, par le lemme de Zorn.
On peut définir un ensemble totalement ordonné comme un treillis dans lequel {a∨b, a∧b} = {a, b} pour tous a, b ; on peut alors poser a ≤ b si et seulement si a = a∧b ; on démontre qu'un ordre total est aussi un treillis distributif.
D'après le théorème d'extension de Szpilrajn, tout ordre partiel ≤ sur un ensemble E est prolongeable en un ordre total sur E, appelé une extension linéaire de ≤.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.