Varias preguntas sobre el teorema de incompletitud

Question

He leído bastantes libros de matemáticas populares a lo largo de los años con descripciones del teorema de incompletitud y creo que entiendo la mayoría de los detalles generales, pero algunos todavía se me escapan. En concreto, estos tres de abajo. Estoy usando la Aritmética de Peano como lo hacen la mayoría de las popularizaciones.

Tal y como yo lo entiendo, el teorema de incompletitud funciona en parte porque uno puede interpretar las frases de PA como si hablaran de (o modelaran) los números naturales (a los que llamaré modelo A ) y esa es obviamente la interpretación que se pretende. Sin embargo, como Gödel demostró famosamente, PA también puede interpretarse como la demostración de verdades sobre cadenas de PA, que llamaré el meta-modelo M .

Finalmente, tal y como yo lo entiendo, la completitud de la Lógica de Primer Orden significa que cualquier frase que sea verdadera en cada modelo es demostrable. En otras palabras, cada modelo de los axiomas necesita estar de acuerdo con el valor de verdad de las sentencias demostrables. Sin embargo, no tienen que estar de acuerdo con las sentencias indemostrables porque esas sentencias indemostrables son formalmente independientes.

Así que aquí están mis preguntas:

1. Por lo que he leído, creo que entiendo por qué G es indemostrable y por qué debe ser verdadera cuando se interpreta con M . Lo que sigo sin entender es por qué también tiene que ser cierto cuando se interpreta sobre A ? ¿No podría darse el caso de que G sea verdadera sólo bajo el primer modelo pero no bajo el segundo?

2. Suponiendo que la pregunta anterior tenga una buena respuesta (y estoy seguro de que la tiene), ¿significa eso que, suponiendo que la AP sea consistente, no podríamos explotarla en busca de verdades aritméticas? Podríamos construir una sentencia de Gödel y simplemente mirar su interpretación bajo A, y luego construir una nueva sentencia de Gödel formalizándola de una manera diferente y eso representaría otra verdad. Estoy seguro de que hay algo fundamentalmente erróneo en esta idea, pero no sé qué.

3. En cuanto al predicado de prueba Prf(x, y), ¿qué es exactamente? ¿Es una igualdad como x=y (con muchas más constantes, estoy seguro), es una implicación como x y, o algo más?

Ten en cuenta que no soy matemático ni lógico, sólo soy un tipo al que le fascina la lógica pero que nunca aprendió los detalles técnicos. Si desea responder, he pegado un ejemplo que encontré en el libro gratuito en línea de Peter Smith Gödel sin (demasiadas) lágrimas para su comodidad al copiar y pegar:

Defn. 47 U(y) =def x¬Gdl(x, y).

Ahora diagonalizamos U, para dar

G =def U(U) = x¬Gdl(x,U). https://www.logicmatters.net/resources/pdfs/gwt/GWT2f.pdf (página 72)

Answer 1

Algunos comentarios...

se pueden interpretar las frases de $\mathsf {PA}$ como hablar de (o modelar) los números naturales (que llamaré modelo $\mathcal A$ ) y esa es obviamente la interpretación que se pretende. Sin embargo, como Gödel demostró famosamente, $\mathsf {PA}$ también puede interpretarse como una prueba de verdades sobre cadenas de $\mathsf {PA}$ que llamaré el metamodelo $\mathcal M$ .

No exactamente; el lenguaje de $\mathsf {PA}$ "habla de" números .

La técnica de Gödel de aritmética codifica expresiones (cadenas) y secuencias de expresiones en números y secuencias de números.

De esta manera, sintáctico propiedades y relaciones de $\mathsf {PA}$ se traducen en propiedades y relaciones aritméticas.

Puedes ver este puesto para un "ejercicio de codificación"; siguiendo ese esquema de codificación, el número $10$ codifica la fórmula $0=0$ .

$10$ es un número que estamos utilizando, en el contexto de la aritmética de la sintaxis, para expresar un hecho sobre la materia sintáctica.

---

Dicho esto, el incomprobable declaración $G$ [una declaración de $\mathsf {PA}$ tal que $\mathsf {PA} \nvdash G$ , siempre que $\mathsf {PA}$ es consistente ] es una afirmación que expresa un "hecho" sobre los números.

¿Por qué afirmamos que es verdad? Porque cuando se "descodifica" se afirma también una relación entre cosas sintácticas, y más precisamente se afirma que para una determinada frase $G$ de $\mathsf {PA}$ no hay ninguna secuencia de fórmulas que sea una derivación de ella a partir de los axiomas.

Este resultado se basa en la definición de la relación :

$\text {Prf}(x,y)$ .

Es una relación binaria que se lee :

"la número $x$ codifica (es el número de Gödel de) una prueba (una secuencia de fórmulas) de la fórmula codificada por (con el número de Gödel) $y$ ".

---

La definición de $\text {Prf}(x,y)$ no es intuitivo, sino que se fabrica paso a paso a partir de bloques de construcción muy sencillos, basándose en que las especificaciones sintácticas del lenguaje son mecánicas.

Comenzamos codificando los símbolos básicos (muy pocos) y luego codificamos finito secuencias de símbolos, de forma que podamos calcular mecánicamente el código correspondiente a una expresión del lenguaje y descodificar un número para recuperar la expresión correspondiente.

De este modo, podemos definir relaciones que reflejen en la aritmética las relaciones y operaciones sintácticas, como por ejemplo :

$\text{neg}(x)$ es decir, la función que asigna el código de una fórmula $A$ en el código de la fórmula $\lnot A$ y de forma similar para $\text {to}(x, y)$ es decir, la función que mapea los números de Gödel de un par $A$ y $B$ de fórmulas al número de Gödel de la fórmula $A \to B$ y así sucesivamente.

Luego pasamos a codificar los axiomas y las reglas de inferencia y, finalmente, las secuencias de fórmulas (es decir, la derivación en el sistema, es decir, la prueba).

De esta manera llegamos a la $\text {Prf}(x,y)$ y su "gemelo", el predicado de comprobabilidad : $\text {Prov}(x)$ , definida simplemente como :

$∃x \ \text {Prf}(x, y)$ .

El anterior dice: "el número $x$ es el número de Gödel de una prueba de la fórmula con el número de Gödel $y$ ".

Por lo tanto, el nuevo es : "hay una prueba de la fórmula con el número de Gödel $y$ ", es decir, :

"la fórmula con el número de Gödel $y$ es comprobable (en el sistema)".

A partir de ella llegamos a la "codificación" de incomprobabilidad : $\lnot ∃x \ \text {Prf}(x, y)$ o, de forma equivalente, : $∀x \lnot \text {Prf}(x, y)$ .