¿Existe un modelo natural de la Aritmética de Peano donde falla el teorema de Goodstein?

El teorema de Goodstein es la afirmación de que cada secuencia de Goodstein finalmente llega a 0. Se sabe que es independiente de la aritmética de Peano (PA) y, de hecho, fue el primer resultado puramente teórico de números. Es demostrable en ZFC.

Una forma de expresar esto es que la teoría "PA + el teorema de Goodstein es falso" es consistente (suponiendo que PA lo sea).

Por el teorema de completitud de Gödel, debe existir un modelo de AP en el que falle el teorema de Goodstein. De hecho, aplicando el teorema de Lowenheim-Skolem hacia abajo, podemos asumir que este modelo es contable.

Sin embargo, con el interés de hablar sobre este resultado a un grupo de estudiantes de posgrado (de diversos intereses), me gustaría ejecutar esto al revés. Entonces,

¿Existe algún modelo contable no estándar conocido, obvio o fácil de construir? PAG A ¿En qué falla el teorema de Goodstein?

Al responder a esto, estoy dispuesto a aceptar los teoremas lógicos de primer orden "fundamentales": los resultados de completitud y compacidad de Godel, el teorema de Lowenheim-Skolem.

Aquí está el tipo de respuesta que realmente me gustaría: hay una colección contable explícita Σ = { ϕ norte } de oraciones de primer orden (posiblemente en un lenguaje un poco más grande) tal que norte es un modelo de PAG A + Σ 0 para cualquier finito Σ 0 Σ , y tal que PAG A + Σ implica que el teorema de Goodstein es falso.


Un enfoque en el que he pensado es primero ampliar el idioma agregando un símbolo constante c. A continuación, deja ϕ norte ser el enunciado "La sucesión de Goodstein para C lleva más de "n" pasos para terminar". (Aunque personalmente no sé cómo codificar "la secuencia de Goodstein para C " en lenguaje de primer orden, estoy seguro de que se puede hacer, porque de lo contrario, uno ni siquiera podría formular "PA demuestra que la secuencia de Goodstein converge".)

En este caso, norte es un modelo de cualquier PAG A + Σ 0 simplemente estableciendo c = n+1, donde n es el subíndice más grande de a ϕ k en Σ 0 (que existe porque Σ 0 es finito).

Por los teoremas de Gödel y Lowenheim-Skolem, PAG A + Σ tiene un modelo contable METRO . Entonces la interpretación de C en este modelo cumple ϕ norte para todos norte , y por lo tanto la sucesión de Goodstein no termina para C en este modelo

Sin embargo, dado que la independencia del teorema de Goodstein fue tan difícil de probar, estoy bastante seguro de que hay un error en esta línea de razonamiento (aunque no sé dónde). Me encantaría que alguien arreglara esto en algo correcto.

Como siempre, siéntase libre de volver a etiquetar según sea necesario, ¡y gracias por las respuestas!

No estaba seguro de si esto encajaría mejor aquí o MO. Estoy abierto a escuchar las opiniones de los demás sobre este asunto.
Parecería ser apropiado en cualquier sitio, aunque sospecho que es más probable que obtenga una respuesta en MO.
Le daré un día o 2 en este sitio para ver si obtengo alguna respuesta. Si no, ¿cuál es el curso de acción adecuado? ¿Debo eliminar esta página? ¿Debo responder con cualquier respuesta que obtenga en MO (hecho CW para que no gane reputación por ello)?
No conozco ninguna prueba de compacidad fácil para generar un modelo donde falle el teorema de Goodstein, pero escribí una respuesta a continuación explicando el problema con el argumento que esbozaste.
Acabo de hacer la pregunta en MO: mathoverflow.net/questions/37329/…

Respuestas (1)

Aquí está la falla en el argumento de compacidad que bosquejaste. En el modelo que construyes, la interpretación de C será de hecho un número no estándar cuya secuencia de Goodstein no se detiene en un número estándar de pasos. Pero el teorema de Goodstein tiene un cuantificador universal para el número de pasos, por lo que también se permiten "secuencias de Goodstein" no estándar. Es decir, cuando el teorema dice "hay una secuencia finita", en un modelo particular esa secuencia "finita" podría tener la longitud de un número no estándar, que no puede ser excluido por la secuencia de oraciones en su argumento.

Una forma de encontrar una extensión de PA donde el teorema de Goodstein sea demostrable es agregar suficiente inducción transfinita a PA para formalizar la prueba habitual del teorema de Goodstein. Los detalles de cómo hacerlo no son tan malos, aunque pueden llevar demasiado tiempo para una clase de primaria.

¡Gracias por señalar la falla en mi argumento! Sabía que no podía ser tan fácil.