Teorema de completitud de Gödel

El teorema de completitud de Gödel es un importante teorema de la lógica matemática, que fue demostrado por primera vez por Kurt Gödel en 1929 y que en su forma más conocida establece lo siguiente:

En una lógica de primer orden, toda fórmula que es válida en un sentido lógico es demostrable. Kurt Gödel

La palabra "demostrable" significa que existe una deducción formal de la fórmula. La deducción consiste en una lista finita de pasos en los que cada paso o bien invoca a un axioma o es obtenido a partir de pasos previos mediante una básica regla de inferencia. 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).

Una fórmula es lógicamente válida si es verdadera en todo modelo para el lenguaje utilizado en la fórmula. Para expresar de manera formal el teorema de completitud de Gödel, se debe definir el significado de la palabra modelo en este contexto. Esta es una definición básica en la teoría de modelos.

Demostraciones

Para una explicación de la demostración original de Gödel del teorema, ver Demostración original del teorema de completitud de Gödel.

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.

Véase también

• Teoremas de la incompletitud de Gödel

Bibliografía

• Kurt Gödel, "Über die Vollständigkeit des Logikkalküls", tesis doctoral, University Of Vienna, 1929. Esta tesis es la fuente original de la demostración del teorema de completitud.
• Kurt Gödel, "Die Vollständigkeit der Axiome des logischen Funktionen-kalküls", Monatshefte für Mathematik und Physik 37 (1930), 349-360. 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 suscintas, y se ha omitido la extensa introducción.

Enlaces externos

• Vilnis Detlovs and Karlis Podnieks, "Introduction to mathematical logic", http://www.ltn.lv/~podnieks/