Ê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
Théorème d'extension de Szpilrajn
Résumé
En mathématiques, le théorème d'extension de Szpilrajn, démontré par Edward Szpilrajn, établit que tout ordre partiel est contenu dans un ordre total.
Intuitivement, le théorème dit qu'une comparaison entre éléments qui laisse quelques couples incomparables peut être étendue de telle manière que chaque élément est soit inférieur, soit supérieur à un autre. C'est l'un des nombreux exemples de l'utilisation de l'axiome du choix (sous la forme du lemme de Zorn) pour trouver un ensemble maximal avec certaines propriétés.
Une relation binaire R sur un ensemble S est formellement définie comme un ensemble de couples (x, y) d'éléments de S. La condition (x, y) ∈ R est généralement abrégée en xRy.
Une relation d'ordre (ou d'ordre partiel) sur S est une relation binaire réflexive (xRx pour tout x ∈ S), antisymétrique (xRy et yRx implique x = y) et transitive (xRy et yRz implique xRz).
Si elle est de plus totale (xRy ou yRx est vraie pour chaque couple (x, y) d'éléments de S), on dit que c'est un ordre total.
Une relation R est contenue dans une autre relation T lorsque chaque couple dans la première est aussi dans la seconde, lorsque xRy implique xTy.
Soit E l'ensemble (non vide) des ordres partiels sur S qui contiennent l'ordre donné R.
En ordonnant E par inclusion, on obtient un ensemble inductif. En effet, toute chaîne de E, toute partie C de E totalement ordonnée par cette relation d'inclusion, admet dans E un majorant : la réunion des éléments de C.
D'après le lemme de Zorn, E possède donc au moins un élément maximal Q.
Cet ordre Q sur S est total car sinon, il existerait dans S deux éléments Q-incomparables x et y, et l'on pourrait alors former un élément T de E contenant strictement Q (ce qui contredirait la maximalité de Q) : il suffirait de prendre pour T la clôture transitive de Q∪{(x,y)}. (T serait bien antisymétrique, du fait que Q∪{(x,y)} serait sans cycle.)
Kenneth Arrow a énoncé que tout préordre (relation réflexive et transitive) peut être étendu en un préordre total ; cette affirmation a été prouvée plus tard par Hansson.
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.