Goodstein contre l'Hydre
Précédemment sur ce blog :
La suite de Goodstein (de graine 6), qui commence comme ça : 6, 29, 257, 3125, 46655, 98039, 187243, ...
Mais comment est définie cette suite ? On part d'un nombre [...] qui sera le premier terme de la suite. [...] On le décompose en base 2 itérée [...] On remplace ensuite tous les 2 par des 3. [...]On soustrait ensuite 1, et on obtient le deuxième terme de la suite.
Pour obtenir le suivant, on décomposera ce nombre en base 3 itérée, et
on remplacera les 3 par des 4, et ainsi de suite. [...] Toutes les suites de Goodstein se terminent par 0 ! [...]
==Générique== Palam palam pam pam ==/Générique==
Aujourd'hui, je vais tenter quelque chose de dingue : démontrer le théorème de Goodstein ! (Je vous renvois à l'article d'il y a 3 semaines pour le (re?)découvrir, et à celui de la semaine dernière pour toutes les histoires d'ordinaux). Si cette histoire ne vous plaît pas, vous pourrez redécouvrir le deuxième des douze travaux d'Hercule un peu plus bas...
Mais juste avant de commencer, une petite chose à ajouter à l'article de la semaine dernière à propos des ordinaux, indispensable pour la démo de Goodstein : toute suite décroissante d'ordinaux parvient à 0 après un nombre fini d'étapes (comme c'est le cas pour les entiers)
Prenons par exemple une suite strictement décroissante d'ordinaux qui commence à ω+5. Après 5 étapes au maximum, on atteindra ω. Un nombre strictement plus petit que ω n'est pas ω-1 (qui n'a aucun sens) mais un nombre entier n. On doit obligatoirement faire un "saut". On arrive alors dans les nombres entiers, et la suite décroissante atteindra 0 après n étapes (au maximum). On ne peut pas prévoir le nombre d'étape, mais on est sûr qu'il s'agira d'un nombre fini d'étapes.
L'idée de la démonstration est de faire correspondre à chaque élément de la suite de Goodstein un équivalent ordinal. Par la suite, on va prendre ces notations là:
un : n-ième terme de la suite de Goodstein
dn->n+1 : transformation des n en n+1 dans l'écriture en base n itérée.
Le principe de la suite de Goodstein se résume essentiellement comme ça :
Maintenant, on va définir une super-transformation Dn sur le même principe que dn->n+1, mais au lieu de transformer les n en n+1, on va transformer les n en ω !
Petit exemple :
(Bon, évidement, l'expression finale est vraiment tordue, mais elle représente bien un ordinal)
Trois choses à voir avec cette super-transformation :
* Appliquer Dn, c'est la même chose que appliquer dn->n+1 puis Dn+1. En effet, la première transforme les n en ω, et la deuxième transforme les n en n+1 puis en ω.
* Cette transformation est strictement croissante : si on a u < v, on aura forcément Dn(u) < Dn(v).
* Si Dn(x)=0, c'est que x=0.
Il y a juste à remarquer que la suite Un=Dn-1(un) est une suite strictement décroissante d'ordinal : elle tombera donc sur 0 après un nombre fini d'étapes, tout comme un ! CQFD comme on dit dans le métier.
Un autre problème dans le même style (qui demande aussi de passer par les ordinaux pour être démontré) est celui du deuxième des 12 travaux d'Hercule : tuer l'hydre de Lerne.
L'Hydre de Lerne est un serpent d'eau à corps de chien possédant de multiples têtes qui peuvent se régénérer, ainsi qu'une haleine empoisonnée pour corser un peu les choses.
Kirby et Paris ont bien étudié les hydres, et ils se trouvent qu'ils
ressemblent tous plus ou moins à un arbre (dans le sens de graphe), comme on peut en voir un exemple juste à gauche.
Pour tuer un tel hydre, il faut lui couper ses têtes :
* Lorsque l'on coupe une tête directement reliée au corps, celle-ci ne repousse pas.
* Si elle n'est pas reliée au corps, l'ensemble des coups et têtes reliés à des nœuds inférieurs peuvent se dupliquer autant de fois que l'hydre le décide (Mais un nombre fini de fois).
Quelle stratégie doit prendre Hercule pour détruire toutes les têtes ?
Imaginons que Hercule décide de couper la tête la plus à droite (en rouge, ici). L'hydre va pouvoir dupliquer en deux temps ses têtes ; d'abord à partir du nœud le plus proche de la tête, l'hydre va se dupliquer en 4 exemplaires, et dans un deuxième temps, elle va dupliquer toute la partie droite à partir du corps (ici, en deux exemplaires). Il ressemblera alors à ceci :
Hercule n'a plus qu'à choisir quelle nouvelle tête il va couper, si possible, sans désespérer de le tuer un jour.
En fait, même si l'hydre fait preuve de vice (dans le nombre de duplications) et Hercule preuve d'une extrême stupidité (dans le choix des têtes qu'il va choisir de couper), Hercule finira un jour par anéantir totalement l'hydre. (Après un nombre fini de têtes tranchées)
De la même façon que pour la suite de Goodstein, on ne peut pas utiliser la simple récurrence pour montrer que Hercule terminera un jour son travail, mais on peut le démontrer en utilisant les ordinaux !
Le seul problème, c'est que l'Univers risque de se détruire avant que Hercule ait terminé le boulot, vu le temps qui sera nécéssaire... L'histoire raconte que Hercule appela son oncle à la rescousse, enflamma quelques arbres pour cautériser les moignons de cou...
Sources :
Pour la science - n°278 - décembre 2000
Le coq et l'Hydre [pdf] (pour la démo de cette histoire d'Hydre)