Théorème de Kruskal

En théorie des graphes, un arbre est un graphe non orienté, acyclique et connexe ; on obtient un arbre enraciné en fixant l'un des sommets, qu'on appelle la racine de l'arbre. En théorie des ensembles, on définit une autre notion d'arbre, à partir d'une relation symétrique ; on démontre[3] que, dans le cas fini, ces deux notions coïncident, et que tout arbre enraciné correspond à un ordre partiel unique défini sur l'ensemble des sommets, tel que tout sommet admette un unique prédécesseur[4], sauf la racine, qui n'en a aucun (les arêtes du graphe étant exactement celles reliant chaque sommet à son prédécesseur) ; c'est cette représentation qui va servir à définir les applications qui font l'objet du théorème de Kruskal.

On dit qu'un arbre est étiqueté par un ensemble d'étiquettes X si on a défini une application x de l'ensemble des sommets de l'arbre vers X, autrement dit si on attache au sommet s l'étiquette x(s).

On dit qu'une application f entre ensembles partiellement ordonnés finis respecte les minorants si a= inf (b, c) entraîne f(a)= inf (f(b), f (c)), où inf(x, y) =z désigne la borne inférieure de x et y, c'est-à-dire le plus grand élément qui soit ≤ à x et à y ; on voit aisément que cela implique que f est strictement croissante, autrement dit que a<b entraîne f(a)<f(b) et que f est une injection. Pour des arbres étiquetés par un ensemble X lui-même muni d'un ordre partiel noté ≤, on définit une notion de morphisme : une application f est un morphisme si elle respecte les minorants, et si elle respecte l'ordre des étiquettes, autrement dit si, pour tout sommet s du premier arbre, on a ${\displaystyle \scriptstyle x(s)\leq x(f(s))}$. La relation « il existe un morphisme de A vers B » est une relation d'ordre partiel sur l'ensemble des arbres étiquetés, considérés à isomorphisme près[5] (si l'on ne considère pas les arbres isomorphes comme identiques, la relation n'est plus antisymétrique, et on obtient seulement un préordre[6]) ; pour des arbres non étiquetés, on démontre que s'il existe un morphisme entre A et B, A est un mineur topologique de B.

Un ordre partiel (ou même un préordre) est appelé un bel ordre s'il ne contient aucune suite infinie strictement décroissante, ni aucune antichaîne infinie (définition qui généralise aux ordres partiels la notion de bon ordre définie pour les ensembles totalement ordonnés) ; c'est équivalent à dire que dans toute suite infinie d'éléments de l'ensemble ${\displaystyle x_{1},x_{2},\dots ,x_{n},\dots }$, il existe deux éléments ${\displaystyle x_{i}}$ et ${\displaystyle x_{j}}$ tels que ${\displaystyle i<j}$ et ${\displaystyle x_{i}\leq x_{j}}$.

Ces définitions permettent de formuler rigoureusement[7] le

L'existence d'une suite infinie strictement décroissante étant évidemment impossible (puisque, si A ≤ B et si A n'est pas isomorphe à B, A contient moins d'arêtes que B, ou des étiquettes plus petites), ce théorème revient donc à affirmer qu'il n'y a pas d'antichaînes infinies, c'est-à-dire d'ensemble infini d'arbres deux à deux incomparables par la relation ≤ (il convient cependant de remarquer qu'il existe des antichaînes finies aussi grandes que l'on veut).

Le lemme de Higman est un cas particulier de ce théorème, dont il existe de nombreuses généralisations, pour des arbres munis d'un plongement dans le plan, des arbres infinis, etc. Une généralisation bien plus puissante, concernant les graphes quelconques, est donnée par le théorème de Robertson-Seymour.

Harvey Friedman a remarqué[8] que certains cas particuliers du théorème de Kruskal peuvent être énoncés dans l'arithmétique du premier ordre (la logique du premier ordre correspondant aux axiomes de Peano), mais que cette théorie est trop faible pour les démontrer, alors qu'ils se démontrent aisément en utilisant l'arithmétique du second ordre. Un exemple analogue est donné par le théorème de Goodstein, mais pour démontrer les énoncés de Friedman, une portion significativement plus grande de l'arithmétique du second ordre doit être utilisée[9].

Soit P(n) l'affirmation

Il existe un m tel que si T₁,...,T_m est une suite finie d'arbres (non étiquetés), avec T_k ayant (pour tout k) k+n sommets, alors il existe un couple (i,j) tel que i < j et T_i ≤ T_j.

Cette affirmation est un cas particulier du théorème de Kruskal, où la taille du premier arbre est fixée, et où la taille des arbres croît au plus petit rythme possible ; on dit souvent qu'il s'agit d'une forme finie du théorème de Kruskal.

Pour chaque n, les axiomes de Peano permettent de démontrer P(n), mais ces axiomes ne permettent pas de démontrer que « P(n) est vrai quel que soit n »[10]. De plus, la plus courte démonstration de P(n) a une longueur grandissant extrêmement vite en fonction de n, beaucoup plus vite que les fonctions récursives primitives ou que la fonction d'Ackermann par exemple.

Friedman a également utilisé la forme finie suivante du théorème de Kruskal pour les arbres étiquetés (avec des étiquettes non ordonnées), forme paramétrée, cette fois, par le nombre d'étiquettes :

Pour tout n, il existe un m tel que si T₁,...,T_m est une suite finie d'arbres dont les sommets sont étiquetés par n symboles, chaque T_i ayant au plus i sommets, alors il existe un couple (i,j) tel que i < j et T_i ≤ T_j.

Dans ce cas, la relation ≤ signifie qu'il existe une application préservant les minorants, et envoyant chaque sommet sur un sommet ayant la même étiquette ; en théorie des graphes, ces applications sont souvent appelées des plongements.

Ce dernier théorème affirme l'existence d'une fonction à croissance rapide, que Friedman a nommée TREE, telle que TREE(n) est la longueur de la plus longue suite d'arbres à n étiquettes T₁, ..., T_m dans laquelle chaque T_i a au plus i sommets, et telle qu'aucun arbre n'est plongeable dans un arbre ultérieur.

Les premières valeurs de TREE sont TREE(1) = 1, TREE(2) = 3, mais soudain TREE(3) explose à une valeur si gigantesque que la plupart des autres « grandes » constantes combinatoires, comme le nombre de Graham, sont ridiculement petites en comparaison. Ainsi, Friedman a défini (pour un autre problème plus simple) une famille de constantes n(k), et a montré que n(4) était beaucoup plus petit que TREE(3)[2]. Or n(4) est minoré par A(A(...A(1)...)), où le nombre de A est A(187196), A() étant une variante de la fonction d'Ackermann définie par : A(x) = 2↑↑...↑x avec un nombre de flèches de Knuth ↑ égal à x-1. À titre de comparaison, le nombre de Graham est de l'ordre de A⁶⁴(4) ; pour mieux voir à quel point ce nombre est petit par rapport à A^A(187196)(1), se reporter à l'article Hiérarchie de croissance rapide. Plus précisément, dans les notations de cette hiérarchie, on peut montrer que la vitesse de croissance de la fonction TREE est supérieure à celle de f_Γ0, où Γ₀ est l'ordinal de Feferman-Schütte, ce qui montre au passage à quel point cette fonction croît plus vite que la fonction de Goodstein, qui ne croît que comme f_ε0.

Tous ces résultats ont pour conséquence que les théorèmes précédents (tels que le fait que TREE soit une application, c'est-à-dire soit définie pour tout n) ne peuvent être démontrés que dans des théories assez fortes[11] ; plus précisément, la force d'une théorie est mesurée par un ordinal (celui de l'arithmétique de Peano, par exemple, étant ε₀), et des théorèmes ayant pour conséquence l'existence de fonctions croissant trop vite (plus rapidement que f_ε0 dans le cas des axiomes de Peano) ne peuvent être démontrés dans ces théories. Comme leur négation ne peut évidemment pas y être démontrée non plus (en supposant que la théorie où l'on a démontré ces théorèmes est cohérente), il en résulte que, par exemple dans l'arithmétique du premier ordre, ces théorèmes sont indécidables, ce qui a d'importantes conséquences métamathématiques, ces formes d'indécidabilité étant ressenties comme beaucoup plus naturelles que celles correspondant au théorème de Gödel[11].

L'ordinal qui mesure la force du théorème de Kruskal est le petit ordinal de Veblen (en) (lequel est beaucoup plus grand que Γ₀)[12] ; il en résulte que l'on peut, par des constructions analogues à celles de Friedman, obtenir grâce à ce théorème des fonctions croissant plus vite que toute f_α de la hiérarchie de croissance rapide, où α est un ordinal plus petit que l'ordinal de Veblen.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Kruskal's tree theorem » (voir la liste des auteurs).
• Un exposé rigoureux de Bastien Legloannec, en français (contenant également une démonstration du théorème de Kruskal dans le cas des arbres non étiquetés, une présentation du théorème de Robertson-Seymour, et beaucoup d'exemples et de contre-exemples)

• (en) Harvey Friedman, Internal finite tree embeddings. Reflections on the foundations of mathematics (Stanford, CA, 1998), Urbana, IL, ASL, coll. « Lect. Notes Log. » (n^o 15), 2002, p. 60-91

• (en) Jean H. Gallier, « What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory », Ann. Pure Appl. Logic, vol. 53, n^o 3,‎ 1991, p. 199-260 lien Math Reviews (texte intégral sous forme de trois documents PDF : partie 1 partie 2 partie 3).

• (en) J. B. Kruskal, « Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture », Trans. Amer. Math. Soc., vol. 95, n^o 2,‎ mai 1960, p. 210-225 (DOI 10.2307/1993287)

• (en) C. St.J. A. Nash-Williams, « On well-quasi-ordering finite trees », Math. Proc. Cambridge Phil. Soc., vol. 59, n^o 04,‎ 1963, p. 833-835 (DOI 10.1017/S0305004100003844)

• (en) Stephen Simpson, « Nonprovability of certain combinatorial properties of finite trees », dans Harvey Friedman's Research on the Foundations of Mathematics, North-Holland, coll. « Studies in Logic and the Foundations of Mathematics », 1985, p. 87-117