Teorema de completitud de Gödel

La fórmulax. R()x,x) →x∃Sí.. R()x,Sí.)) sostiene en todas las estructuras (sólo los 8 más simples se muestran a la izquierda). Por el resultado de la integridad de Gödel, debe tener una prueba de deducción natural (derecho mostrado).

El teorema de completitud de Gödel es un teorema fundamental en lógica matemática que establece una correspondencia entre la verdad semántica y la demostrabilidad sintáctica en lógica de primer orden.

El teorema de completitud se aplica a cualquier teoría de primer orden: si T es una teoría de este tipo y φ es una oración (en el mismo idioma) y cada modelo de T es un modelo de φ, entonces hay una prueba (de primer orden) de φ usando las declaraciones de T como axiomas. A veces se dice esto como "cualquier cosa universalmente cierta es comprobable". Esto no contradice el teorema de incompletitud de Gödel, que muestra que alguna fórmula φ_u es indemostrable aunque cierta en los números naturales, que son un modelo particular de una teoría de primer orden que los describe: φ _u es simplemente falso en algún otro modelo de la teoría de primer orden que se está considerando (como un modelo no estándar de aritmética para la aritmética de Peano).

Establece un vínculo estrecho entre la teoría de modelos que se ocupa de lo que es cierto en diferentes modelos y la teoría de la prueba que estudia lo que se puede probar formalmente en sistemas formales particulares.

Probado por primera vez por Kurt Gödel en 1929. Luego se simplificó cuando Leon Henkin observó en su Ph.D. tesis de que la parte difícil de la demostración puede presentarse como el Teorema de la Existencia del Modelo (publicado en 1949). La demostración de Henkin fue simplificada por Gisbert Hasenjaeger en 1953.

Preliminares

Existen numerosos sistemas deductivos para la lógica de primer orden, incluidos los sistemas de deducción natural y los sistemas de estilo Hilbert. Común a todos los sistemas deductivos es la noción de deducción formal. Esta es una secuencia (o, en algunos casos, un árbol finito) de fórmulas con una conclusión especialmente designada. La definición de una deducción es tal que es finita y que es posible verificar algorítmicamente (por una computadora, por ejemplo, oa mano) que una determinada secuencia (o árbol) de fórmulas es de hecho una deducció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 enunciar formalmente y luego probar el teorema de completitud, es necesario definir también un sistema deductivo. Un sistema deductivo se llama completo si cada fórmula lógicamente válida es la conclusión de alguna deducción formal, y el teorema de completitud para un sistema deductivo particular es el teorema de que es completo en este sentido. Así, en cierto sentido, existe un teorema de completitud diferente para cada sistema deductivo. Lo opuesto a la completitud es la solidez, el hecho de que solo 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 lógicamente válida), por lo tanto equivalente a cualquier otro sistema deductivo con la misma calidad (cualquier prueba en un sistema puede convertirse en otro).

Declaración

Primero fijamos un sistema deductivo de cálculo de predicados de primer orden, eligiendo cualquiera de los sistemas equivalentes conocidos. La prueba original de Gödel asumió el sistema de prueba de Hilbert-Ackermann.

Fórmula original de Gödel

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

Así, el sistema deductivo es "completo" en el sentido de que no se requieren reglas de inferencia adicionales para probar todas las fórmulas lógicamente válidas. Lo opuesto a la completitud es la solidez, el hecho de que solo 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.

Forma más general

El teorema se puede expresar más generalmente en términos de consecuencia lógica. Decimos que una frase s es un consecuencia sintáctica de una teoría T, denotado T⊢ ⊢ s{displaystyle Tvdash s, si s es prable de T en nuestro sistema deductivo. Decimos eso. s es un consecuencia semántica de T, denotado T⊨ ⊨ s{displaystyle Tmodels s, si s sostiene en cada modelo de T. El teorema de integridad entonces dice que para cualquier teoría de primer orden T con un lenguaje bien ordenado, y cualquier sentencia s en el idioma de T,

si T⊨ ⊨ s{displaystyle Tmodels s, entonces T⊢ ⊢ s{displaystyle Tvdash s.

Puesto que el converso (suena) también sostiene, sigue que T⊨ ⊨ s{displaystyle Tmodels s si T⊢ ⊢ s{displaystyle Tvdash s, y por lo tanto esa consecuencia sintáctica y semántica son equivalentes para la lógica de primer orden.

Este teorema más general se usa implícitamente, por ejemplo, cuando se demuestra que una oración es demostrable a partir de los axiomas de la teoría de grupos al considerar un grupo arbitrario y mostrar que la oración se satisface con ese grupo.

La formulación original de Gödel se deduce tomando el caso particular de una teoría sin ningún axioma.

Teorema de existencia del modelo

El teorema de completitud también se puede entender en términos de consistencia, como consecuencia del teorema de existencia del modelo de Henkin. Decimos que una teoría T es sintácticamente consistente si no hay ninguna oración s tal que tanto s como su negación ¬s son demostrables a partir de T en nuestro sistema deductivo. El teorema de existencia del modelo dice que para cualquier teoría de primer orden T con un lenguaje bien ordenable,

si T{displaystyle T} es sintácticamente consistente, entonces T{displaystyle T} tiene un modelo.

Otra versión, con conexiones con el teorema de Löwenheim-Skolem, dice:

Dado el teorema de Henkin, el teorema de integridad puede ser probado como sigue: Si T⊨ ⊨ s{displaystyle Tmodels s, entonces T∪ ∪ ¬ ¬ s{displaystyle Tcup lnot s no tiene modelos. Por el contrario del teorema de Henkin, entonces T∪ ∪ ¬ ¬ s{displaystyle Tcup lnot s es sintácticamente inconsistente. Así que una contradicción⊥ ⊥ {displaystyle bot }) es provable de T∪ ∪ ¬ ¬ s{displaystyle Tcup lnot s en el sistema deductivo. Por lo tanto ()T∪ ∪ ¬ ¬ s)⊢ ⊢ ⊥ ⊥ {displaystyle (Tcup lnot s)vdash bot }, y luego por las propiedades del sistema deductivo, T⊢ ⊢ s{displaystyle Tvdash s.

Como un teorema de la aritmética

El teorema de existencia del modelo y su prueba se pueden formalizar en el marco de la aritmética de Peano. Precisamente, podemos definir sistemáticamente un modelo de cualquier teoría de primer orden efectiva consistente T en la aritmética de Peano interpretando cada símbolo de T mediante una fórmula aritmética cuyas variables libres son los argumentos del símbolo. (En muchos casos, necesitaremos asumir, como hipótesis de la construcción, que T es consistente, ya que la aritmética de Peano puede no probar ese hecho). Sin embargo, la definición expresada por esta fórmula no es recursivo (pero es, en general, Δ2).

Consecuencias

Una consecuencia importante del teorema de completitud es que es posible enumerar recursivamente las consecuencias semánticas de cualquier teoría efectiva de primer orden, enumerando todas las posibles deducciones formales de los axiomas de la teoría, y usar esto para producir una enumeración de sus conclusiones.

Esto contrasta con el significado directo de la noción de consecuencia semántica, que cuantifica todas las estructuras en un lenguaje particular, que claramente no es una definición recursiva.

Además, hace del concepto de "probabilidad", y por tanto de "teorema", un concepto claro que sólo depende del sistema elegido de axiomas de la teoría, y no de la elección de un sistema de demostración.

Relación con los teoremas de incompletitud

Los teoremas incompletos de Gödel muestran que existen limitaciones inherentes a lo que se puede probar dentro de cualquier teoría de primer orden dada en las matemáticas. La "incompleta" en su nombre se refiere a otro significado de completo (ver teoría modelo – Usando los teoremas de compactidad y integridad): Una teoría T{displaystyle T} es completo (o decidable) si cada frase S{displaystyle S. en el idioma de T{displaystyle T} es provable (T⊢ ⊢ S{displaystyle Tvdash S}) o desprovable (T⊢ ⊢ ¬ ¬ S{displaystyle Tvdash neg S}).

El primer teorema de incompleta declara que cualquier T{displaystyle T} que es consistente, eficaz y contiene aritmética Robinson ("Q") debe ser incompleta en este sentido, construyendo explícitamente una frase ST{displaystyle S_{T} que es demostrable ni provable ni desprovable dentro T{displaystyle T}. El segundo teorema de incompleta extiende este resultado mostrando que ST{displaystyle S_{T} puede ser elegido para que expresa la consistencia de T{displaystyle T} en sí mismo.

Desde ST{displaystyle S_{T} no se puede probar T{displaystyle T}, el teorema de la integridad implica la existencia de un modelo T{displaystyle T} en que ST{displaystyle S_{T} es falso. De hecho, ST{displaystyle S_{T} es una frase LOG1, es decir, afirma que alguna propiedad finita es verdadera de todos los números naturales; por lo que si es falsa, entonces algún número natural es un contraejemplo. Si este contraejemplo existiera dentro de los números naturales estándar, su existencia refutaría ST{displaystyle S_{T} dentro T{displaystyle T}; pero el teorema de la incompleta mostró que esto es imposible, por lo que el contraexamplo no debe ser un número estándar, y por lo tanto cualquier modelo de T{displaystyle T} en que ST{displaystyle S_{T} es falso debe incluir números no estándar.

De hecho, el modelo de cualquier teoría que contenga Q obtenido mediante la construcción sistemática del teorema de existencia del modelo aritmético, es siempre no estándar con un predicado de demostrabilidad no equivalente y una forma no equivalente de interpretar su propia construcción, por lo que esta construcción no es recursiva (como las definiciones recursivas serían inequívocas).

También, si T{displaystyle T} es al menos ligeramente más fuerte que Q (por ejemplo, si incluye inducción para fórmulas existenciales ligadas), entonces el teorema de Tennenbaum muestra que no tiene modelos recursivos no estándar.

Relación con el teorema de compacidad

El teorema de completitud y el teorema de compacidad son dos pilares de la lógica de primer orden. Si bien ninguno de estos teoremas se puede probar de manera completamente efectiva, cada uno se puede obtener de manera efectiva a partir del otro.

El teorema de compacidad dice que si una fórmula φ es una consecuencia lógica de un conjunto (posiblemente infinito) de fórmulas Γ, entonces es una consecuencia lógica de un subconjunto finito de Γ. Esta es una consecuencia inmediata del teorema de completitud, porque solo se puede mencionar un número finito de axiomas de Γ en una deducción formal de φ, y la solidez del sistema deductivo implica que φ es una consecuencia lógica de este conjunto finito. Esta demostración del teorema de la compacidad se debe originalmente a Gödel.

Por el contrario, para muchos sistemas deductivos, es posible probar el teorema de completitud como una consecuencia efectiva del teorema de compacidad.

La ineficacia del teorema de completitud se puede medir siguiendo las líneas de las matemáticas inversas. Cuando se consideran sobre un lenguaje contable, los teoremas de completitud y compacidad son equivalentes entre sí y equivalentes a una forma débil de elección conocida como lema débil de König, con la equivalencia demostrable en RCA₀ (una variante de segundo orden de la aritmética de Peano restringida a la inducción sobre fórmulas Σ⁰₁). El lema débil de König es demostrable en ZF, el sistema de teoría de conjuntos de Zermelo-Fraenkel sin axioma de elección, y por lo tanto los teoremas de completitud y compacidad para lenguajes contables son demostrables en ZF. Sin embargo, la situación es diferente cuando el lenguaje es de gran cardinalidad arbitraria desde entonces, aunque los teoremas de completitud y compacidad siguen siendo probablemente equivalentes entre sí en ZF, también son probablemente equivalentes a una forma débil del axioma de elección conocido como el lema del ultrafiltro.. En particular, ninguna teoría que extienda ZF puede probar los teoremas de completitud o compacidad sobre lenguajes arbitrarios (posiblemente incontables) sin probar también el lema del ultrafiltro en un conjunto de la misma cardinalidad.

Integridad en otras lógicas

El teorema de completitud es una propiedad central de la lógica de primer orden que no se cumple para todas las lógicas. La lógica de segundo orden, por ejemplo, no tiene un teorema de completitud para su semántica estándar (pero tiene la propiedad de completitud para la semántica de Henkin), y el conjunto de fórmulas lógicamente válidas en la lógica de segundo orden no es recursivamente enumerable. Lo mismo es cierto para todas las lógicas de orden superior. Es posible producir sistemas deductivos sólidos para lógicas de orden superior, pero ningún sistema de este tipo puede ser completo.

El teorema de Lindström establece que la lógica de primer orden es la lógica más fuerte (sujeta a ciertas restricciones) que satisface tanto la compacidad como la integridad.

Se puede probar un teorema de completitud para la lógica modal o la lógica intuicionista con respecto a la semántica de Kripke.

Pruebas

La prueba original del teorema de Gödel procedió reduciendo el problema a un caso especial para fórmulas en una forma sintáctica determinada, y luego manejando esta forma con un argumento ad hoc.

En los textos de lógica modernos, el teorema de completitud de Gödel generalmente se demuestra con la prueba de Henkin, en lugar de con la prueba original de Gödel. La prueba de Henkin construye directamente un modelo de término para cualquier teoría de primer orden consistente. James Margetson (2004) desarrolló una prueba formal computarizada utilizando el demostrador del teorema de Isabelle. También se conocen otras pruebas.