Extension linéaire

Étant donnés des ordres partiels quelconques ≤ et ≤^* sur un ensemble X, ≤^* est une extension linéaire de ≤ si et seulement si (1) ≤^* est un ordre total et (2) pour tout x et y dans X, si x ≤ y, alors x ≤^* y. C'est cette deuxième propriété qui conduit les mathématiciens à décrire ≤^* comme une extension de ≤.

De façon équivalente, une extension linéaire peut être considérée comme une bijection croissante d'un ensemble partiellement ordonné vers un ordre total sur le même ensemble.

L'affirmation que tout ordre partiel peut être étendu en un ordre total est connu comme le principe d'extension d'ordre. Une preuve utilisant l'axiome du choix a d'abord été publiée par Edward Marczewski en 1930 : voir Théorème d'extension de Szpilrajn. Marczewski a écrit que le théorème avait déjà été prouvé par Stefan Banach, Kazimierz Kuratowski et Alfred Tarski, en utilisant également l'axiome du choix, mais que les preuves n'avaient jamais été publiées[1].

Dans la théorie des ensembles axiomatique moderne, le principe d'extension d'ordre est lui-même pris comme un axiome, de même statut ontologique que l'axiome du choix. Le principe d'extension d'ordre est impliqué par le théorème de l'idéal premier dans une algèbre de Boole ou le théorème de compacité (équivalent)[2], mais la réciproque est fausse[3] .

L'application du principe d'extension d'ordre à un ordre partiel dans lequel chaque couple d'éléments sont incomparables montre que (en vertu de ce principe) tout ensemble peut être totalement ordonné. Cette affirmation est connue sous le nom de « principe de classement », OP, et c'est une version faible du théorème de Zermelo. Cependant, il existe des modèles de la théorie des ensembles dans lesquels le principe de classement est vrai alors que le principe d'extension d'ordre ne l'est pas[4].

Le principe d'extension d'ordre est démontrable de manière constructive pour des ensembles finis à l'aide d'algorithmes de tri topologique, où l'ordre partiel est représenté par un graphe orienté acyclique avec ses sommets les éléments de l'ensemble. Plusieurs algorithmes peuvent trouver un prolongement en temps linéaire[5]. En dépit de la facilité à trouver une seule extension linéaire, le problème du comptage de toutes les extensions linéaires d'un ordre partiel fini est #P-complet; cependant, il peut être estimé par un schéma d'approximation en temps polynomial[6] - [7]. Parmi tous les ordres partiels avec un nombre fixé d'éléments et un nombre fixé de paires comparables, les ordres partiels qui ont le plus grand nombre d'extensions linéaires sont des semi-ordres (en)[8].

La dimension d'un ordre partiel est la cardinalité minimum d'un ensemble d'extensions linéaires dont l'intersection est l'ordre partiel donné ; de manière équivalente, c'est le nombre minimum d'extensions linéaires nécessaires pour s'assurer que chaque couple critique de l'ordre partiel est inversé dans au moins une des extensions.

Les antimatroïdes (en) peuvent être considérés comme la généralisation des ordres partiels ; de ce point de vue, les structures correspondant aux extensions linéaires d'un ordre partiel sont les mots de base de l'antimatroïde[9].

Ce domaine comprend également un des problèmes ouverts de la théorie des ordres le plus célèbre, la conjecture 1/3-2/3, qui prétend que dans tous les ensembles finis partiellement ordonnés P n'étant pas totalement ordonnés, il existe un couple (x,y) d'éléments de P pour lequel les extensions linéaires de P dans lesquelles x < y constituent entre 1/3 et 2/3 du nombre total des extensions linéaires de P[10] - [11]. De manière équivalente, si l'on choisit une extension linéaire de P uniformément au hasard, il existe un couple (x, y) qui a une probabilité entre 1/3 et 2/3 d'être ordonné de manière que x < y. Toutefois, pour certains ensembles infinis partiellement ordonnés, avec une probabilité canonique définie sur leurs extensions linéaires comme une limite des probabilités pour des ordres partiels finis qui couvrent l'ordre partiel infini, la conjecture 1/3-2/3 n'est pas vraie[12].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Linear extension » (voir la liste des auteurs).