Posterior: Ilustración del Teorema de Arriba: El teorema de Goodstein Anterior: Sucesión de Goodstein

Función de Goodstein

Definimos a la función $G$ como

$$G:(a,m)\mapsto G:(a,m)=\min\{n\vert s_n(a,m)=0\}.$$

Puede probarse que la diagonal de $G$ ``domina'' a cualquier función recursiva, es decir:

$$\forall f\in\{\mbox{\rm funciones recursivas}\}\exists n_0: \ n\geq n_0\ \rightarrow\ f(n)<G(n,n),$$

con fines de la exposición aquí, y sin entrar en detalles técnicos, podemos pensar que las funciones recursivas son precisamente las funciones efectivamente computables. Se tiene, en consecuencia, que:

• $G$ no puede ser recursiva y
• el Teorema de Goodstein no es demostrable formalmente, pues
  • una demostración formal de él daría un algoritmo para calcular $G$, y no puede existir tal algoritmo pues la función que calcularía tal algoritmo estaría acotada a la larga por $G$.