Théorème d'extension de Szpilrajn
En mathématiques, le théorème d'extension de Szpilrajn, démontré par Edward Szpilrajn[1], é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.
Définitions et énoncé
- 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, c.-à-d. lorsque xRy implique xTy.
Le théorème d'extension indique que toute relation d'ordre (partiel) R est contenue dans une relation d'ordre total T.
Démonstration
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, c.-à-d. 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.)
Autres théorèmes d'extension
- 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.
- Kotaro Suzumura (en) a prouvé qu'une relation binaire R peut être étendue pour former un préordre total si et seulement si elle est Suzumura-consistante c.-à-d. s'il n'existe pas de cycle d'éléments dans lequel xRy pour chaque couple (x, y) d'éléments consécutifs et dans lequel, pour au moins l'un de ces couples, yRx n'est pas vraie.
Notes et références
- E. Szpilrajn, « Sur l'extension de l'ordre partiel », Fund. Math., vol. 16, , p. 386-389 (lire en ligne).