¿Existe algún modelo natural conocido de la Aritmética de Peano donde falle el teorema de Goodstein?

Question

(Anteriormente hice esta pregunta en el sitio hermano aquí, pero no recibí respuestas).

El Teorema de Goodstein establece que cada secuencia de Goodstein eventualmente llega a 0. Resulta que este teorema no es demostrable en la Aritmética de Peano ($PA$) pero sí en $ZFC$.

Me gustaría "discutir" esto (tanto la demostración en $ZFC$ como la demostración de su imposibilidad en $PA$) en una conferencia de una hora a un grupo de estudiantes de posgrado (sin formación previa asumida, el discurso farragoso no solo está permitido, sino que se anima). Debido a charlas anteriores que he dado, creo que no tomará demasiado tiempo cubrir/recodarles los conceptos básicos de un curso semestral de lógica de primer orden (por ejemplo, el teorema de compacidad y el teorema de completitud, etc).

El problema es que las demostraciones de imposibilidad que he encontrado (las mismas que están enlazadas en el artículo de Wikipedia) son bastante difíciles para este contexto. En pocas palabras, estoy buscando la prueba más fácil conocida.

Por ejemplo, me encantaría una demostración de imposibilidad que funcione exhibiendo un modelo de $PA$ en el cual falle el teorema de Goodstein. Tales modelos existen necesariamente gracias al teorema de completitud, ya que "$PA$ + el teorema de Goodstein es falso" es consistente.

¿Alguien ha demostrado la independencia del teorema de Goodstein exhibiendo un modelo de $PA$ donde ha fallado el teorema de Goodstein?

Con el objetivo de obtener una prueba lo más simple posible, me encantaría ver una prueba que utilice las ideas de compacidad y completitud, algo como mostrar que hay un conjunto $\Sigma = \{\phi_n\}$ de enunciados explícitos de primer orden (en un lenguaje ligeramente más amplio, por ejemplo) tal que

1) para cualquier $\Sigma_0\subseteq PA\cup \Sigma$ finito, el modelo estándar $\mathbb{N}$ modela $\Sigma_0$ y

2) la teoría $PA\cup \Sigma$ prueba que el teorema de Goodstein es falso.

¿Se conoce una prueba de este tipo? En general, ¿hay una prueba conocida de la demostrabilidad del teorema de Goodstein que sea accesible para alguien con solo un semestre o dos de clases de lógica?

Gracias y por favor siéntase libre de reetiquetar como sea necesario.

Answer 1

Tu estrategia de prueba a través (1) y (2) es imposible. Si $PA\cup\Sigma$ demuestra que el teorema de Goodstein es falso, entonces la prueba tendrá longitud finita, y por lo tanto habrá algún $\Sigma_0$ finito tal que $PA\cup\Sigma_0$ demuestre que el teorema de Goodstein es falso. Esto implicaría, por (1), que el teorema de Goodstein es falso en el modelo estándar. Pero el teorema de Goodstein se mantiene en el modelo estándar, como Goodstein demostró.

Un segundo punto es que podrías encontrar que no hay modelos "naturales" específicos de PA aparte del modelo estándar. Por ejemplo, Tennenbaum demostró que no hay modelos no estándar computables de PA; es decir, no se puede exhibir un modelo no estándar de PA de forma tan explícita que la adición y multiplicación del modelo sean funciones computables. (Ver esta pregunta relacionada en MO.) Pero no descarto que podría haber modelos no estándar naturales en otros sentidos.

Answer 2

No estoy seguro de entender lo que quieres decir con "natural".

De todos modos, la prueba de Kirby-Paris es "teórica del modelo" o tan "explícita" como es probable que encuentres. La referencia es Resultados de independencia accesibles para la aritmética de Peano. Boletín de la London Mathematical Society 14 (1982), 285-293. (Puedo enviarte el artículo por correo electrónico si no puedes encontrarlo fácilmente. Es una lectura interesante.)

El argumento utiliza el método de los indicadores. La idea (de manera muy general) del método es comenzar con un modelo no estándar de PA (cualquiera servirá, para algunos resultados más específicos puede ser necesario prestar atención a este paso, pero aquí cualquier modelo no estándar es suficiente) y usar la función de Goodstein $G$ (la función que asigna a $n$ el número de pasos que la secuencia toma para llegar a 0) para encontrar un corte. Se trata de un segmento inicial de tu modelo no estándar que es en sí mismo un modelo de PA, pero el corte se construye explícitamente para que para algún $N$ no estándar en el corte el número de pasos $G(N)$ esté más allá del corte. Por lo general, esto requiere que produzcas `indiscernibles' que se utilizan para garantizar que los axiomas de inducción se cumplan en tu corte. Es un método muy útil y la base de la mayoría de los resultados independientes conocidos en PA. (Los teoremas de Paris-Harrington y Kanamori-McAloon son otros ejemplos bien conocidos).

Escribí un pequeño artículo que muestra que un resultado bien conocido de teoría de la prueba sobre PA se puede utilizar para probar la indemostrabilidad del teorema de Goodstein. La idea del artículo es una fórmula explícita para $G$. Puedes encontrarlo en mi página, o también puedo enviártelo por correo electrónico si estás interesado.