Teorema de Completitud de Gödel

Introducción

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

La formulación original de Gödel

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.

Teorema de la existencia del modelo

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:

Cada teoría consistente y contable de primer orden tiene un modelo finito o contable.
Una versión más general se puede expresar como:

Toda teoría coherente de primer orden con un lenguaje bien ordenado tiene un modelo.
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.