Teorema de completitud de Gödel

Una fórmula de primer orden se llama lógicamente válida si es verdadera en cada estructura para el lenguaje de la fórmula (es decir, para cualquier asignación de valores a las variables de la fórmula). Para declarar formalmente, y luego demostrar, el teorema de la integridad, es necesario también definir un sistema deductivo. Un sistema deductivo se llama completo si toda fórmula lógicamente válida es la conclusión de alguna deducción formal, y el teorema de la completitud para un sistema deductivo particular es el teorema de que está completo en este sentido. Así, en cierto sentido, hay un teorema de completitud diferente para cada sistema deductivo. Algo importante junto con la integridad es la solidez, el hecho de que sólo las fórmulas lógicamente válidas son demostrables en el sistema deductivo.

Si algún sistema deductivo específico de lógica de primer orden es sólido y completo, entonces es "perfecto" (una fórmula es demostrable si y sólo si es una consecuencia semántica de los axiomas), equivalente a cualquier otro sistema deductivo con el mismo Calidad (cualquier prueba en un sistema se puede convertir en el otro).

El teorema de la integridad dice que si una fórmula es lógicamente válida entonces hay una deducción finita (una prueba formal) de la fórmula.

El teorema de Gödel de completitud dice que un sistema deductivo de cálculo de predicados de primer orden es "completo" en el sentido de que no se requieren reglas de inferencia adicionales para probar todas las fórmulas lógicamente válidas. Junto con la integridad hay que tener en cuenta la solidez, el hecho de que sólo las fórmulas lógicamente válidas son demostrables en el sistema deductivo. Junto con la solidez (cuya verificación es fácil), este teorema implica que una fórmula es lógicamente válida si y sólo si es la conclusión de una deducción formal.

La versión más simple de este teorema que es suficiente en la práctica para la mayoría de las necesidades, y tiene conexiones con el teorema de Löwenheim-Skolem, dice:

Una versión más general se puede expresar como:

Aquí, una teoría consistente se define como aquella en la que, para ninguna fórmula 'F', tanto 'F' como '¬F' pueden ser probados. Ver Consistencia, la definición sintáctica; La definición semántica sería tautológica en este contexto.

Este teorema de Henkin es la versión más directa obtenida del teorema de la completitud en su prueba más simple.

Dado el teorema de Henkin, la demostración del teorema de la completitud es como sigue: Si ${\displaystyle \Phi \models A}$ es válido, entonces${\displaystyle \Phi \cup \lnot A}$ no tiene modelos. Por la contraposición de Henkin, entonces ${\displaystyle \lnot A}$ es una fórmula inconsistente. Pero, por la definición de consistencia, si ${\displaystyle \Phi \cup \lnot A}$ es inconsistente entonces es posible construir una prueba de ${\displaystyle \Phi \vdash A}$.

En 1930 Gödel demostró la completitud de la lógica cuantificacional de primer orden. Literalmente el teorema de completitud de Gödel establece: "Para toda fórmula A de la lógica cuantificacional de primer orden, si A es lógicamente verdadera, entonces A es deducible". Dicho formalmente: "Si ╞ A, entonces ├ A". Esto quiere decir que el sistema formal de la lógica cuantificacional será completo si todas las fórmulas que representan verdades lógicas son formalmente deducibles en el sistema.

La prueba del teorema de completitud se reduce a consignar las siguientes premisas

1. A es lógicamente verdadera: A ╞ A
2. Si A es lógicamente verdadera, entonces ¬A es insatisfacible
3. Si ¬A es insatisfacible, entonces ¬A es inconsistente
4. Si ¬A es inconsistente, entonces da lugar a contradicción: ¬A ├ B y ¬A ├ ¬B
5. Si ¬A ├ B y ¬A ├ ¬B, entonces ├ A

La justificación de estas premisas es la siguiente

1. Es la hipótesis del teorema de completitud
2. Se sigue de la definición del concepto de fórmula lógicamente verdadera: su negación ha de ser insatisfacible
3. Es la contraposición del teorema de Henkin
4. Es un mero análisis de la definición de inconsistencia
5. Se basa en el teorema de deducción, que permite pasar de ¬A ├ B y ¬A ├ ¬B a ├ ¬A ^ B y ├ ¬A ^ ¬B, respectivamente, y en Modus Ponens, que permite, con ayuda de estas dos últimas fórmulas, eliminar los antecedentes en la ley de reducción al absurdo (├ (¬A ^ B) ® ((¬A ^ ¬B) ^ ¬¬A); de ├ ¬¬A se pasa a ├ a mediante una aplicación de MP a la ley de doble negación ├ ¬¬A ^ A

Aceptadas estas premisas, se les aplica reiteradamente la regla MP, empezando por (2) y (1), siguiendo con (3) y el consecuente de (2), y así sucesivamente, hasta liberar el consecuente de (5): ├ A, que es justamente la tesis del teorema de Gödel, el cual queda, por tanto, demostrado.

En los libros de lógica modernos, el teorema de completitud de Gödel es por lo general demostrado mediante la demostración de Henkin, aunque a veces también se utiliza la demostración de Herbrand, en lugar de la demostración original de Gödel.

• Gödel, K (1929). Über die Vollständigkeit des Logikkalküls. Doctoral dissertation. University Of Vienna. Esta tesis es la fuente original de la demostración del teorema de completitud.
• Gödel, K (1930). «Die Vollständigkeit der Axiome des logischen Funktionenkalküls». Monatshefte für Mathematik (en alemán) 37: 349-360. doi:10.1007/BF01696781. JFM 56.0046.04. Este artículo contiene el mismo material que la tesis doctoral en una forma abreviada. Las demostraciones son más cortas, las explicaciones más sucintas, y se ha omitido la extensa introducción.