Teorema de completitud de Gödel

El teorema de Gödel sobre la completitud del cálculo de predicados es uno de los teoremas fundamentales de la lógica matemática : establece una relación inequívoca entre la verdad lógica de un enunciado y su deducibilidad en lógica de primer orden . Este teorema fue probado por primera vez por Kurt Gödel en 1929 .

Una fórmula es derivable en el cálculo de predicados de primer orden si y solo si es válida (verdadera en cualquier interpretación para cualquier sustitución ).

En otras palabras, si es una fórmula idénticamente verdadera del cálculo de predicados, entonces es demostrable en el cálculo de predicados. [una] $\Fi$ $\Fi$

Prueba

Del mismo hecho, obtenemos que el conjunto no tiene modelo . Del teorema de la existencia del modelo se sigue, que es contradictorio, es decir , el teorema del cálculo de predicados. Por la regla de inferencia , obtenemos que es demostrable. [una] $\Fi$ $\{\ neg \Phi \}$ $\{\ neg \Phi \}$ $\neg \Phi \vdash$ ${\frac {\Gamma ,\neg \Phi \vdash }{\Gamma \vdash \Phi ))$ $\Fi$

Véase también

Notas

↑ 1 2 Ershov, 1987 , pág. 139.

Literatura

Ershov Yu.L. , Palyutin E.A. Lógica matemática. — M .: Nauka, 1987. — 336 p.