Deux (deux ?) minutes pour l'hydre de Kirby & Paris
Hey ! Et pourquoi pas une nouvelle vidéo ? On y parlerai des nombres ordinaux et du jeu de l'hydre. Ca serait une bonne occasion de parler d'énoncés indécidables !
Transcriptions + commentaires
En 1982, Laurie Kirby et Jeff Paris réinventent dans leur article “Résultats d’indépendances accessibles pour l’arithmétique de Peano” le mythe de Hercule contre l’hydre de Lerne. Un problème qui fournit pour la première fois un exemple plutôt concret de ce que peut être un problème indécidable. Ça tombe bien, j’ai deux minutes pour en parler...
Voici l’hydre de Lerne : un monstre fabuleux qui possède de nombreuses têtes et de nombreux cous. Dans le cadre du deuxième de ses douze travaux, Hercule doit l’affronter et le vaincre, et doit pour cela couper chacune de ses têtes. Le hic, c’est que lorsque l’hydre se fait décapiter, des têtes repoussent, et contrairement à la légende, il ne pourra pas appeler son neveu à la rescousse. Existe-t-il pour notre héros une stratégie qui permettrait d’empêcher à tout jamais cet horrible monstre de nuire ? Eh bien, oui, et les nombres transfinis sont là pour nous aider !
Vous pouvez tenter de jouer au jeu de l'hydre en suivant ce lien.
Détaillons un peu le mécanisme de régénération des têtes. Mathématiquement, l’hydre peut être représentée comme un graphe, et plus précisément, comme un arbre enraciné. Un arbre est une structure mathématique composée de différents nœuds reliés par des arêtes, mais qui ne présente aucun cycle. Sur un arbre, les nœuds situés aux extrémités sont appelés les feuilles. On dit que l’arbre est enraciné lorsque l’un des nœuds a été choisi pour en être la racine.
On peut assimiler l’hydre à un arbre, où son corps est la racine de l’arbre, ses têtes sont ses feuilles, ses cous sont ses arêtes, et les jonctions entre les cous sont les autres nœuds du graphe.
La régénération céphalique de l’hydre fonctionne de la façon suivante. Lorsqu’une tête est découpée, la feuille et l’arête correspondante sont retirées du graphe. L’hydre se renouvellera à partir du nœud situé en dessous de l’arête retirée, en générant plusieurs copies de la partie de l’arbre située au-dessus de ce nœud. Le nombre de copies créées par l’hydre sera à chaque étape le nombre de coups donnés par Hercule.
Ainsi, l’hydre fabriquera une seule copie lors de sa première régénération, puis deux à la deuxième, et ainsi de suite. A noter tout de même que lorsque Hercule découpe une tête directement reliée au corps de la bête, celle-ci ne pourra pas se régénérer.
La question que Hercule se pose est évidente : quelle stratégie doit-il accomplir pour réduire à néant le mastodonte ?
Assez étonnamment, il existe des stratégies, et ça quelle que soit la taille initiale de l’hydre. Encore plus étonnant, une stratégie qui fonctionne toujours est de couper les têtes complètement au hasard jusqu’à extinction complète du monstre. Mais ce qui est encore plus étonnant, c’est que ce résultat est vrai, mais qu’il est impossible de le démontrer avec les outils de l’arithmétique comme la démonstration par récurrence, ce qui fait que ce résultat est un indécidable de l’arithmétique. Heureusement, on peut le prouver dans la théorie des ensembles, et on va même le faire tout de suite !
Pour vaincre l’hydre, nous avons besoin des nombres transfinis, qui font partie de la classe des nombres ordinaux. Si vous pensez que les raisonnements sur les cardinaux infinis auquel on a eu recours lors de cette histoire d’hôtel de Hilbert qui possédait une infinité de chambres était tordue, accrochez-vous… Les nombres transfinis, c’est encore pire.
Comptons les nombres le plus loin possible. 0, 1, 2, 3, 4, et ainsi de suite, on peut aller aussi loin que l’on veut. Mais qu’est ce qui arrive juste après ? Eh bien, c’est à ce moment que les nombres transfinis rentrent en jeu. Après tous les nombres entiers vient naturellement l’infini, que l’on appellera ici ω. ω, c’est donc l’ordinal qui vient juste après l’ensemble de tous les nombres entiers.
Et après ? Eh bien, il n’y a pas de raison qui pourrait nous empêcher de compter plus loin. Il vient donc ensuite ω+1, ω+2, ω+3 etc… Tous ces nombres là sont appelés les ordinaux, parmi lesquels ont distingue d’un côté les nombres entiers, et de l’autre côté les nombres transfinis et, comme souvent dès qu’il s’agit d’infinis, ces nombres ont été créés par le génial Georg Cantor.
Cette construction peut sembler complètement absurde au premier abord, mais elle a du sens dès que l’on cherche à décrire des ensembles infinis bien ordonnés, c’est à dire, des ensembles où l’on peut toujours dire entre plusieurs éléments lequel est le plus petit.
Reprenons l’hôtel de Hilbert, qui possède un nombre infini dénombrable de chambres. Les affaires étant florissante, un deuxième étage a été créé dans cet hôtel, deuxième étage qui lui aussi possède une infinité dénombrable de chambres. Tous les matins, le service d’étage passe dans chacune des chambres pour refaire le lit, arroser les plantes, remplir le minibar et changer les échantillons de shampooing. Ils visiteront donc chacune des chambres, en commençant par le rez-de-chaussée, puis en visitant ensuite le second étage. De cette façon, les chambres sont bien ordonnées, et on peut du coup les numéroter à l’aide des ordinaux : il y a d’abord les chambres du rez-de-chaussée, numérotées par 0, 1, 2, 3, 4, et ainsi de suite, puis, une fois que l’intégralité du rez-de-chaussée aura été visité, on pourra passer aux chambres du premier étage que l’on numérotera par des ordinaux transfinis : ω, ω +1, ω +2, ω +3 et ainsi de suite.
Bref : les ordinaux permettent de numéroter, même au-delà de l’infini. Mais ils ne s’arrêtent pas là. Après ω, ω +1, ω +2, ω +3, et ainsi de suite, il y a un ordinal encore plus grand : ω + ω, que l’on nommera plutôt ω×2. Vient ensuite ω×2+1, ω×2+2, ω×2+3, et ainsi de suite. Tous ces nombres permettraient de numéroter des chambres d’un hôtel de Hilbert à deux étages.
On peut continuer encore, et ainsi de parler de ω×3, de ω×4, et ainsi de suite, pour numéroter les chambres d’un hôtel de Hilbert avec davantage d’étages. Mais rien ne nous empêche de continuer, et on peut donc parler de l’ordinal ω × ω, que l’on note plus commodément ω². Les ordinaux inférieurs à ω² permettent de numéroter les chambres d’un hôtel de Hilbert possédant une infinité d’étages.
Vient ensuite ω²+1, puis ω²+2, et, si on va toujours plus loin, on pourra parler de ω² × 2, qui correspondrait à un deuxième hôtel de Hilbert possédant une infinité d’étages avec une infinité de chambres par étages construit juste en face du premier hôtel.
Mais après ω² viennent des ordinaux comme ω²×2, ω²×3, et on peut poursuivre jusqu’à ω² × ω, c’est à dire, de ω³. Un tel ordinal permet par exemple de numéroter les chambres d’un complexe hôtelier possédant une infinité d’hôtels de Hilbert.
Gardons tout de même en tête une chose : les ordinaux ne servent pas à dénombrer, mais bien à numéroter. Pour dénombrer un ensemble, c’est à dire, compter le nombre d’objets que contient cet ensemble infini ou non, on utilisera les nombre cardinaux. Par exemple, le cardinal 5 correspond au nombre de doigts d’une main, le cardinal ℵ₀ correspond au nombre de nombres entiers ou au nombre de chambres dans l’hôtel de Hilbert tandis que le cardinal ℵ₁ correspond au nombre de nombres réels.
L'affirmation de cette dernière phrase n'est vraie que si l'on admet l'hypothèse du continu (qui est un indécidable de la théorie des ensembles). Il aurait été plus juste d'écrire que c'est le cardinal 2^ℵ₀ qui compte le nombre de nombres réels.
Les ordinaux, eux, permettent de préciser la position d’un objet au sein d’un ensemble bien ordonné. L’ordinal 4 correspond à la position de l’auriculaire sur une main, l’ordinal ω précise la position de la première chambre de l’étage de l’hôtel de Hilbert, tandis que ω+1 est la position de chambre juste à côté.
On peut s'étonner qu'il existe des façons de parler des ensembles infinis : ordinaux et cardinaux. En fait, ce sont deux points de vue différents sur des mêmes objets mathématiques. Tous les ordinaux présentés dans la vidéo (qui s'écrivent avec le symbole ω et les opérations usuelles +, × et ^) permettront de numéroter les éléments d'ensembles dénombrables (possédant ℵ₀ éléments). On peut aussi numéroter les éléments d'ensembles comptant 2^ℵ₀ comme l'intervalle [0,1] avec des ordinaux, mais il faudra utiliser des ordinaux encore plus grand (les ordinaux indénombrables).
Évidemment, on peut continuer toujours plus loin, et parler de ω⁴, de ω ⁵, de ω⁶, et ainsi de suite jusqu’à ωᵚ. La métaphore de l’hôtel de Hilbert commence à devenir difficile à tenir à présent, surtout que l’on peut toujours trouver des ordinaux plus grand, comme ωᵚ+1, voire ω^(ω²), voir même ω^(ω^ω), ou encore ω^(ω^(ω^ω)). Je m’arrête ici dans la construction des ordinaux, mais il faut retenir qu’elle peut toujours être poursuivie une infinité de fois. D’ailleurs, si vous poursuivez la construction une infinité de fois, elle pourra toujours être poursuivie. Mais je m’égare. Retenons simplement que l’on peut additionner et multiplier des ordinaux, et même former des puissances.
Si vous regardez en détail les tables d'additions, de multiplications et de puissances présents dans la vidéo, vous pourrez voir que les opérations sur les ordinaux sont loin d'être triviales. Par exemple, 1+ω = ω. Cela vient du fait que les nombres ordinaux, même si ils sont présentés sous forme de nombres, sont davantages des ensembles. La définition formelle de l'addition des ordinaux, tout comme celle de la multiplication, passe par la théorie des ensembles, un point que je ne voulais pas aborder pour ne pas rendre l'exposé trop technique. En fait, additionner des ordinaux revient à placer l'un à la suite de l'autre des ensembles ordonnés correspondant à cet ordinal. La somme 1+ω correspond à l'ordinal associé à la suite "un élément puis 0, 1, 2, 3, 4, 5, ...". Renumérotée, c'est l'ensemble des entiers naturels (correspondant donc à l'ordinal, ω). A l'inverse, la somme ω+1 est l'ordinal associé à la suite "0, 1, 2, 3, 4, ... puis un élément" ; on ne peut pas le renuméroter autrement qu'en parlant de "l'ensemble des entiers naturels puis un autre élément", ce qui correspond bien à l'ordinal ω+1 . En fait, on appelle ça une addition puisqu'elle correspond à l'addition sur les entiers naturels, mais c'est sans doute un mauvais terme pour appréhender la somme des ordinaux transfinis. Cela dit, cette non commutativité ne pose pas de problème dans le cas de l'hydre, il suffira juste d'additionner les termes du plus grand au plus petit (je ne l'ai pas précisé dans la vidéo dans un soucis de vulgarisation).
Les ordinaux partagent avec les entiers une propriété réellement remarquable : toute suite strictement décroissante d’ordinaux atteint 0 en un nombre fini d’étapes. Cela signifie que si on prend une séquence de nombres ordinaux où chaque ordinal est strictement plus petit que le précédent, on finira toujours par tomber sur 0.
Prenons l’exemple du room service dans un hôtel de Hilbert ayant un étage. Chaque chambre est donc numérotée par un ordinal : soit un nombre entier pour le rez-de-chaussée, soit un nombre de la forme ω+k, avec k entier, pour le premier étage. Notre agent est situé quelque part dans une chambre de l’étage, et s’aperçoit qu’il a oublié ses lunettes dans l’une des chambres précédentes. Il doit donc faire marche arrière, et retourner voir certaines chambres, en suivant un ordre strictement décroissant. Dans un premier temps, ce sont des chambres de l’étage qu’il revisitera, jusqu’à ce qu’il atteigne la chambre ω. Dans un second temps, ce sont les chambres du rez-de-chaussée qu’il faut retourner voir. Seulement, il y a une infinité de chambres, il est donc impossible de recommencer par la dernière, mais seulement par une chambre avec un très grand numéro. Si il visite les chambres en suivant un ordre décroissant, c’est donc un nombre fini de chambres qu’il visitera finalement au rez-de-chaussée, avant de s’arrêter à zéro.
L'important à comprendre ici, c'est qu'il n'existe pas d'ordinal qui viendrait juste avant ω. Il n'y a rien, chez les ordinaux, que l'on pourrait appeller "ω-1". Si l'employé suit les chambres en sivant un ordre décroissant, il visitera après ω une chambre du rez-de-chaussée. Cela peut être la chambre 1000 (dans ce cas, il visitera ensuitre au plus 1000 chambres), cela peut être la chambre 100000 (dans ce cas, il visitera ensuitre au plus 1000000 chambres), peu importe. Ce que l'on est sûr, c'est que cela sera une chambre portant un numéro fini, et dans ce cas, il visitera ensuitre au plus un nombre fini de chambres.
Bref : si on décompte des ordinaux, on retombe toujours sur zéro. Et ça, ça permettra à Hercule de vaincre cette affreuse hydre.
Revenons justement à notre hydre, et mesurons sa force. Cette mesure ne se fera pas avec des nombres entiers ou réels, mais avec des nombres ordinaux. On va définir la mesure de la force d’une hydre en associant à chaque tête, à chaque cou et à chaque nœud une certaine force. Pour cela, on commence par affecter à chaque tête le nombre 0, et à chacun des cous menant à une tête le nombre 1. Ensuite, pour chaque nœud où sont basés un ou plusieurs de ces cous, on y associe le nombre de cous.
Pour les autres cous et nœuds, on procède de façon similaire. On associe à chacun des cous l’ordinal ωˣ, où X est la force du nœud juste au-dessus. Ceci est cohérent avec la règle 0 : si une tête a pour force 0, un cou menant à une tête a pour force ω⁰=1. On associe enfin à chaque nœud la somme des forces des cous qui y repose. Si on veut être tout à fait précis, et pour éviter les soucis de non comutativité de la somme d'ordinaux, il faut tout de même préciser que ces ordinaux doivent être sommés en suivant un ordre décroissant. Par exemple, ce morceau de cou mène à un nœud de force 2, il aura donc pour force ω puissance 2, c’est à dire ω². Sur le nœud juste en dessous repose un cou de force 1 et un cou de force ω². Il aura donc pour force ω² +1. Le cou inférieur a donc pour force l’ordinal ω puissance ω² + 1. On calcule la force des autres éléments du corps de l’hydre de la même façon, ce qui permet finalement de dire que cette hydre a pour force ω^(ω ² +1) + ω³ + 2.
Cette définition de la force permet d’associer un ordinal à chaque hydre imaginable. Celle-ci a par exemple pour force ω^(ω^ω) + 1, tandis que celle-ci a pour force ω^(ω³+ω²). Puisque l’on peut toujours comparer deux ordinaux, on peut par exemple affirmer ici que l’hydre de gauche est plus puissante que l’hydre de droite.
Hercule entre en scène, et coupe l’une des têtes. Quelle que soit la tête qu’il attaquera, il en résultera que la force globale de l’hydre diminuera. Par exemple, si la première tête qu’il attaque est celle-ci, la force de l’hydre deviendra ω^(ω ² +1) + ω² × 2+ 2, qui est une force strictement plus petite, puisque ω²×2 est un ordinal strictement inférieur à ω³. S’il attaque ensuite à cette tête là, la force de l’hydre devient ω^(ω×3+1) + ω²×2+ 2, qui est à nouveau strictement inférieur à la force précédente. En fait, quand une tête est coupée, bien que la largeur de l’arbre augmente, sa hauteur diminue. Ce que l’on mesure avec les ordinaux, c’est justement cette hauteur, qui diminue donc à chaque étape.
En poursuivant sans relâche ces attaques, la force de l’hydre ne cessera de décroître. Puisqu’il s’agit d’une suite strictement décroissante d’ordinaux,elle finira forcément par tomber à zéro après un nombre non infini de décapitations.
On m'a plusieurs fois posé la question "pourquoi définit-on la force des hydres de cette façon et pas d'une autre ?". La raison est assez terre à terre : parce que si on la définit autrement, il y a des chances que l'on ne puisse pas conclure quand à la finitude du combat de Hercule. Plus précisément, en définissant la force de l'hydre ainsi, on s'assure que l'opération "couper une tête" entraînebien l'existence d'une suite strictement décroissante d'ordinaux, auquel on pourra appliquer le théorème "toute suite strictement décroissante d'ordinaux est finie". Si on décide, par exemple, de définir le poids comme "le nombre de têtes", on obtiendra une suite qui sera parfois croissante, parfois décroissante, et pour laquelle on ne pourra finalement pas dire grand chose d'intéressant.
Bien sûr, le combat sera très certainement très long, mais on ne peut pas abattre un monstre mythologique sans un minimum de patience.
Je n'ai pas caculé le nombre minimal de coups nécéssaires pour anéantir l'hydre de la vidéo. On peut tout de même dire que ce nombre va être immensément grand. A titre d'exemple, l'hydre ci-contre demande pour être détruit un nombre de coups supérieur au nombre de Graham, qui est un nombre inimaginablement et démesurément immense (évoqué là-bas).
Finalement, on vient de démontrer que, quelle que soit la forme de l’hydre et quelle que soit la stratégie de Hercule, celui-ci parviendra toujours à occire son opposant. Pour démontrer ce théorème de l’hydre, il nous a fallu passer par les ordinaux.
Mais ce que Kirby et Paris ont prouvé dans leur article est en réalité bien plus génial : pour prouver que Hercule est toujours plus fort que l’hydre, on ne peut pas faire autrement que d’utiliser les ordinaux. La démonstration du théorème de l’hydre est en fait absolument impossible à réaliser avec les outils de l’arithmétique que l’on connaît, comme les opérations sur les nombres entiers ou la démonstration par récurrence.
Le théorème de l’hydre est en fait ce que l’on appelle en logique un théorème indécidable pour l’arithmétique : un théorème qui est vrai mais qui ne peut pas être démontré au sein de cette théorie.
La notion d'énoncé "vrai" est un peu plus précise que cela en mathématiques. Pour dire qu'un énoncé est vrai dans une théorie donné des mathématiques (comme celle de l'arithmétique de Peano), il faut qu'elle soit vraie dans tous les modèles de cette théorie (le modèle le plus simple de l'arithmétique de peano est celui de la séquence de nombres 0-1-2-3-... que l'on trouve dans la théorie des ensembles ZF). En fait, le théorème de Kirby & Paris montre que l'énoncé est vrai dans la théorie des ensembles (et donc, dans le modèle classique de l'arithmétique), mais ne dit rien de sa véracité de façon générale. Il a donc été un peu précipité pour moi d'affirmer que l'énoncé est vrai sans plus de précisions.
C’est d’ailleurs ce qu’énonce le théorème de Gödel : la plupart des théories mathématiques contiennent des énoncés qui sont vrais mais qui ne peuvent pas y être démontrés. Mais ça, c’est une autre histoire...
Le théorème de Gödel fera peut être un jour l'objet d'un article ou d'une vidéo. Cela dit, le sujet est vaste et particulièrement pointu. Je ne veux donc pas m'y précipiter pour ne pas y dire trop de choses approximatives.
Quelques liens :
L'article de Kirby et Peano
Une excellente approche un peu vulgarisée des ordinaux, par David Madore
Tester le jeu de l'hydre : Hercule vs l'hydre
/http%3A%2F%2Fstorage.canalblog.com%2F70%2F81%2F210892%2F112209252_o.png)
/http%3A%2F%2Fstorage.canalblog.com%2F58%2F95%2F210892%2F102067299_o.png)
/http%3A%2F%2Fstorage.canalblog.com%2F85%2F70%2F210892%2F65561362_o.png)
/http%3A%2F%2Fstorage.canalblog.com%2F30%2F49%2F210892%2F60870097_o.jpg)