¿Por qué ' t allí cualquier primer orden las oraciones que tienen la propiedad de ser verdadera en todos los modelos no estándar de PA y falso en el estándar?

Question

Me gustaría saber donde está el siguiente resultado viene (es decir, si hay un más general el resultado, del que se desprende o de lo contrario ¿cómo puede ser probada):

No es de primer orden de la frase es verdadera en todos los no-estándar de los modelos de la aritmética, pero falso en el estándar, mientras que no son de segundo orden, las oraciones que tienen esta propiedad.

(He encontrado esta afirma brevemente en el artículo de la wikipedia en Nonfirstorderizability)

Ayuda se agradece mucho. Gracias!

Mejor,

Berta

Answer 1

Sea $\varphi$ cualquier frase que es falsa en los números naturales. Sea teoría $T$ Peano de primer orden aritmético $\lnot\varphi$ como un axioma adicional. $T$ Tiene un modelo, los números naturales. Así por el teorema Lowenheim Skolem, $T$ tiene modelos de cardinality arbitrariamente alta y, en particular modelos diferente $\mathbb{N}$. La frase $\varphi$ no es cierto en ese modelo.

Answer 2

Deje $\varphi$ ser una oración que es verdadera en todos los no-estándar de los modelos de la aritmética, pero falso en el modelo estándar.

Entonces la teoría T se construye por la suma de $\neg \varphi$ a los axiomas de Peano tiene un único modelo; el modelo estándar de la aritmética.

Por lo tanto, cada declaración $P$, en el lenguaje de la teoría de números es verdadera en todo modelo de $T$ o falso en cada modelo de $T$. En particular, Gödel integridad del teorema implica que cada una de dichas $P$ es comprobable o disprovable: $T$ es completa.

Nuestros axiomas para $T$ son recursivamente enumerable, por lo que Gödel primer teorema de la incompletitud implica $T$ debe ser incompleta: de este modo obtenemos una contradicción.

Answer 3

Para entender este hecho, véase George Boolos, la Lógica de la Lógica y la Lógica (1998), página 57 :

[Considerar la fórmula : ]

(C) $\quad \exists X(\exists x Xx \land \forall x \forall y[Xx \land (x = 0 \lor x = y+1) \rightarrow x \ne y \land Xy])$.

[Esto] es una oración que es verdadera en todos los modelos no estándar de la aritmética, pero falso en el modelo estándar [nota : Para ver que (C) es verdadera en todo modelo no estándar, tomar como $X$ el conjunto de todos los elementos no estándar del modelo. $X$ es no vacío, no contiene $0$, por lo tanto, contiene sólo sucesores, y contiene el predecesor inmediato de cualquiera de sus miembros.]

A ver que es falso en el modelo estándar, supongamos que hay algunos adecuado establecer $X$ de los números naturales. $X$ debe ser no vacío: si por lo menos su miembro $x$$0$, vamos a $y = 0$; de lo contrario $x = y + 1$ algunos $y$. Desde $x$ es menos, $y$ no $X$, e "$Xy$" es falsa.

Para los no-estándar de los modelos de primer orden $\mathsf {PA}$, ver George Boolos & John Burgess & Richard Jeffrey, Computabilidad y la Lógica (5ª ed - 2007), página 304 :

En resumen: los elementos del dominio de cualquier modelo no estándar $\mathcal M$ de la aritmética va a ser linealmente ordenado DE MENOS a más. Este orden se han inicial segmento que es isomorfo a la habitual ordenación de números naturales, seguido por un secuencia de bloques, cada uno de los cuales es isomorfo a la habitual orden de los números enteros (negativo, cero, y positivo). No es ni primera ni última bloque, y entre dos cuadras se encuentra un tercero. Por lo tanto el orden de los bloques es lo que fue llamado [...] una densa lineal de pedidos sin extremos, y así, es isomorfo a la habitual orden de los números racionales.

Agregó

Suponiendo que hemos convencido a nosotros mismos de que la fórmula (C) es verdadera cada no-estándar modelo, pero falsa en $\mathbb N$, si suponemos que (C) es expresable en primer orden de la lógica, se puede utilizar como la fórmula $\varphi$ de Hurkyl la respuesta y la conclusión de la siguiente manera.

Answer 4

¿Por qué no hay ningún primer orden oraciones que tienen la propiedad de ser verdadero en todos los no-estándar de los modelos de PA y falso en el estándar?

No es un conjunto de oraciones con la propiedad de que todas las frases son verdaderas en todos los no-estándar de los modelos de PA, pero infinitamente muchas son falsas en el estándar:

$\omega \neq 0$, $\omega \neq \sigma(0)$, $\omega \neq \sigma(\sigma(0))$, ...

Para estas fórmulas a ser penas, $\omega$ debe ser una constante y parte de la firma de $S=\{\sigma,0,\omega\}$.