Teorema de completitud de Gödel

La palabra "demostrable" significa que existe una deducción formal de la fórmula.

A partir de dicha deducción, es posible verificar si cada uno de los pasos es correcto mediante un algoritmo (por ejemplo, mediante una computadora o a mano).

A su vez, la prueba de Henkin fue simplificada por Gisbert Hasenjaeger en 1953.

Para declarar formalmente, y luego demostrar, el teorema de la integridad, es necesario también definir un sistema deductivo.

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).

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.

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.