Extension linéaire

Dans la branche des mathématiques de la théorie des ordres, une extension linéaire d'un ordre partiel est un ordre total (ou ordre linéaire) qui est compatible avec l'ordre partiel. Un exemple classique est l'ordre lexicographique des ensembles totalement ordonnés qui est une extension linéaire de leur ordre produit.

Définitions

É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.

Principe d'extension d'ordre

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,[Information douteuse] 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].

Résultats associés

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 (en), 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[pas clair], la conjecture 1/3-2/3 n'est pas vraie[12].

Références
  1. E. Szpilrajn, « Sur l'extension de l'ordre partiel », Fund. Math., vol. 16,‎ , p. 386-389 (lire en ligne).
  2. (en) Thomas Jech, The Axiom of Choice, Dover Publications, (1re éd. 1973) (ISBN 0-486-46624-8).
  3. (en) U. Felgner et J. K. Truss, « The Independence of the Prime Ideal Theorem from the Order-Extension Principle », Journal of Symbolic Logic, vol. 64, no 1,‎ , p. 199-215 (DOI 10.2307/2586759, JSTOR 2586759).
  4. (en) A. R. D. Mathias, « The order extension principle », dans Dana S. Scott et Thomas J. Jech, Axiomatic Set Theory (University of California, Los Angeles, Calif., July 10 – August 5, 1967), AMS, coll. « Proceedings of Symposia in Pure Mathematics » (no 13), , p. 179-183.
  5. (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein (2001), "Section 22.4: Topological sort", Introduction à l'algorithmique (2nd ed.), MIT Press, pp. 549–552, (ISBN 0-262-03293-7).
  6. (en) Brightwell, Graham R.; Winkler, Peter (1991), "Counting linear extensions", Order, 8 (3): 225–242, doi:10.1007/BF00383444
  7. (en) Bubley, Russ; Dyer, Martin (1999), "Faster random generation of linear extensions", Discrete Mathematics, 201: 81–88, doi:10.1016/S0012-365X(98)00333-1.
  8. (en) Peter C. Fishburn et W. T. Trotter (1992), "Linear extensions of semiorders: a maximization problem", Discrete Mathematics, 103 (1): 25–40, MR 1171114, doi:10.1016/0012-365X(92)90036-F.
  9. (en) Anders Björner et Günter M. Ziegler, « Introduction to Greedoids », dans Neil White, Matroid Applications, vol. 40, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications », (ISBN 978-0-521-38165-9), p. 284-357. Voir surtout item (1) p. 294.
  10. (en) S. S. Kislitsyn, « Finite partially ordered sets and their associated sets of permutations », Matematicheskiye Zametki, vol. 4,‎ , p. 511–518.
  11. (en) Graham R. Brightwell, « Balanced pairs in partial orders », Discrete Mathematics, vol. 201, nos 1-3,‎ , p. 25-52 (DOI 10.1016/S0012-365X(98)00311-2).
  12. (en) G. R. Brightwell, S. Felsner et W. T. Trotter, « Balancing pairs and the cross product conjecture », Order, vol. 12, no 4,‎ , p. 327-349 (DOI 10.1007/BF01110378, Math Reviews 1368815).
  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.