¿Cómo no inducción en modelos no estándares computable?

Question

Tennenbaum del teorema no se aplica a la Aritmética de Robinson ($Q$). Hay una computable, no estándar del modelo de $Q$ "que consiste en la entero-coeficiente de polinomios positivos coeficiente inicial, más el cero del polinomio, con sus usuales de la aritmética."

¿Cuál es un ejemplo de cómo la primera orden de inducción esquema de falla en una computable, no estándar del modelo de $Q$? Puede que este modelo tiene un predicado, en el lenguaje de la Q, que sólo es cierto para el estándar de números naturales y falso de "infinito" números naturales? Puede una computable no estándar del modelo de recepción?

Dado que el modelo anterior, lo que es un ejemplo de una declaración, en el lenguaje de la $Q$, que es cierto para el polinomio cero y todos los sucesores de los cero del polinomio y falsa para otros polinomio en el modelo?

Answer 1

Aquí es aún más simple: "Cada número es par o impar." Que es, $$\forall x\exists y(x=y+y \mbox{ or } x=y+y+1).$$ The polynomial $x$ es un contraejemplo.

---

Ignorando el modelo específico y centrado en la teoría, también vale la pena señalar que Robinson aritmética ni siquiera demostrar que la suma es conmutativa o que el sucesor de un número es diferente de la que número! (Si recuerdo correctamente, esto está cubierto en Burgess libro de Fijación de Frege - ver una revisión en http://www.utexas.edu/cola/_files/iaa4774/On_Burgess_Fixing_Frege.pdf.)

EDIT: Ahora que miro más de cerca, esto es, básicamente, todos los cubiertos en la página de la wikipedia sobre la aritmética de Robinson, en la sección "Metamathematics"; le sugiero que lea y las referencias vinculadas.

ADEMÁS EDIT: Aquí es aún más declaraciones, con fácil de inducción de pruebas, que Robinson no creer! :P (tenga en cuenta que estos hacen en el hecho de sostener en el modelo específico en la OP.)

• $\sqrt{2}$ es irracional.

• Existen infinitos números primos. Más precisamente, "para cada $x$ hay un primer $>x$."

• Única factorización en números primos.

Ver Francois Dorais' como respuesta a http://mathoverflow.net/questions/19857/has-decidability-got-something-to-do-with-primes.

Answer 2

Este es otro ejemplo, $$\forall x(S(x)\neq x)$ $

Tiene $0$, y si tiene $x$, entonces tiene $S(x)$ así. Pero es posible tener un modelo con un elemento que es su propio sucesor.

Answer 3

Para una verdadera pena para los números naturales, pero falso en los polinomios descritos anteriormente, podemos utilizar $$\forall w\exists y_1\exists y_2\exists y_3\exists y_4(w=y_1^2+y_2^2+y_3^2+y_4^2),$ $ ya que por un resultado de Lagrange cada entero no negativo es la suma de cuadrados de #% de #% %, pero el polinomio $4$ no es una suma de $x$ cuadrados de polinomios.