Hydre de Kirby — Les-mathematiques.net The most powerful custom community solution in the world

Hydre de Kirby

J'ai regardé récemment une vidéo sur l'hydre de Kirby. Je ne sais pas trop quoi penser de la conclusion : s'applique-t-elle au monde réel (à supposer qu'on vive indéfiniment) ?

Réponses

  • Bonjour rebellin.
    Il n'y a rien de bien mystérieux là-dessous. Ce qui est regrettable c'est que le type passe 3 plombes à t'expliquer ce qu'est un ordinal, et sur la fin, là où ça devient plus difficile à suivre, il accélère comme un malade.
    Tape "suites de Goodstein" dans google, c'est un problème très similaire peut-être plus facile à appréhender.

    Quant aux applications au monde réel elles me paraissent utopiques : si Hercule donne un coup par seconde, le temps qu'il va mettre à flinguer son hydre est immensément plus grand que l'espérance de vie de la Terre...
  • Oui, mais en imaginant que la terre existe indéfiniment, la solution est-elle viable ?
  • En supposant les conditions réunies, le théorème est vrai. Es-tu vraiment satisfait de cette réponse ?
  • Bonjour,
    Moi je dirais : oui la solution est viable dans la "vraie vie" de la Terre éternelle.
    La raison pour laquelle certains énoncés arithmétiques, tel que "l'hydre sera vaincu peu importe la stratégie d'Hercule" (enfin, une traduction de cette phrase en langage arithmétique), sont indécidables, c'est que les axiomes de l'arithmétique de Peano n'excluent pas l'existence d'entiers chelous supérieurs à tous les entiers intuitifs (ceux qu'on utilise pour compter : 0, 1, 2, 3, etc.). Le vrai terme est "entiers non standard". Il existe des structures $(\Bbb N',0,1,+,\times)$ qui satisfont les axiomes de Peano, et qui contiennent donc tous les entiers intuitifs (0, 1, 1+1=2, 2+1=3, etc. donc $\Bbb N\subset \Bbb N'$), mais qui contiennent aussi des $n'\in\Bbb N'$ tels que $\forall n\in\Bbb N, n'>n$. Donc certains énoncés peuvent être vrais pour $\Bbb N$ mais pas pour tous les $\Bbb N'$, et donc non démontrable dans la théorie de Peano. C'est le cas de "l'hydre sera vaincu peu importe la stratégie d'Hercule". C'est un peu une bizarrerie de la logique à première vue.
    Mais l'hydre de la "vraie vie", lui, possède un nombre de têtes qui est un entier standard. Donc ce qui compte pour savoir si "l'hydre sera vaincu peu importe la stratégie d'Hercule" est vérifié dans la réalité, c'est que cet énoncé soit vrai pour $\Bbb N$ l'ensemble des entiers intuitifs. Et c'est le cas.
  • En fait, ce qui me gêne le plus, c'est que la démonstration utilise les nombres transfinis : n'est-ce pas une "entourloupe" de passer par des entiers non standards ?

    Je vois bien que ma question paraît naïve aux yeux de certains compte tenu des réponses que j'ai reçues, mais je suis vraiment gêné. D'un côté, je me dis "on s'en fiche", c'est comme quand on passe par les nombres complexes pour résoudre un problème sur les nombres réels ; d'un autre côté, je me dis qu'il y a quelque chose de plus profond... et à vrai dire, je suis vraiment gêné par ce nombre $\omega$.
  • En coup de vent, je n'ai âs regardé la vidéo, mais je trouve cet exemple malsain car on le prend parfois pour dire qu'il ne se prouve pas dans Peano, mais en fait, c'est con, il ne s'énonce pas dans Peano, il ne risque donc pas de s'y trouver. Comme dit Martial, au moins les suites de Godstein c'est plus réglo : ça s'exprime dans Peano et ne s'y prouve pas.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • C'est un théorème de ZF mais non de PA, c'est tout.
  • $\omega$ c'est simplement la première piaule du premier étage de l'hôtel de Hilbert, les entiers occupant le rez-de-chaussée.

    Attention, il ne faut pas confondre ordinaux infinis et entiers non standards. S'il existe des entiers non standard ils vont indexer des chambres qui sont situées tout à droite du RDC de l'hôtel (bonjour la dame qui fait le ménage !), mais tu vois bien qu'ils sont tous $< \omega$
  • @Christophe : bien vu, je n'avais pas pensé à ça. Le problème n'est pas formalisable dans Peano, donc c'est certes plus ludique que Goodstein mais, comme tu dis, c'est moins réglo.

    @rebellin : je t'explique pourquoi on ne peut pas énoncer le problème de l'hydre dans Peano : il suffit de reprendre les explications de Calli. Si tu voulais l'écrire il faudrait que tu dises : "je suppose que l'hydre a un nombre standard de têtes". Et ça tu ne peux pas, car un modèle non standard ne sait pas qu'il est non standard. En particulier il est incapable de différencier ses éléments standards des autres. C'est un peu la chaîne de Darwin, qui part d'un singe pour arriver à un homme. Pourtant, le fils d'un singe est toujours un singe, et le père d'un homme est toujours un homme.

    Par contre, le truc des suites de Goodstein peut s'écrire dans Peano. Mais ce qui est marrant c'est que l'énoncé (dans Peano) est plus difficile et plus long à écrire que la démonstration (dans ZFC).
  • Vraiment, le problème n'est pas formalisable dans Peano ? Ça m'étonne. On peut bien y coder des arbres de preuves, alors pourquoi pas des hydres ?
  • @Calli : en fait je n'en sais rien. J'ai fait confiance à Christophe, et puis je me suis basé sur ton raisonnement avec les nombres standards de têtes, mais peut-être que je suis à côté de la plaque.
  • Ben, on peut coder avec des entiers des arbres, donc a fortiori des hydres, et on sait aussi coder par des entiers des listes de trucs qu'on sait coder. Donc "l'hydre sera vaincu peu importe la stratégie d'Hercule" m'a l'air de pouvoir s'exprimer dans le langage de Peano de la manière suivante :
    1. une formule $P(h)$ qui dit si un entier $h$ code une hydre
    2. une formule $Q(n)$ qui dit si un entier $n$ est une listes d'hydres (elle utilise la formule $P$)
    3. une fonction $\ell(n)$ qui donne la longueur de la liste $n$
    4. une fonction $f(n,i)$ qui a un $n$ codant une liste d'hydres associe la $i$-ième hydre
    5. une relation $S(h_1,h_2)$ qui dit si l'hydre $h_2$ est obtenu à partir de l'hydre $h_1$ auquel on a coupé une tête (et d'autres têtes ont éventuellement repoussé)
    6. finalement l'énoncé $$\forall n, \,Q(n) \Rightarrow ([\forall i,\, i<\ell(n) \Rightarrow S(f(n,i),f(n,i+1))] \wedge f(n,\ell(n)) = \text{l'hydre sans tête}).$$
    Dans un modèle non standard de Peano, on risque d'avoir des entiers non standard codant des hydres d'après la formule $P$, mais ce ne seront pas de vraies hydres. Donc on ne peut pas trouver de formule $R(h)$ qui dit si $h$ est un entier standard qui code une hydre, mais je pense qu'on peut écrire une formule $P$ telle que tout entier standard $h$ vérifie "$P(h) \Rightarrow h$ code une hydre". C'est suffisant pour formaliser le problème de manière satisfaisante.
  • @Calli : "Hydre" est féminin.
  • Merci Poirot.
  • @Calli: c'est un jeu qui alterne sans borne uniforme des $\forall $ et des $\exists$ (si mes couvenirs de ce conte sont exacts), ce n'est pas de la forme "je sais à l'avance quelles têtes vont repousser et j'ai juste à exhiber une suite finie qui gagne"

    Bon, bien sûr, on peut "taffer" pour approcher ça artificellement dans Peano, mais didactiquement, c'est désastreux puisqu'il est prouvé que seule l'alternance de quantificateurs est ce qui fait monter les marches de la complexité en maths.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!