Théorème d'extension de Szpilrajn

Théorème d'extension de Szpilrajn Dans la théorie de l'ordre, le théorème d'extension de Szpilrajn (également appelé principe d'extension de commande), prouvé par Edward Szpilrajn dans 1930,[1] stipule que tout ordre partiel strict est contenu dans un ordre total. Intuitivement, le théorème dit que toute méthode de comparaison d'éléments qui laisse certaines paires incomparables peut être étendue de telle manière que chaque paire devient comparable. Le théorème est l'un des nombreux exemples de l'utilisation de l'axiome de choix sous la forme du lemme de Zorn pour trouver un ensemble maximal avec certaines propriétés.

Contenu 1 Définitions et déclaration 2 Preuve 3 Autres théorèmes d'extension 4 Voir également 5 Références Définitions et énoncé Une relation binaire {style d'affichage R} sur un ensemble {style d'affichage X} est formellement défini comme un ensemble de paires ordonnées {style d'affichage (X,y)} d'éléments de {style d'affichage X,} et {style d'affichage (X,y)en R} est souvent abrégé en {style d'affichage xRy.} Une relation est réflexive si {style d'affichage xRx} vaut pour chaque élément {style d'affichage xin X;} il est transitif si {style d'affichage xRy{texte{ et }}yRz} impliquer {style d'affichage xRz} pour tous {style d'affichage x,y,Zine X;} il est antisymétrique si {style d'affichage xRy{texte{ et }}yRx} impliquer {style d'affichage x=y} pour tous {style d'affichage x,yin X;} et c'est une relation connexe si {style d'affichage xRy{texte{ ou }}yRx} tient pour tous {style d'affichage x,Yin X.} Une commande partielle est, par définition, un réflexif, relation transitive et antisymétrique. Un ordre total est un ordre partiel connexe.

Une relation {style d'affichage R} est contenu dans une autre relation {style d'affichage S} lorsque toutes les paires ordonnées dans {style d'affichage R} apparaissent également dans {style d'affichage S;} C'est, {style d'affichage xRy} implique {style d'affichage xSy} pour tous {style d'affichage x,Yin X.} Le théorème d'extension énonce que toute relation {style d'affichage R} c'est réflexif, transitif et antisymétrique (C'est, une commande partielle) est contenu dans une autre relation {style d'affichage S} qui est réflexif, transitif, antisymétrique et connexe (C'est, une commande totale).

Preuve Le théorème se démontre en deux étapes. Première, si une commande partielle ne se compare pas {style d'affichage x} et {style d'affichage y,} il peut être étendu en ajoutant d'abord la paire {style d'affichage (X,y)} puis effectuer la fermeture transitive, et deuxieme, puisque cette opération génère un ordre qui contient strictement celui d'origine et peut être appliqué à toutes les paires d'éléments incomparables, il existe une relation dans laquelle toutes les paires d'éléments ont été rendues comparables.

La première étape est démontrée comme un lemme préliminaire, dans lequel un ordre partiel où une paire d'éléments {style d'affichage x} et {style d'affichage y} sont incomparables est modifié pour les rendre comparables. Cela se fait en ajoutant d'abord la paire {style d'affichage xRy} à la relation, qui peut aboutir à une relation non transitive, puis en restaurant la transitivité en ajoutant toutes les paires {style d'affichage qRp} tel que {style d'affichage qRx{texte{ et }}yRp.} Cela se fait sur une seule paire d'éléments incomparables {style d'affichage x} et {style d'affichage y,} et produit une relation encore réflexive, antisymétrique et transitif et qui contient strictement celui d'origine.

On montre ensuite que le poset d'ordres partiels contenant {style d'affichage R,} classé par inclusion, a un élément maximal. L'existence d'un tel élément maximal est prouvée en appliquant le lemme de Zorn à ce poset. Une chaîne dans ce poset est un ensemble de relations contenant {style d'affichage R} tel que étant donné deux de ces relations, l'un est contenu dans l'autre.

Appliquer le lemme de Zorn, il faut montrer que toute chaîne a une borne supérieure dans le poset. Laisser {style d'affichage {mathématique {C}}} être une telle chaîne, et il reste à montrer que l'union de ses éléments, {style d'affichage bigcup {mathématique {C}},} est une borne supérieure pour {style d'affichage {mathématique {C}}} qui est dans le poset: {style d'affichage {mathématique {C}}} contient la relation d'origine {style d'affichage R} puisque chaque élément de {style d'affichage {mathématique {C}}} est un ordre partiel contenant {style d'affichage R.} Prochain, on montre que {style d'affichage bigcup {mathématique {C}}} est une relation transitive. Supposer que {style d'affichage (X,y)} et {style d'affichage (y,z)} sont dans {style d'affichage bigcup {mathématique {C}},} pour qu'il existe {style d'affichage S,Étain {mathématique {C}}} tel que {style d'affichage (X,y)en S{texte{ et }}(y,z)en t.} Depuis {style d'affichage {mathématique {C}}} est une chaîne, Soit {style d'affichage Ssubsetq T{texte{ ou }}Tsubseteq S.} Supposer {style d'affichage Ssubsetq T;} l'argument pour quand {style d'affichage Tsubseteq S} est similaire. Alors {style d'affichage (X,y)en t.} Puisque toutes les relations produites par notre processus sont transitives, {style d'affichage (X,z)} est dans {style d'affichage T} et donc aussi dans {style d'affichage bigcup {mathématique {C}}.} De la même manière, on peut montrer que {style d'affichage bigcup {mathématique {C}}} est antisymétrique.

Par conséquent, par le lemme de Zorn, l'ensemble des ordres partiels contenant {style d'affichage R} a un élément maximal {style d'affichage Q,} et il ne reste plus qu'à montrer que {style d'affichage Q} est totale. En effet si {style d'affichage Q} avait une paire d'éléments incomparables alors il est possible d'y appliquer le procédé de la première étape, menant à un autre ordre partiel strict qui contient {style d'affichage R} et contient strictement {style d'affichage Q,} contredire cela {style d'affichage Q} est maximal. {style d'affichage Q} est donc un ordre total contenant {style d'affichage R,} complétant la preuve.

Autres théorèmes d'extension Arrow a déclaré que chaque précommande (relation réflexive et transitive) peut être étendu à une précommande totale (relation transitive et connexe), et cette affirmation a ensuite été prouvée par Hansson.

Suzumura a prouvé qu'une relation binaire peut être étendue à un préordre total si et seulement si elle est cohérente avec Suzumura, ce qui signifie qu'il n'y a pas de cycle d'éléments tel que {style d'affichage xRy} pour chaque paire d'éléments consécutifs {style d'affichage (X,y),} et il y a une paire d'éléments consécutifs {style d'affichage (X,y)} dans le cycle pour lequel {style d'affichage yRx} ne tient pas.

Voir aussi Extension linéaire - Ordre mathématique d'un ordre partiel Références ^ Szpilrajn, Edouard (1930), "Sur l'extension de l'ordre partiel" (PDF), Fondamentaux des mathématiques (en français), 16: 386–389, est ce que je:10.4064/fm-16-1-386-389. Catégories: Axiome du choixThéorèmes dans les fondements des mathématiquesThéorie de l'ordre