Algunas preguntas generales sobre la lógica de primer orden.

Question

Actualmente estoy trabajando a través de Peter Smith "Introducción a los Teoremas de Gödel'.

Me pregunto cómo una formalización de la lógica de primer orden que nos permite demostrar los teoremas de la incompletitud, etc. podría parecer. Es de primer orden de la teoría misma? Parece hacer algunos de segundo orden de las declaraciones. Por ejemplo, cuando se habla de la Aritmética de Peano, queremos hablar sobre el conjunto de la 'real' números naturales, es decir, los sucesores de 0 y nada más. A continuación, de nuevo, la teoría de conjuntos se las arregla para decir las cosas con la primera orden lógico que se sienta más como de orden superior de la lógica.

En particular, me pregunto si la lógica de primer orden puede ser demostrado ser coherente en sí mismo. Si no, ¿qué tipo de consistencia de los resultados son con respecto a la primera orden de la lógica?

Gracias.

Answer 1

Tome la segunda a la primera pregunta:

Me pregunto si la lógica de primer orden puede ser demostrado ser coherente en sí mismo.

Es un libro de texto de resultados en matemáticas de la lógica de texto que un estándar de sistema deductivo de la lógica de primer orden (elija su favorito, la axiomática de Hilbert-estilo, deducción natural de estilo, cuadros de estilo ...) es constante. Es decir, usted no puede derivar algo de la forma $C \land \neg C$ a partir de suposiciones en el sistema deductivo. (Aparte: tal vez es un poco preocupante que preguntar eso. Realmente me gustaría sugerirle a nadie que hacer frente a una primaria de matemáticas de la lógica de texto que cubre este tipo de cosas antes de intentar conseguir su cabeza ronda cosas más avanzadas como los teoremas de incompletitud ...)

Me pregunto cómo una formalización ... que nos permite demostrar los teoremas de la incompletitud, etc. podría parecer.

Para fijar ideas, consideremos (la mitad) del primer teorema de primer orden de la Aritmética de Peano, PA. Ese es el resultado (F) que si PA es consistente, entonces PA no prueba $\mathsf{G}_{PA}$. Este es un resultado acerca de las expresiones (wffs) y las relaciones entre ellos, así que tenemos que formalizar una teoría acerca de las expresiones. Pero las expresiones son finitos y objetos que nos pueden dar los números de código para ellos (ese es el truco que uso en informalmente demostrando (F)). Así, utilizando la codificación de truco, podemos expresar (F) en el lenguaje de la aritmética de sí mismo. Deje $\mathsf{Con}$ ser la expresión aritmética que los códigos que PA es consistente. Y la expresión que $\mathsf{G}_{PA}$ es improbable en el PA es ... espere! -- $\mathsf{G}_{PA}$ sí. Así podemos expresar (F), a través de la codificación, en el lenguaje de la aritmética como $\mathsf{Con} \to \mathsf{G}_{PA}$.

OK, así que ¿qué se necesita para demostrar formalmente esta frase (es decir, para dar un formalizado la prueba de la mitad del primer teorema de la incompletitud de PA)? Así, la prueba del primer teorema es bastante elemental, por lo que era de esperar que fuese demostrable en cálculo elemental por lo que en PA en sí. Y lo es! [De hecho, como cabría imaginar, un débil subsistema de PA es suficiente]. Así que, en respuesta a tu pregunta

De primer orden PA es en sí suficiente para demostrar (a la mitad) el primer teorema de la incompletitud de PA.

Bono de resultado: Puesto que la PA puede demostrar $\mathsf{Con} \to \mathsf{G}_{PA}$ y no puede probar $\mathsf{G}_{PA}$, PA no puede probar $\mathsf{Con}$. Que es, por supuesto, el segundo teorema de la incompletitud.

Todo esto se explica en mi libro, Ch. 24 en la primera edición, Cap. 31 en el mucho mejor segunda edición.

(Con matices diferentes, si usted quiere saber acerca de una formales equipo de verificación de la primera teorema de la incompletitud, a continuación, mira aquí: http://r6.ca/Goedel/goedel1.html )