Desbordamiento en modelos computables no estándar

Question

Teorema de los Tennenbaums no se aplica a Aritmética Robinson ( $Q$ ) . Existe un modelo computable y no estándar de $Q$ "consistente en polinomios de coeficiente entero con coeficiente inicial positivo, más el polinomio cero, con su aritmética habitual".

Hace poco pregunté ¿Cómo falla la inducción en los modelos computables no estándar? Un ejemplo fue $\forall x \exists y(x=y+y \lor x=S(y+y))$ . En el modelo anterior esto falla para el número no estándar infinito representado por el polinomio $x+1$ que no es ni par ni impar. Este predicado es verdadero para el número no estándar representado por $2x$ y los sucesores de $2x$ .

Es tentador pensar que este predicado puede utilizarse para elegir los números naturales estándar. Elegimos los números que son pares o Impares y menores que el número representado por el polinomio $x$ . El problema es que no hay un número finito para el número representado por el polinomio $x$ . No podemos escribir $\forall x < SSS...SSS0$ en la lengua de $Q$ . Podríamos pedir el número más pequeño que no es ni par ni impar pero esto sería como pedir el número más pequeño no estándar.

¿Es este predicado en este modelo un ejemplo de derrame ? Si no es así, ¿en qué se diferencia de los vertidos?

Answer 1

Tienes razón, "es par o impar" no mata el desbordamiento - sin embargo el desbordamiento falla en ese modelo a través de una fórmula estrechamente relacionada: concretamente, la fórmula "Cada $y<x$ es par o impar", o $$\varphi(x)\equiv\forall y[y<x\rightarrow[(\exists z(y=2z))\vee(\exists z(y=2z+1))]],$$ caracteriza a los números naturales. (Para ser $100\%$ preciso: si $M$ es el modelo que usted describe y $N\subset M$ es el segmento inicial correspondiente a $\mathbb{N}$ entonces $\varphi^M=N$ .)

Esbozo de prueba: Claramente $\varphi(n)$ es válida para cada $n\in\mathbb{N}$ . Así que el punto importante es el inverso. En primer lugar, demuestre que para cualquier no constante polinomio $p$ tenemos $p>x-n$ para algún número natural $n$ . Entonces, basta con observar que ningún polinomio de la forma $x-n$ es par o impar.

---

Obsérvese que esto no es más que una agudización de la afirmación de que "todo número es par o impar" atestigua el fracaso de la inducción. Hasta donde yo sé, toda sentencia natural que atestigua el fracaso de la inducción en $M$ puede modificarse fácilmente (con el mismo truco de decir "Para cada número menor ") para que también sea testigo del fracaso del desbordamiento, es decir, para definir $\mathbb{N}$ .

EDIT: Sólo para completar, aquí hay un contraejemplo de inducción que no lo hace convertir en un contraejemplo al desbordamiento de la manera indicada anteriormente: $$\psi(x)\equiv\exists y, z<x\forall w<x\exists k\in\mathbb{N}[(w=y+k)\vee (w+k=y)\vee(w=z+k)\vee(w+k=z)].$$ Aquí, " $\exists k\in\mathbb{N}$ "es la abreviatura de " $\exists k[\varphi(k)\wedge . . .]$ ," donde $\varphi$ es la fórmula que define $\mathbb{N}$ dado arriba.

La fórmula $\psi$ se traduce en "Hay dos elementos $y, z<x$ de manera que todo $<x$ está a una distancia finita de cualquiera de los dos $y$ o $z$ ." Esto escoge exactamente a los naturales, y polinomios de la forma $X\pm j$ (p. ej., establecer $y=X$ y $z=0$ - hay otras opciones). También satisface claramente las hipótesis de la inducción.

BÁSICO: cualquier contraejemplo a la inducción produce una corte definible (el segmento inicial más largo del modelo en el que se cumple el contraejemplo sin excepción); sin embargo, estos cortes definibles no tienen por qué ser exactamente los $\mathbb{N}$ -pieza, y es coherente que haya un corte propio fácilmente definible pero $\mathbb{N}$ no es un corte definible. Obsérvese que, por el contrario, un contraejemplo de desbordamiento es (por definición) una instancia de la $\mathbb{N}$ -pieza siendo un corte definible.