Teorema de completitud de Gödel

Question

Hace poco me di cuenta de que no entendía bien el teorema de completitud de Godel, y cómo interactúa con los teoremas de incompletitud.

Lo que entiendo ahora (¡y verás que mi entendimiento no es consistente!)

1. Incompletitud significa que, mientras tenga algún tipo de potencia aritmética (digamos la multiplicación) en mis axiomas, mi teoría es incompleta : hay fórmulas (incluso de FOL) que no se pueden demostrar ni refutar.
2. Completitud significa que para cualquier fórmula de lógica de primer orden (FOL), si esta fórmula es verdadera en todos los modelos de mi teoría, hay una prueba de esa fórmula en mi teoría.

Así que tomo una teoría (con aritmética potente) en la que los enteros son iguales en todos los modelos de la teoría (¿axioma del infinito?), y miro las fórmulas de FOL sobre esos enteros. Siento que hay una contradicción entre 1. y 2., porque mis fórmulas "viven" sólo en un modelo de $\mathbb N$ pero hay algunos sin pruebas.

Como me siento seguro con el teorema de incompletitud, creo que no entiendo el teorema de completitud.

He encontrado esa pregunta pero no entiendo la respuesta que dice que la teoría no es completa pero la lógica utilizada en el lenguaje sí. ¿Puede alguien explicarlo?

Muchas gracias.

Answer 1

Lo que has descubierto ahí es una prueba (por contradicción) del hecho de que hay no teoría de primer orden recursivamente axiomatizada consistente "donde los enteros son los mismos en cada modelo de la teoría".

Tal teoría no puede existir porque, gracias al teorema de incompletitud, podemos añadir a la teoría la sentencia de Gödel o su negación sin obtener una teoría inconsistente. Como las dos teorías extendidas diferentes son ambas consistentes y FOL es completa, ambas tienen modelos. Y estos modelos deben ser también modelos de la teoría original (acabamos de añadiendo un axioma en cada uno), pero deben tener diferentes números enteros porque si tuvieran los mismos enteros, estarían de acuerdo sobre si la sentencia de Gödel es verdadera o no.

---

Para conseguir una teoría en la que los enteros sean siempre los mismos, hay que pasar a la lógica de segundo orden. Por ejemplo, los axiomas de Peano de segundo orden (donde en lugar de una infinidad de axiomas de inducción para diferentes fórmulas de inducción se tiene uno solo que cuantifica sobre todos los predicados) garantizan que, cuando se usa la semántica estándar de la lógica de segundo orden.

Por otro lado, bajo la semántica estándar la lógica de segundo orden es no completa .