Siguiente: Ilustración del Teorema de Un nivel arriba: El teorema de Goodstein Anterior: Representación formal en base

Sucesión de Goodstein

Para $a\in N$ y $m\geq 2$ dados, definiremos a la sucesión de Goodstein $S(a,m)=\left\{s_n(a,m)\right\}_{n\geq 0}$ de manera recursiva. Para ello nos auxiliaremos de la sucesión $B(a,m)=\left\{b_n(a,m)\right\}_{n\geq 0}$ definida igualmente de manera recursiva. Explícitamente, hacemos

$$\begin{array}{rlcl} & b_0 = m &;& s_0 = a \vspace{2ex} \\ ... ...& s_{n+1} = \mbox{\it rp}(s_n,b_{n+1}\vert b_n) -1 \end{array}$$

Ejemplo. Para m=2 y a=100 tenemos $\mbox{\it rp}_2(100)=2^{2^2+2} + 2^{2^2+1} +2^2.$ Luego

$$\begin{eqnarray*}s_0(100,2) &=& 2^{2^2+2} + 2^{2^2+1} +2^2 \\ &=& 100 \\ s_1(1... ...2\cdot 4^2 +2\cdot 4 +1 \\ &=& O(2^{512}) \\ \vdots && \vdots \end{eqnarray*}$$

Sorpresivamente tenemos que ... ¡la sucesión de Goodstein converge a cero!



Teorema de Goodstein: $\forall a \forall m \exists n:\;s_n(a,m)=0.$

• el teorema se cumple en $I\!\!N$: el modelo estándar de los números naturales, sin embargo
• no es demostrable en la aritmética de Peano,
  • en términos de (a,m), el mínimo n que anula a la sucesión de Goodstein crece vertiginosamente rápido.

Función de Goodstein: Definimos a la función G como

$$G:(a,m)\mapsto G:(a,m)=\mathop{\rm 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).$$

Se tiene:

• 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.

Siguiente: Ilustración del Teorema de Un nivel arriba: El teorema de Goodstein Anterior: Representación formal en base