4.1: Introducción a la incompletitud
- Page ID
- 113503
Ahora, esperamos que haya estado prestando atención lo suficientemente de cerca como para que le moleste el título de este capítulo. El capítulo anterior fue sobre la integridad, y probamos el Teorema de la Integtud. ¡Ahora parece que estamos lanzando una investigación de incompletitud! Este punto es bastante confuso, así que intentemos comenzar con la mayor claridad posible.
En el Capítulo 3 probamos la integridad de nuestro sistema axiomático. Hemos demostrado que el sistema deductivo descrito en el Capítulo 2 es sólido y completo. ¿Qué significa esto? Para la colección de axiomas lógicos y reglas de inferencia que hemos establecido, cualquier fórmula\(\phi\) que pueda deducirse de un conjunto de axiomas no lógicos\(\Sigma\) será verdadera en todos los modelos de\(\Sigma\) bajo cualquier función de asignación variable (eso es solidez), y además cualquier fórmula\(\phi\) eso es cierto en todos los modelos de\(\Sigma\) bajo cada función de asignación será deducible de\(\Sigma\) (eso es integridad). Por lo tanto, nuestro sistema deductivo es lo más agradable que pueda ser. La versión aproximada de los Teoremas de Integtud y Solidez es: Podemos probarlo si y sólo si es cierto en todas partes.
Ahora vamos a cambiar nuestro enfoque. En lugar de discutir las maravillosas cualidades de nuestro sistema deductivo, nos concentraremos en un lenguaje particular\(\mathcal{L}_{NT}\), y pensaremos en una estructura particular\(\mathfrak{N}\), los números naturales.
¿No sería la vida simplemente genial si supiéramos que podríamos probar cada afirmación verdadera sobre los números naturales? Por supuesto, las afirmaciones que podamos probar dependen de nuestra elección de axiomas no lógicos\(\Sigma\), así que empecemos de nuevo este párrafo.
¿No sería la vida simplemente genial si pudiéramos encontrar un conjunto de axiomas no lógicos que pudieran probar cada afirmación verdadera sobre los números naturales? Nos encantaría tener un conjunto de axiomas\(\Sigma\) tales que\(\mathfrak{N} \models \Sigma\) (así nuestros axiomas son verdaderas declaraciones sobre los números naturales) y\(\Sigma\) sea lo suficientemente rico como para que por cada oración\(\sigma\), si\(\mathfrak{N} \models \sigma\), entonces\(\Sigma \vdash \sigma\). Ya que\(\Sigma \vdash \sigma\) tiene un modelo, sabemos que\(\Sigma\) es consistente, así que por solidez nuestro anhelado\(\Sigma\) probará exactamente aquellas frases que son verdaderas en\(\mathfrak{N}\). El conjunto de oraciones de\(\mathcal{L}_{NT}\) que son verdaderas en\(\mathfrak{N}\) se llama la Teoría de\(\mathfrak{N}\), o\(Th \left( \mathfrak{N} \right)\).
Ya que sabemos que una oración es verdadera en\(\mathfrak{N}\) o falsa en\(\mathfrak{N}\), este conjunto de axiomas\(\Sigma\) está completo -completo en el sentido de que dada cualquier oración\(\sigma\),\(\Sigma\) proporcionará ya sea una deducción\(\sigma\) o una deducción de\(\neg \sigma\).
Un conjunto de axiomas no lógicos\(\Sigma\) en un lenguaje\(\mathcal{L}\) se llama completo si por cada\(\mathcal{L}\) -oración\(\sigma\), ya sea\(\Sigma \vdash \sigma\) o\(\Sigma \vdash \neg \sigma\).
Chaf: Para reiterar, en el Capítulo 3 demostramos que nuestro sistema deductivo está completo. Esto significa que para un dado\(\Sigma\), el sistema deductivo probará exactamente aquellas fórmulas que son consecuencias lógicas de\(\Sigma\). Cuando decimos que un conjunto de axiomas está completo, estamos diciendo que los axiomas son lo suficientemente fuertes como para proporcionar ya sea una prueba o una refutación de cualquier sentencia. Esto es más difícil.
Nuestro objetivo es encontrar un conjunto completo y consistente de\(\mathcal{L}_{NT}\) -axiomas\(\Sigma\) tales que\(\mathfrak{N} \models \Sigma\). Entonces este conjunto\(\Sigma\) sería lo suficientemente fuerte como para probar cada\(\mathcal{L}_{NT}\) frase que es cierta en la estructura estándar\(\mathfrak{N}\). Se dice que tal conjunto de axiomas axiomatiza\(Th \left( \mathfrak{N} \right)\).
Un conjunto de axiomas\(\Sigma\) es una axiomatización de\(Th \left( \mathfrak{N} \right)\) si por cada oración\(\sigma \in Th \left( \mathfrak{N} \right)\),\(\Sigma \vdash \sigma\).
En realidad, como se dijo, es bastante fácil encontrar una axiomatización de\(Th \left( \mathfrak{N} \right)\): Solo deja que el conjunto de axiomas sea\(Th \left( \mathfrak{N} \right)\) él mismo. Este conjunto claramente se axiomatiza a sí mismo, ¡así que estamos terminados! Fuera vamos a tomar una copa. Por supuesto, nuestra respuesta a la búsqueda tiene el problema de que no tenemos una manera fácil de decir exactamente qué fórmulas son elementos del conjunto de axiomas. Si tomamos una oración aleatoria\(\mathcal{L}_{NT}\) y te preguntamos si esta oración era cierta en la estructura estándar, dudamos que puedas decirnos. La verdad de las oraciones no aleatorias también es difícil de entender -consideremos la conjetura del primo gemelo, que hay infinitamente muchos pares de enteros positivos\(k\) y\(k + 2\) tales que ambos\(k\) y\(k + 2\) son primos. La gente viene pensando en eso desde hace más de 2000 años y no sabemos si es cierto o no, aunque parece que actualmente (verano 2014) nos estamos acercando. Pero al menos a partir de ahora, realmente no tenemos idea de si la conjetura del primo gemelo está en\(Th \left( \mathfrak{N} \right)\) o no. Por lo que parece que\(Th \left( \mathfrak{N} \right)\) es insatisfactorio como conjunto de axiomas no lógicos.
Entonces, para refinar un poco nuestra pregunta, lo que nos gustaría es un conjunto de axiomas no lógicos\(\Sigma\) que sea lo suficientemente simple como para que podamos reconocer si una fórmula dada es o no un axioma (por lo que el conjunto de axiomas debe ser decidible) y lo suficientemente fuerte como para probar cada fórmula en\(Th \left( \mathfrak{N} \right)\). Entonces buscamos un conjunto completo, consistente, decidible de axiomas para\(\mathfrak{N}\). Desafortunadamente, nuestra búsqueda está condenada al fracaso, y ese hecho es el contenido del Teorema del Primer Incompletitud de Gödel, que probaremos en el Capítulo 6 y luego nuevamente en el Capítulo 7. (Sabes que un teorema es importante si vamos a demostrarlo más de una vez...)
¿Qué, precisamente, es lo que vamos a hacer? Dado cualquier conjunto completo, consistente y decidible de axiomas para\(\mathfrak{N}\), vamos a encontrar una oración\(\sigma\) que sea una verdadera declaración sobre los números naturales (so\(\sigma \in Th \left( \mathfrak{N} \right)\)) pero que no\(\sigma\) será demostrable a partir de la colección de axiomas. ¿Y qué tan complicada debe\(\sigma\) ser esta frase? Resulta que no tiene por qué ser muy complicado en absoluto. El siguiente subapartado aportará cierta estructura a la colección de\(\mathcal{L}_{NT}\) -fórmulas y nos dará algún lenguaje con el que hablar de la complejidad de las fórmulas.