Pero entonces, argumentar que en AP no puede demostrarse que Hércules siempre vence no es tan sencillo, ¿no?
No, no es tan sencillo. En el hilo hemos analizado la estrategia consistente en cortar en cada asalto la cabeza más alta y, de entre las de altura máxima, la que tenga mayor número de hermanas, y hemos visto que en AP podemos probar que Hércules siempre gana si usa esa estrategia.
La situación es distinta si consideramos la estrategia opuesta: cortar en cada asalto la cabeza de menor altura y, de entre las que altura mínima, la que tenga un menor número de hermanas.
Esta estrategia es definible en AP, pero se puede demostrar que no es posible demostrar en AP que es una estrategia ganadora.
Pero la única prueba que conozco usa cálculo secuencial (el el teorema 8.27 de mi libro de Cálculo secuencial).
Un poco más de detalle: Podemos considerar la función \( N(\alpha) \) que determina el número de asaltos necesarios para vencer a la Hidra de ordinal \( \alpha \) siguiendo la estrategia indicada, y es trivialmente una función recursiva, pues un ordenador puede calcularla: sólo tiene que ir calculando el combate siguiendo la estrategia y dar como salida el número de asaltos que ha necesitado para acabar.
Que sea recursiva se traduce en que existe una fórmula aritmética \( \psi(\alpha, n) \) (con una estructura especialmente simple, a saber, que consta de un único cuantificador existencial seguido de una fórmula con cuantificadores acotados) que la representa en AP, es decir, que si se cumple \( N(\alpha) = n \), en AP se puede demostrar \( \phi(\bar \alpha, \bar n) \) y si \( N(\alpha) \neq n \), en AP se puede demostrar \( \lnot \phi(\bar \alpha, \bar n) \), donde \( \bar \alpha \) y \( \bar n \) son los numerales correspondientes a los números naturales \( \alpha \) y \( n \) (por ejemplo, si \( \alpha = 3 \) entonces \( \bar\alpha = SSS0 \)).
Eso significa que toda función recursiva se puede calcular en AP. Sin embargo, eso no significa que sea
demostrablemente recursiva. Eso quiere decir que en AP se pueda demostrar \( \forall \alpha \exists ! n\, \psi(\alpha, n) \), lo que supone demostrar que \( \psi \) define una función sobre todos los números naturales. (En realidad la clave es la existencia, pues la unicidad se puede garantizar siempre modificando la fórmula \( \psi \).)
Pues bien, si en AP se pudiera probar que la estrategia que he descrito es ganadora, la función \( N(\alpha) \) sería demostrablemente recursiva en AP, pues eso es lo que significa que la estrategia es ganadora, que, para todo \( \alpha \) existe un número de asaltos \( n \) tras el que la Hidra muere. Pero sucede que eso es falso: la función \( N(\alpha) \) no es demostrablemente recursiva en AP, pero la prueba no es trivial.
