Si j'ai été silencieux pendant deux semaines c'est qu'aussitôt abandonné le nim épicé j'ai été saisi d'une autre obnubilation intellectuelle (et qui me revient périodiquement[#]), c'est celle des ordinaux dénombrables : j'avais déjà écrit des articles de vulgarisation à ce sujet (celui-ci il y a très longtemps et celui-ci il y a un peu moins longtemps, le premier ayant même été traduit en chinois[#2] ; et j'ai beaucoup contribué à l'article de Wikipédia en anglais), cette fois je me suis intéressé aux notations ordinales — c'est-à-dire, en gros, la façon de donner un nom aux (plus petits des) ordinaux dénombrables, en essayant d'aller le plus loin possible, tout en sachant très bien qu'on ne pourra pas atteindre tous les ordinaux dénombrables (ni même tous les ordinaux récursifs). Et j'ai produit les jolis dessins que voici[#3] et surtout ce texte explicatif dont je vais dire un peu plus.
[Ajout : voir une entrée ultérieure, qui peut servir d'introduction à la suite.]
Quand on entend parler des ordinaux pour la première fois, on entend parler de ω, de ωω, de ωωω, et souvent de la limite de tout ça, qui est ε0 (qui le plus petit ordinal vérifiant ωξ = ξ, c'est-à-dire le plus petit point fixe de ξ↦ωξ). Manipuler les ordinaux jusqu'à ε0 (pour les ajouter, les multiplier ou les exponentier) est facile si on travaille en forme normale de Cantor (c'est-à-dire, informellement, en base ω) itérée pour les exposants ; à partir de ε0 ça devient un chouïa plus compliqué parce qu'il y a des égalités qui ne sautent pas immédiatement aux yeux (comme le fait que ωε0+1 = ε0·ω), mais on finit par s'y habituer. Le problème est plutôt de monter aussi loin que possible : si ε1 est la prochaine solution de ωξ = ξ, et ainsi de suite, jusqu'où ira-t-on ? On pourrait appeller ζ0 la limite de la suite ε0, εε0, εεε0, c'est-à-dire le premier point fixe de ξ↦εξ, on peut continuer à jouer ainsi avec les lettres grecques qui énumèrent les points fixes les unes des autres, si bien qu'on finit par avoir besoin d'un alphabet grec transfini : c'est ce qu'on appelle le schéma φ de Veblen (à deux variables, pour commencer), chaque rang énumérant les points fixes du rang précédent. Seulement, on arrive à court de ce schéma aussi lorsqu'on tombe sur la première lettre grecque qui est, pour ainsi dire, son propre rang dans l'alphabet. C'est cet ordinal (toujours dénombrable, bien sûr) qu'on appelle l'ordinal de Feferman-Schütte (et c'est la limite des ordinaux pour lesquels le schéma de Veblen à deux variables fournit des notations).
Car certains grands ordinaux dénombrables, comme ça, ont des noms de gens associés : l'ordinal de Feferman-Schütte, l'ordinal d'Ackermann, les petit et grand ordinaux de Veblen, l'ordinal de Bachmann-Howard, l'ordinal de Takeuti-Feferman-Buchholz (c'est moi qui l'appelle comme ça) et peut-être plus encore. En gros, il y a deux approches possibles pour donner des noms systématiques à de grands ordinaux dénombrables :
- L'approche prédicative part, pour ainsi dire, de bas en haut. Elle consiste à appliquer des fonctions toujours plus compliquées définies comme des points fixes de points fixes de points fixes de, etc., c'est-à-dire des constructions comme le schéma de Veblen. En utilisant cette approche on peut certainement définir l'ordinal de Feferman-Schütte (parfois considéré comme la limite des ordinaux prédicatifs, mais à mon avis c'est une bêtise) avec le schéma de Veblen à deux indices ; et, en travaillant un peu plus, aussi le petit — voire le grand — ordinal de Veblen (avec des schémas de Veblen à plus de variables). Atteindre l'ordinal de Bachmann-Howard de cette façon semble à peu près impossible (peut-être pas de façon théorique mais certainement en pratique), pour ne rien dire des encore plus grands.
- L'approche imprédicative par écrasement est plus inattendue, plus difficile à comprendre, mais beaucoup plus puissante, et permet sans trop de difficulté d'atteindre l'ordinal de Bachmann-Howard et, en travaillant un peu plus, des ordinaux encore plus grands. L'idée surprenante est que pour construire des notations pour de grands ordinaux dénombrables on va en construire pour certains ordinaux indénombrables et utiliser une fonction écrasante qui les renvoie sur des ordinaux dénombrables. Intuitivement, l'idée est quelque chose du style : si on tombe à court de notations pour les ordinaux dénombrables, faisons un saut jusqu'aux indénombrables qui nous fournissent forcément des choses plus grandes — et rendons-nous ensuite compte que si on met les notations en question dans l'ordre, ça ne fait évidemment qu'un ordinal dénombrable. (C'est ainsi que l'ordinal de Bachmann-Howard se note quelque chose comme le ψ(εΩ+1) du titre de cette entrée : ici, εΩ+1 est un ordinal qui n'est pas dénombrable, mais ψ(εΩ+1) l'est.)
Les jolis petits
dessins mentionnés ci-dessus représentent les ordinaux (enfin, un
petit échantillon d'ordinaux !) jusqu'au petit ordinal de Veblen,
c'est-à-dire à peu près l'étendue de l'approche prédicative, en leur
donnant si possible deux noms, l'un utilisant l'approche prédicative
(avec les fonctions φ de Veblen) et l'autre utilisant une fonction
écrasante ψ. Pour les arbres, je vais en dire plus dans une
minute. Concernant la fonction écrasante, j'ai écrit
ce texte
explicatif : reste à savoir où l'insérer dans Wikipédia (si
possible sans qu'on m'accuse de faire de la original
research
). Peut-être que ce n'était pas la meilleure place pour
ça, en fait. Mais quelles que soient ses vertus pédagogiques (ou
pas), il m'aura au moins permis de bien comprendre ces choses-là, et
donc, en quelque sorte, d'apprendre à « compter » jusqu'à l'ordinal de
Bachmann-Howard (sans doute même au-delà).
Ce qui est étrange, c'est qu'on a parfois l'impression que les
ordinaux (dénombrables, au moins, car les autres sont juste
inimaginables) sont « tous pareils » : quand j'essaie d'expliquer
comment on grimpe jusqu'à tel ou tel ordinal, on se retrouve souvent à
prononcer des phrases comme et on recommence tout ce
truc
, et ainsi de suite jusqu'à
, etc. Pourtant, au
contraire, il n'y a pas de structure mathématique plus
rigide[#4] que les ordinaux.
L'autre chose étrange, c'est que les ordinaux apparaissent très peu dans les mathématiques standards, hors théorie des ensembles (au point que la plupart des mathématiciens considèrent que c'est un peu un gros mot). Pourtant, on pourrait dire qu'à chaque fois qu'il y a un processus dont la terminaison est garantie en temps fini (et c'est chose fort courante en mathématiques ou en informatique), il y a un ordinal qui se cache[#5]. Seulement, en pratique, cet ordinal n'est jamais bien grand (très souvent c'est simplement un entier naturel, en fait, quand il y a une borne universelle sur la longueur du processus, ou bien ω quand il y a une borne qui dépend d'un unique premier choix), donc les mathématiciens n'ont pas trop besoin de savoir compter loin.
Parmi les processus qui terminent forcément et auxquels sont associés des ordinaux pas trop petits, il y en a qui sont souvent donnés en exemple parce qu'ils sont récréatifs et faciles à comprendre : ce sont les jeux de l'hydre. En gros il s'agit de partir d'une structure finie, typiquement un arbre, censé symboliser l'hydre. Un joueur, censé symboliser Hercule, réduit la structure par petites étapes (du genre, couper une branche de l'arbre, parfois avec des contraintes sur la branche) : mais dès qu'on la réduit, la structure grandit de façon apparemment démesurée (l'hydre repousse des nouvelles têtes), selon des règles plus ou moins compliquées. Selon toute apparence, Hercule n'a aucune chance de gagner, et le nombre de têtes de l'hydre croît de façon vertigineuse ; en réalité, les règles sont faites en sorte qu'à chaque configuration de l'hydre est associé un ordinal et que cet ordinal décroît forcément, de sorte que le jeu termine toujours en temps fini. Le cas le plus classique est l'hydre de Kirby-Paris, dont il y a par exemple une description ici (avec même une petite applet pour jouer) : dans ce cas, l'ordinal est ε0 (au sens où chaque arbre fini encode un ordinal inférieur à ε0 de façon à décroître à chaque coup d'Hercule, ce qui garantit la terminaison, et les ordinaux). Mais il y a d'autres variantes (parfois compliquées) du jeu de l'hydre, qui doivent être associées à d'autres ordinaux éventuellement plus grands : par exemple, l'hydre de Kirby-Paris ne croît jamais en hauteur, seulement en largeur, mais on doit pouvoir en faire une qui croît en hauteur aussi. J'aimerais définir une hydre de Veblen mais je n'ai pas trouvé de description simple ou qui me satisfaisse.
L'ordre sur les arbres finis enracinés (et à descendants ordonnés) qui leur donne la taille du petit ordinal de Veblen est défini récursivement comme suit :
Un arbre (fini enraciné) A est strictement inférieur à B lorsque soit il existe une branche (i.e., un sous-arbre immédiat, i.e., un fils) B′ de B qui soit supérieur ou égal à A, soit les deux conditions suivantes sont vérifiées : d'une part toute branche A′ de A est strictement inférieur à B et, d'autre part la liste des branches de A est lexicographiquement strictement inférieure à celle des branches de B (en donnant le plus de poids aux branches les plus à gauche et en convenant que s'il y a moins de branches dans A alors la liste est lexicographiquement inférieure).
— c'est un peu long à dire, mais ce n'est pas vraiment compliqué[#6]. En gros ça dit qu'on compare les branches lexicographiquement mais avec l'exception évidemment nécessaire que l'arbre tout entier doit être supérieur à chacune de ses branches. Ce qui n'est pas totalement évident, c'est que c'est bien un bon ordre (et que la relation d'égalité associée est bien l'égalité à laquelle on s'attend sur les arbres finis enracinés !), et la longueur de ce bon ordre est précisément le petit ordinal de Veblen. Donc à tout arbre fini enraciné est associé, de cette façon, un ordinal inférieur au petit ordinal de Veblen et c'est ça que j'ai représenté dans mes pages de petits dessins. Et il doit y avoir un jeu d'hydre associé à cet ordre, mais je n'arrive pas à décrire de façon générale quelle en serait la règle[#7].
[#] En l'occurrence, c'est quand même parti du jeu de nim, puisqu'il y a un problème — à ma connaissance encore ouvert — posé par Conway en 1976 qui est de déterminer le deuxième ordinal qui soit un transcendant pour la multiplication de nim (sachant que le premier est ωωω).
[#2] Il va de soi que
tous les liens que je donnais en 2005 sont cassés. <soupir> La
traduction chinoise en question, parue
dans 三思科学,
existe cependant encore, elle
est trouvable
par son
titre, 不同寻常的数
.
[#3] Produits par ce programme Perl et qui font ensuite beaucoup souffrir TeX (j'ai dû augmenter la mémoire qu'il peut prendre, et ça compile en plus de 20s sur ma machine qui n'est pourtant pas minable). J'espère ne décevoir personne en avouant que les noms n'ont pas été générés automatiquement…
[#4] Par rigide
,
j'entends, techniquement, qu'ils n'ont pas d'automorphismes : lorsque
deux ensembles bien ordonnés sont isomorphes, l'isomorphisme est
unique — c'est-à-dire, avec les mains, qu'il n'y a qu'une seule
façon de les faire se correspondre. Donc si on peut se poser la
question philosophique complètement oiseuse de savoir si le ℂ
auquel je pense est bien le même que celui de mon voisin (a-t-on l'un
et l'autre le même i ? ou sont-ils conjugués complexes ?),
cette question ne peut pas se poser pour les ordinaux.
[#5] On pourrait le caractériser ainsi : soit P un processus dont un théorème nous assure qu'il termine toujours, quels que soient certains choix effectués ; on considère un jeu à deux joueurs où un joueur applique le processus P, à raison d'une étape à chaque tour, en effectuant les choix qu'il veut, et l'autre joueur part d'un certain ordinal α et peut à chaque étape le décroître comme il lui plaît. Le premier joueur qui termine a perdu (c'est-à-dire le joueur-processus si le processus termine, et le joueur-ordinal si l'ordinal tombe à zéro) : à partir d'un certain ordinal, c'est le joueur-ordinal qui a une stratégie gagnante — et cet ordinal mesure la longueur de terminaison du processus P.
[#6] Pour comparaison, l'ordre sur les arbres finis enracinés (sans distinction des descendants) qui conduit à l'hydre de Kirby-Paris est le suivant : un arbre A est inférieur à un arbre B lorsque, en triant les branches de A et celles de B pour l'ordre en question et en regardant le nombre d'occurrence de chacune, le nombre pour A est lexicographiquement inférieur au nombre pour B en donnant au nombre des branches les plus grandes le plus de poids. Cette fois-ci l'ordinal est ε0 (beaucoup plus petit, donc), et, pour ainsi dire, les arbres grandissent en largeur avant de grandir en profondeur (pour l'ordre de Veblen, c'est le contraire).
[#7] Ça devrait ressembler à ceci : quand on coupe une tête, toutes les têtes situées à sa droite s'énervent, et ça leur fait pousser sur chacune une copie du sous-arbre complet qui les relie au chemin de coupe (têtes énervées comprises) et on recommence ça aussi souvent que l'hydre le veut. Malheureusement, sous cette forme, ça ne marche pas.