¿Cómo Gödel Integridad fallar en segundo orden, la lógica?

Question

Así que hace un tiempo vi una prueba de la Integridad Teorema, y la parte más difícil de todo, lógicamente válidas las fórmulas de tener una prueba de) fue de esta manera:

Tome una teoría de la $K$ como la base de su teoría. Supongamos $\varphi$ es lógicamente válida, pero no es un teorema. A continuación, puede agregar $\neg\varphi$ $K$'s axiomas, la formación de una nueva teoría de la $K'$, lo que es consistente, y por lo tanto $K'$ tiene un modelo de $M$. Desde $\neg\varphi$ es un axioma de la $K'$, $M\models\neg\varphi$, pero desde $\varphi$ es lógicamente válido en $K$ $M$ es también un modelo de $K$, $M\models\varphi$, contradicción. Por lo tanto, $\varphi$ debe ser un teorema de $K$.

Lo que tiene sentido para mí, pero yo no veo cómo el anterior falla en segundo orden, la lógica? Este teorema se ve perfectamente generalizables a segundo orden de la lógica, yo no veo ninguno de los pasos que no se podía hacer allí.

Es el teorema de la correcta? Si no, ¿por qué? Si es así, que la parte que falla en segundo orden, la lógica?

--EDIT:

Como fue comentado, tengo tres isomorfo respuestas, y yo no puedo conjunto de todos ellos como la verdadera respuesta así que me puse a la que fue formulada de la manera más clara para mí. En cualquier caso, muchas gracias a todos!

Answer 1

La propiedad de que "cada coherente de la teoría tiene un modelo" hace que no se mantenga de segundo orden de la lógica.

Considere, por ejemplo, el de segundo orden axiomas de Peano, que son bien conocidos por tener sólo $\mathbb N$ como su modelo (en el estándar de la semántica). Extender el lenguaje de la teoría con una nueva constante $c$, y añadir nuevos axiomas $$ c\ne 0 \\ c\ne S0 \\ c\ne SS0 \\ \cdots $$

La teoría ampliada aún es consistente, es decir, se puede probar una contradicción, porque cuentan con una prueba debe ser finito, y sólo se puede mencionar un número finito de los nuevos axiomas, y no es un modelo tan largo, ya que sólo toma un número finito de estos axiomas.

Pero la teoría ampliada no tiene un modelo, debido a que el modelo tendrá que ser exactamente $\mathbb N$ con el fin de satisfacer la original axiomas de Peano, pero debe tener un $c$ que es no un número en orden a satisfacer a todos los nuevos axiomas.

Answer 2

Primero de todo, incluso en el caso de la orden de que la "prueba" no funciona: ¿cómo usted consigue $M$? Usted necesita la suposición de que, si $K'$ es consistente, entonces tiene un modelo; pero esto es exactamente lo que usted está tratando de demostrar.

En segundo lugar, con el fin de preguntar si la integridad teorema vale para la de segundo orden, la lógica, tenemos que definir lo que es una "prueba" es de segundo orden de la lógica.

Como cuestión de hecho, podemos demostrar que no hay ningún razonable noción de la prueba de segundo orden de la lógica, a todos! Esto es debido a que de segundo orden, la lógica no es compacto: hay un conjunto de oraciones $K$, y una frase $\varphi$, de tal manera que (i) $\varphi$ es una consecuencia lógica de $K$, pero (ii) $\varphi$ no es una consecuencia lógica de cualquier subconjunto finito de $K$. (El ejercicio. SUGERENCIA: buscar un $\varphi$ que caracteriza a $(\mathbb{N}; +, \times)$ hasta isomorfismo.) Esto significa que cualquier tipo de prueba de sistema de segundo orden de la lógica, para ser completa, tendría que permitir infinitamente larga pruebas en un cierto sentido.

Answer 3

Tomar el lenguaje de la aritmética, aumentada por una sola constante símbolo $c$. Ahora agrega a la Peano [de segundo orden] axiomas en el siguiente esquema, $0<c$, $s(0)<c$ y así sucesivamente.

Si esta teoría es consistente, entonces debe haber un modelo. Pero de segundo orden Peano sólo un modelo. Así que tiene que ser ese modelo. Pero ¿cómo va a interpretar $c$ no? Usted no puede.

De modo que la teoría es inconsistente. Así una contradicción debe ser demostrable a partir de un número finito de axiomas. Pero dado cualquiera de un número finito de axiomas, usted puede encontrar algunos lo suficientemente grande como número natural tal que la interpretación de $c$ con que valor está bien. Por lo que cualquier un número finito de axiomas a partir de esta teoría no demostrar una contradicción.

Así que usted tiene una teoría sin un modelo, pero sin inconsistencias. Así la integridad (y compacidad) no.

Answer 4

El teorema de compacidad necesarios para la prueba de "cada coherente de la teoría tiene un modelo" no es válido en la lógica de segundo orden. Que dónde está el problema.