Sobre un modelo explícito para $\mathbf Q$ con la negación del axioma de inducción

Question

Llevo un tiempo pensando en los modelos no estándar de Aritmética Robinson (de aquí en adelante denominados $\mathbf Q$ ), concretamente aquellas en las que la inducción ( $\mathbf{AI}$ ) falla. Esto puede ocurrir de dos maneras: (1) $\mathbf Q$ se deja tal cual sin inducción y se analizan los modelos no estándar sobre ella, y (2) añadimos la negación de $\mathbf{AI}$ a $\mathbf Q$ (un sistema que he bautizado estrafalariamente como Aritmética Hume ) y busca un modelo en él.

En este post me centraré principalmente en este último enfoque. $\neg \mathbf{AI}$ implica que existe una fórmula con una variable libre $P$ tal que $P(0) \wedge \forall x (P(x) \rightarrow P(x'))$ es cierto pero $\forall x P(x)$ no se sostiene. Llevo unos meses dándole vueltas a este asunto, pero no encuentro ningún modelo que pueda satisfacer mis necesidades. $\neg \mathbf{AI}$ y mucho menos una fórmula específica. Sé que debe existir porque para $\mathbf{Q}$ y $\mathbf{PA}$ ser sistemas diferentes entonces $\mathbf{AI}$ tiene que ser contingente en $\mathbf{Q}$ .

¿Alguna ayuda para encontrar un modelo de este tipo? Y sé que puede parecer una tontería, pero si vas a dar una respuesta explícita sobre un modelo, ¿puedes añadir una advertencia de spoiler? Me doy cuenta de que con mis habilidades y conocimientos actuales no puedo resolver esto, pero aún así me encantaría intentarlo por mí mismo, ¡aunque sea con un poco de ayuda!

Answer 1

¡Buena pregunta!

En mi opinión, el modelo no estándar más sencillo de $Q$ consiste en polinomios (en una variable). En concreto $\mathfrak{P}$ sea el conjunto formado por todos los polinomios de coeficiente entero en la variable $x$ con coeficiente principal positivo ... y también el polinomio cero. Con sucesor, suma y multiplicación definidos de la manera obvia, $\mathfrak{P}$ forma un modelo de $Q$ y esto es fácil de comprobar.

(En este punto también es una buena idea comprobar que un par de otras ideas obvias no trabajo: por ejemplo, el conjunto de todos los polinomios con coeficientes enteros no da lugar a un modelo de $Q$ .)

Es una estructura muy bonita, y algo que no es difícil de cuidar. Pero afirmo que la inducción se rompe en ella... ¡muy muy mal de hecho! Dijiste que no querías spoilers, así que he ocultado la respuesta completa más abajo, pero te doy una pista: piensa en paridad (incluso contra impar) .

La idea clave es que, aunque todo número natural es par o impar, no tiene mucho sentido preguntarse si el polinomio " $x$ "es par o impar. Esto motiva el siguiente contraejemplo a la inducción en $\mathfrak{P}$ : ver la propiedad $EoO(a)$ = "O bien para algunos $b$ tenemos $S(b+b)=a$ o para algunos $b$ tenemos $b+b=a$ ." Es fácil comprobarlo en $\mathfrak{P}$ , $(i)$ no todos los elementos cumplen $EoO$ pero $(ii)$ 0 satisface EoO y $(iii)$ si $a$ satisface $EoO$ entonces $S(a)$ también satisface $EoO$ . Así que esto constituye de hecho un fracaso de la inducción en $\mathfrak{P}$ .

---

Por cierto, has tenido mucha suerte aquí en tu elección de $Q$ específicamente.

Hay muchas teorías entre $Q$ y PA, generalmente de la forma [axiomas de semiring ordenados] + [algún fragmento del esquema de inducción completo]. Por ejemplo, la teoría I $\Sigma_1$ consiste en los axiomas de sembrado ordenado junto con el esquema de inducción para $\Sigma_1$ fórmulas. Se trata de una teoría atractiva en muchos contextos, y -como $Q$ - la distancia entre él y PA se mide por inducción. Pero hay un sentido importante en el que $Q$ es manso de una manera que $\Sigma_1$ no lo es: a saber, Teorema de Tennenbaum . La teoría I $\Sigma_1$ no tiene modelos no estándar "fácilmente descriptibles", por lo que aunque se podría hacer la misma pregunta sobre I $\Sigma_1$ no obtendrías una respuesta tan rápida.

En general, el teorema de Tennenbaum explica una laguna evidente en la literatura: ¿por qué, en toda la discusión sobre el carácter incompleto de la AP, no hay análisis de modelos específicos no estándar interesantes de AP? La respuesta es que Tennenbaum descarta en gran medida esta posibilidad. Esto también ayuda a motivar $Q$ : Robinson encontró una teoría que es lo suficientemente débil como para tener montones de modelos interesantes, fácilmente descriptibles y muy diferentes, al tiempo que es lo suficientemente fuerte como para estar sujeta al teorema de incompletitud de Godel.