Utilisateur:ManiacParisien/Brouillons/Math-6

En mathématiques, et notamment en combinatoire, en théorie des ordres et en informatique théorique, un bon préordre ou bon quasi-ordre (en anglais well quasi-order ou wqo) est un préordre (relation réflexive et transitive) $\leq$ qui possède la propriété supplémentaire suivante : pour toute suite $x_{0},x_{1},\ldots ,x_{n},\ldots$ d'éléments de $E$, il existe deux entiers $i<j$ tels que $x_{i}\leq x_{j}$. pour toute suite $x_{0},x_{1},\ldots ,x_{n},\ldots$ d'éléments de $E$, il existe deux entiers $i<j$ tels que $x_{i}\leq x_{j}$. Ceci équivaut aux deux conditions suivantes :

• il n'existe pas de suite infinie strictement décroissante (c'est une relation bien fondée) et
• il n'existe pas d'ensemble infini d'éléments deux-à-deux incomparables (c'est une relation sans antichaîne infinie).

Un ensemble muni d'un bon préordre est dit bien préordonné. Lorsque le préordre est un ordre, on parle de bel ordre, ou de bon ordre partiel. Lors la relation est un ordre total, on l'appelle un bon ordre. Un bon ordre est donc toujours un ordre total dans la terminologie francophone.

Les résultats les plus importants concernent des propriétés d'existence de bons préordres. Ces résultats sont le Lemme de Higman sur les suites finies, le Théorème de Kruskal sur les arbres, et le Théorème de Robertson-Seymour sur les graphes. Ce sont des théorèmes de transfert de bons préordres à des structures plus complexes.

Les applications des bons préordres sont multiples. Il sont utilisés dans des raisonnement de récurrence transfinie, il s'emploient dans des preuves de terminaison dans les systèmes de réécriture, dans le model checking, et dans des caractérisations de certaines familles de langages formels.

Dans certains cas, notamment pour l'étude de suites infinies ou de graphes infinis, la notion de bon préordre est insuffisante. Elle a été étendue en le concept de meilleur préordre (en anglais better quasi-order (en) ou bqo).

Motivation

Un bon préordre est en particulier une relation bien fondée. Dans un ensemble muni d'une relation bien fondée, chaque élément admet un rang construit par induction transfinie ; ce rang permet des démonstrations par récurrence transfinie. Toutefois, la classe des relations bien fondées n'est pas fermée pour certaines opérations naturelles. En imposant une condition supplémentaire sur la relation de départ, on peut obtenir une relation bien fondée.

Ceci est le cas du passage au sous-ensembles d'un ensemble. À partir d'un préordre $\leq$ sur un ensemble $X$, on peut définir un préordre noté $\leq ^{+}$ sur l'ensemble $P(X)$ des parties de $X$ en posant $A\leq ^{+}B$ si et seulement si pour tout élément de $A$ il existe un élément de $B$ qui est plus grand pour la relation $\leq$. On constate que ce préordre sur $P(X)$ n'est pas nécessairement bien fondé, mais si l'ordre de départ est un bon préordre, alors le nouveau préordre l'est également.

Définition

Un bon préordre ou bon quasi-ordre sur un ensemble $E$ est un préordre (relation réflexive et transitive) $\leq$ sur $E$ qui possède la propriété supplémentaire suivante : pour toute suite $x_{0},x_{1},\ldots ,x_{n},\ldots$ d'éléments de $E$, il existe deux entiers $i<j$ tels que $x_{i}\leq x_{j}$.

Il est de coutume de dire qu'une suite $x_{0},x_{1},\ldots ,x_{n},\ldots$ d'éléments de $E$ est bonne pour $\leq$ s'il existe deux entiers $i<j$ tels que $x_{i}\leq x_{j}$. Ainsi, dans un bon préordre toutes les suites sont bonnes pour ce préordre. Une suite est parfaite si $x_{0}\leq x_{1}\leq \cdots \leq x_{n}\leq \cdots$. On peut montrer que, de toute bonne suite, on peut extraire une sous-suite parfaite.

Un bel ordre est un bon préordre qui est antisymétrique. Un bon ordre est un bel ordre qui est total. Un bon préordre peut être total ou non. En anglais, un bon préordre total se dit prewellordering.

Plusieurs formulations équivalentes existent pour la notion de bon préordre. Parmi celles-ci la plus utilisée est la suivante : un préordre est un bon préordre si et seulement il n'y a pas de suite infinie strictement décroissante (c'est une relation bien fondée) et il n'y a pas d'ensemble infini d'éléments deux-à-deux incomparables (pas antichaîne infinie).

Il est important de noter que, dans le cas d'un préordre noté $\leq$, le préordre strict associé, noté $<$, est défini par : $x<y\iff x\leq y\land y\not \leq x$. La condition $y\neq x$, usuelle dans le cas des ordres, doit être remplacée par $y\not \leq x$.

Exemples

• L'ensemble $(\mathbb {N} ,\leq )$ des entiers naturels, pour l'ordre usuel, et bien ordonné. Par contre, l'ensemble $(\mathbb {Z} ,\leq )$ des entiers relatifs ne l'est pas, puis qu'il n'est pas bien fondé.
• L'ensemble $(\mathbb {Z} ,\leq ')$ des entiers relatif, muni de la relation $x\leq 'y$ si et seulement si $|x|\leq |y|$. C'est un bon préordre, sans être un ordre.
• L'ensemble $(\mathbb {N} ,\mid )$ des entiers naturels ordonné par divisibilité n'est pas bien ordonnée puisque les nombres premiers forment une antichaîne infinie.
• L'ensemble $(\mathbb {N} ^{k},\leq )$ des $k$-uplets d'entiers naturels muni de l'ordre produit est bien ordonné (c'est le Lemme de DicksonLemme de Dickson). Plus généralement, si $(X,\leq )$ est bien préordonné, alors $(X^{k},\leq ^{k})$ est aussi bien préordonné pour tout $k$.
• Soit $X$ un ensemble fini ayant au moins deux éléments, muni d'un ordre. L'ensemble $X^{*}$ de tous les mots finis sur $X$, ordonné par ordre lexicographique (comme dans un dictionnaire) n'est pas bien ordonné, parce qu'il contient des suites décroissantes infinies, comme $b,ab,aab,aaab,\dots$. De même, $X^{*}$ muni de l'ordre préfixe n'est pas bien ordonnée parce que la suite précédente est une antichaîne infinie pour cet ordre partiel. En revanche, l'ensemble $X^{*}$ est bien ordonné pour la relation « être sous-mot ». (Si $X$ n'a qu'un seul élément, ces ordres coïncident.)
• Dans l'ensemble des parties finies non vides d'un ensemble $X$, la relation $A\leq B$ s'il existe une injection de $A$ dans $B$ est un préordre sans être un ordre. Ce préordre est bien fondé. Les singletons sont deux-à-deux incomparables, et le préordre est donc bon si et seulement si $X$ est lui-même fini.
• Dans un graphe orienté, la relation « être accessible depuis » est un préordre. Ce préordre est bien fondé si et seulement s'il n'existe pas de chemin infini les sommets sont pas dans des composantes composantes fortement connexes distinctes .

Définition équivalentes

Soit $X$ un ensemble préordonné par la relation $\leq$. Nous avons besoin des notions suivantes. Un segment initial (resp. segment final) de $X$ est une partie $S$ de $X$ fermée inférieurement (resp. supérieurement) c'est-à-dire telle que si $s$ est dans $S$ et $t\leq s$ (resp. $s\leq t$) alors $t$ est dans $S$. Une base de $S$ est un ensemble d'éléments minimaux et incomparables de $S$.

Théorème (Higman). Les propriétés suivantes sont équivalentes pour un préordre sur un ensemble $X$ :

1. le préordre un bon préordre ;
2. le préordre est bien fondé et n'admet pas d'antichaîne infinie ;
3. toute suite contient une sous-suite parfaite ;
4. toute extension linéaire de l'ordre associé est un bon ordre ;
5. tout sous-ensemble de $X$ a une base finie (« propriété de la base finie ») ;
6. il n'y a pas de suite strictement croissante de segments terminaux pour la relation d'inclusion ;
7. il n'y a pas de suite strictement décroissante de segments initiaux pour la relation d'inclusion.

Propriétés élémentaires

Produit cartésien

Si X et Y sont deux ensembles bien préordonnés, alors le produit cartésien X\times Y est bien préordonnée par la relation produit.

Ensemble des parties finies

Soit $(X,\leq )$ un ensemble bien préordonné, on peut définir un préordre $\leq ^{+}$ sur l'ensemble $P(X)$ des parties de $X$ en posant $A\leq ^{+}B$ si et seulement si pour tout élément de $A$ il existe un élément de $B$ qui est plus grand pour la relation $\leq$. Ce préordre sur $P(X)$ est bon si l'ordre de départ est un bon préordre.

Propriétés fondamentales

Lemme de Higman

Ce lemme dit que l'ensemble $(X^{*},\leq )$ des mots sur un ensemble fini $X$ préordonné par l'opération de division, aussi appelé plongement est bien préordonné si et seulement si $(X,\leq )$ est bien préordonné.

Un mot $x=a_{1}a_{2}\cdots a_{n}$, où les $a_{i}$ sont dans $X$, divise un mot $y$ si $y$ peut s'écrire $y=z_{0}b_{1}z_{1}b_{2}\cdots b_{n}z_{n}$, où $z_{0},\ldots ,z_{n}$ sont des mots, $b_{1},\ldots ,b_{n}$ sont dans $X$, et $a_{i}\leq b_{i}$ pour $i=1,\ldots ,n$. Si l'ordre sur $X$ est l'égalité, alors $x$ divise $y$ si et seulement $x$ est un sous-mot de $y$. La relation de division se dit aussi domination.
L'extension du lemme aux suites infinies n'est pas possible sans condition supplémentaire. L'ensemble $(X^{\omega },\leq )$ des mots infinis sur un ensemble bien préordonné $(X,\leq )$, ordonné par domination, n'est en général pas bien préordonné. En d'autres termes, me lemmme de Higman n'est plus vrai pour les mots infinis. En vue de la généralisation le concept de meilleur préordre (en) (better quasi ordering en anglais) a été introduit.

Théorème de Kruskal

Ce théorème dit que l'ensemble des arbres finis avec des sommets étiquetés par des éléments d'un ensemble bien préordonné $X$ est bien préordonné pour l'ordre de plongement.

Théorème de Nash-Williams

Le plongement d'arbres infinis étiquetés par des éléments d'un ensemble bien préordonné est un bon préordre

Théorème de Laver

Le plongement de types d'ordre linéaires dispersés est un bon préordre.

Plongement d'algèbres de Boole

Le plongement d'algèbres de Boole énombrables est un bon préordre.

Théorème de Robertson-Seymour

Le théorème du mineur exclu utilise la notion de mineur. Sur l'ensemble des graphes finis, la relation « être un mineur » est un bon préordre.

Autres résultats

Les graphes de profondeur arborescente finie, ordonnés par la relation de sous-graphe induit, forment un ensemble bien préordonné, ainsi que les co-graphes ordonnés par la relation de sous-graphe induit.

Bon préordre et bel ordre

Dans de nombreux cas, comme la plupart des exemples donnés plus haut, le préordre est en fait un ordre. L'avantage de manipuler des préordres est que l'on n'a pas à vérifier l'antisymétrie.

Un bon préordre donne un bel ordre par passage aux classes de l'équivalence associée (deux éléments $x$ et $y$ sont équivalent si $x\leq y$ et $y\leq x$). Par exemple, si l'on préordonne $\mathbb {Z}$ par la relation de divisibilité, on obtient que $n\equiv m$ si et seulement si $n=\pm m$, de sont que l'ensemble quotient est $\mathbb {N}$.

Annexes

Articles connexes

• bon ordre
• bel ordre
• better-quasi-ordering (en)
• prewellordering (en)

Bibliographie

• Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008 (ISBN 978-2-7117-2077-4)
• Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003 (ISBN 978-2-7117-4807-5)
• (en) Reinhard Diestel, Graph Theory, Springer, 2005 (lire en ligne), chap. 12 (« Minors, Trees, and WQO »), p. 326–367
• (en) Thomas Forster, « An Introduction to WQO and BQO Theory : Preliminary Version », CDMTCS Research Report Series, Cambridge University, Centre for Discrete Mathematics and Theoretical Computer Science, n^o CDMTCS-250,‎ septembre 2003 (lire en ligne)

Articles historiques

• Leonard E. Dickson, « Finiteness of the odd perfect and primitive abundant numbers with r distinct prime factors », American Journal of Mathematics, vol. 35, n^o 4,‎ 1913, p. 413–422 (DOI 10.2307/2370405, JSTOR 2370405)
• Graham Higman, « Ordering by divisibility in abstract algebras », Proc. London Math. Soc., 3rd series, vol. 2,‎ 1952, p. 326–336 (DOI 10.1112/plms/s3-2.1.326)
• Joseph B. Kruskal, « The theory of well-quasi-ordering: A frequently discovered concept », Journal of Combinatorial Theory, vol. 13, n^o 3,‎ 1972, p. 297–305 (DOI 10.1016/0097-3165(72)90063-5)
• (en) Eric C. Milner, « Basic WQO- and BQO-theory », dans Ivan Rival (éditeur), Graphs and Order : The Role of Graphs in the Theory of Ordered Sets and Its Applications, D. Reidel Publishing Co, coll. « NATO ASI Series » (n^o 147), 1985 (ISBN 90-277-1943-8), p. 487–502
• Jussi Ketonen, « The structure of countable Boolean algebras », Annals of Mathematics, vol. 108, n^o 1,‎ 1978, p. 41–89 (DOI 10.2307/1970929, JSTOR 1970929)
• Jean H. Gallier, « What's so special about Kruskal's theorem and the ordinal Γo? A survey of some results in proof theory », Annals of Pure and Applied Logic, vol. 53, n^o 3,‎ 1991, p. 199–260 (DOI 10.1016/0168-0072(91)90022-E)