La prueba del teorema de completitud de Gödel dada por Kurt Gödel en su tesis doctoral de 1929 (y una versión más corta de la prueba, publicada como un artículo en 1930, titulada "La completitud de los axiomas del cálculo funcional de la lógica" (en alemán) ) no es fácil de leer hoy; utiliza conceptos y formalismos que ya no se utilizan y una terminología que a menudo es oscura. La versión que se da a continuación intenta representar fielmente todos los pasos de la prueba y todas las ideas importantes, mientras que reafirma la prueba en el lenguaje moderno de la lógica matemática . Este esquema no debe considerarse una prueba rigurosa del teorema.
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/0/03/1925_kurt_g%C3%B6del_%28cropped%29.png/200px-1925_kurt_g%C3%B6del_%28cropped%29.png)
Supuestos
Trabajamos con cálculo de predicados de primer orden . Nuestros lenguajes permiten símbolos de constante, función y relación. Las estructuras consisten en dominios (no vacíos) e interpretaciones de los símbolos relevantes como miembros constantes, funciones o relaciones sobre ese dominio.
Asumimos la lógica clásica (a diferencia de la lógica intuicionista, por ejemplo).
Arreglamos alguna axiomatización (es decir, un sistema de prueba manejable por máquina y basado en sintaxis) del cálculo de predicados: axiomas lógicos y reglas de inferencia. Cualquiera de las varias axiomatizaciones equivalentes conocidas servirá. La prueba original de Gödel asumió el sistema de prueba de Hilbert-Ackermann.
Suponemos sin pruebas todos los resultados básicos bien conocidos sobre nuestro formalismo que necesitamos, como el teorema de la forma normal o el teorema de solidez .
Axiomatizamos el cálculo de predicados sin igualdad (a veces llamado confusamente sin identidad ), es decir, no hay axiomas especiales que expresen las propiedades de la igualdad (del objeto) como un símbolo de relación especial. Una vez probada la forma básica del teorema, será fácil extenderla al caso del cálculo de predicados con igualdad .
Declaración del teorema y su demostración
A continuación, enunciamos dos formas equivalentes del teorema y mostramos su equivalencia.
Posteriormente probamos el teorema. Esto se hace en los siguientes pasos:
- Reducir el teorema a frases (fórmulas sin variables libres) en forma prenex , es decir, con todos los cuantificadores ( ∀ y ∃ ) al principio. Además, lo reducimos a fórmulas cuyo primer cuantificador es ∀ . Esto es posible porque para cada oración, hay una equivalente en forma de prenex cuyo primer cuantificador es ∀ .
- Reducir el teorema a oraciones de la forma ∀ x 1 ∀ x 2 ... ∀ x k ∃ y 1 ∃ y 2 ... ∃ y m φ ( x 1 ... x k , y 1 ... y m ) . Si bien no podemos hacer esto simplemente reordenando los cuantificadores, mostramos que todavía es suficiente para probar el teorema para oraciones de esa forma.
- Finalmente probamos el teorema para oraciones de esa forma.
- Esto se hace observando primero que una oración como B = ∀ x 1 ∀ x 2 ... ∀ x k ∃ y 1 ∃ y 2 ... ∃ y m φ ( x 1 ... x k , y 1 . .. y m ) es refutable (su negación es siempre verdadera) o satisfactoria, es decir, hay algún modelo en el que se sostiene (incluso podría ser siempre cierto, es decir, una tautología); este modelo simplemente asigna valores de verdad a las subproposiciones a partir de las cuales se construye B. La razón de esto es la integridad de la lógica proposicional , en la que los cuantificadores existenciales no juegan ningún papel.
- Extendemos este resultado a oraciones cada vez más complejas y largas, D n (n = 1,2 ...), construidas a partir de B, de modo que cualquiera de ellas es refutable y, por lo tanto, también lo es φ, o todas son no refutable y por lo tanto cada uno se sostiene en algún modelo.
- Finalmente usamos los modelos en los que se cumple D n (en caso de que no todos sean refutables) para construir un modelo en el que se cumple.
Teorema 1. Toda fórmula válida (verdadera en todas las estructuras) es demostrable.
Ésta es la forma más básica del teorema de completitud. Lo reafirmamos de inmediato en una forma más conveniente para nuestros propósitos: cuando decimos "todas las estructuras", es importante especificar que las estructuras involucradas son interpretaciones clásicas (Tarskianas) I, donde I = (U es un conjunto de objetos no vacío (posiblemente infinito), mientras que F es un conjunto de funciones de expresiones del simbolismo interpretado en U). [Por el contrario, las llamadas "lógicas libres" se refieren posiblemente a conjuntos vacíos para U. Para obtener más información sobre las lógicas libres, consulte el trabajo de Karel Lambert.]
Teorema 2. Toda fórmula φ es refutable o satisfactoria en alguna estructura.
"φ es refutable" significa, por definición, "¬φ es demostrable".
Equivalencia de ambos teoremas
Si el teorema 1 se cumple, y φ no es satisfactorio en ninguna estructura, entonces ¬φ es válido en todas las estructuras y, por lo tanto, se puede demostrar, por lo que φ es refutable y el teorema 2 se cumple. Si, por otro lado, el teorema 2 se cumple y φ es válido en todas las estructuras, entonces ¬φ no es satisfactorio en ninguna estructura y, por tanto, refutable; entonces ¬¬φ es demostrable y luego φ, por lo que el Teorema 1 es válido.
Prueba del teorema 2: primer paso
Nos acercamos a la demostración del teorema 2 restringiendo sucesivamente la clase de todas las fórmulas φ para las que necesitamos demostrar que "φ es refutable o satisfactoria". Al principio tenemos que demostrar esto para todas las fórmulas posibles φ en nuestro idioma. Sin embargo, suponga que para cada fórmula φ hay alguna fórmula ψ tomada de una clase más restringida de fórmulas C , tal que "ψ es refutable o satisfactorio" → "φ es refutable o satisfactorio". Entonces, una vez que se demuestra esta afirmación (expresado en la frase anterior), será suficiente para demostrar "φ es o refutables o satisfiable" sólo para φ la pertenencia a la clase C . Si φ es demostrablemente equivalente a ψ ( es decir , (φ≡ψ) es demostrable), entonces es de hecho el caso de que "ψ es refutable o satisfactoria" → "φ es refutable o satisfactoria" (el teorema de solidez es necesario para mostrar esto).
Existen técnicas estándar para reescribir una fórmula arbitraria en una que no utilice símbolos de función o constantes, a costa de introducir cuantificadores adicionales; por tanto, asumiremos que todas las fórmulas están libres de tales símbolos. El artículo de Gödel utiliza una versión del cálculo de predicados de primer orden que, para empezar, no tiene funciones ni símbolos constantes.
A continuación, consideramos una fórmula genérica φ (que ya no usa símbolos de función o constantes) y aplicamos el teorema de la forma prenex para encontrar una fórmula ψ en forma normal tal que φ≡ψ (ψ en forma normal significa que todos los cuantificadores en ψ, si hay alguno, se encuentran al principio de ψ). De ello se deduce ahora que solo necesitamos demostrar el teorema 2 para las fórmulas form en forma normal.
A continuación, eliminamos todas las variables libres de φ cuantificándolas existencialmente: si, digamos, x 1 ... x n son libres en φ, formamos. Si ψ es satisfactoria en una estructura M, entonces ciertamente también lo es φ y si ψ es refutable, entonceses demostrable, y luego ¬φ, por lo tanto es refutable. Vemos que podemos restringir φ para que sea una oración , es decir, una fórmula sin variables libres.
Finalmente, nos gustaría, por razones de conveniencia técnica, que el prefijo de φ (es decir, la cadena de cuantificadores al principio de φ, que está en forma normal) comience con un cuantificador universal y termine con un cuantificador existencial. Para lograr esto para un φ genérico (sujeto a restricciones que ya hemos probado), tomamos algún símbolo de relación de un lugar F sin usar en φ, y dos nuevas variables y y z .. Si φ = (P) Φ , donde (P ) representa el prefijo de φ y Φ para la matriz (la parte restante, libre de cuantificador de φ) que formamos. Desde es claramente demostrable, es fácil ver que es demostrable.
Reducir el teorema a fórmulas de grado 1
Nuestra fórmula genérica φ ahora es una oración, en forma normal, y su prefijo comienza con un cuantificador universal y termina con un cuantificador existencial. Llamemos R a la clase de todas estas fórmulas . Nos enfrentamos a probar que todas las fórmulas de R son refutables o satisfactorias. Dada nuestra fórmula φ, agrupamos cadenas de cuantificadores de un tipo en bloques:
Definimos el grado de ser el número de bloques cuantificadores universales, separados por bloques cuantificadores existenciales como se muestra arriba, en el prefijo de . El siguiente lema, que Gödel adaptó de la demostración de Skolem del teorema de Löwenheim-Skolem , nos permite reducir drásticamente la complejidad de la fórmula genérica necesitamos demostrar el teorema para:
Lema . Sea k > = 1. Si cada fórmula en R de grado k es refutable o satisfactoria, entonces también lo es toda fórmula en R de grado k + 1 .
- Comentario : Tome una fórmula φ de grado k + 1 de la forma , dónde es el resto de (es por tanto de grado k-1 ). φ establece que para cada x hay un ay tal que ... (algo). Hubiera sido bueno tener un predicado Q 'de modo que para cada x, Q' (x, y) sería verdadero si y solo si y es el requerido para hacer (algo) verdadero. Entonces podríamos haber escrito una fórmula de grado k, que es equivalente a φ, es decir . Esta fórmula es de hecho equivalente a φ porque establece que para cada x, si hay ay que satisface Q '(x, y), entonces (algo) se cumple, y además, sabemos que existe tal ay, porque para cada x ', hay ay' que satisface Q '(x', y '). Por lo tanto, φ se sigue de esta fórmula. También es fácil demostrar que si la fórmula es falsa, entonces también lo es φ. Desafortunadamente , en general no existe tal predicado Q '. Sin embargo, esta idea puede entenderse como base para la siguiente prueba del Lema.
Prueba. Sea φ una fórmula de grado k + 1 ; entonces podemos escribirlo como
donde (P) es el resto del prefijo de(es por tanto de grado k-1 ) y es la matriz libre de cuantificador de . x , y , u y v denotan aquí tuplas de variables en lugar de variables individuales; p.ej realmente representa dónde son algunas variables distintas.
Deje ahora x ' e Y' sea tuplas de variables previamente no utilizadas de la misma longitud que x e y , respectivamente, y dejar que Q sea un símbolo de relación no utilizada anteriormente que tiene tantos argumentos como la suma de las longitudes de X y Y ; consideramos la fórmula
Claramente, es demostrable.
Ahora, desde la cadena de cuantificadores no contiene variables de x o y , la siguiente equivalencia es fácilmente demostrable con la ayuda de cualquier formalismo que estemos usando:
Y como estas dos fórmulas son equivalentes, si reemplazamos la primera con la segunda dentro de Φ, obtenemos la fórmula Φ 'tal que Φ≡Φ':
Ahora Φ 'tiene la forma , donde (S) y (S ') son algunas cadenas de cuantificadores, ρ y ρ' están libres de cuantificadores y, además , ninguna variable de (S) ocurre en ρ 'y ninguna variable de (S') ocurre en ρ. En tales condiciones, cada fórmula de la forma, donde (T) es una cadena de cuantificadores que contiene todos los cuantificadores en (S) y (S ') intercalados entre sí de cualquier manera, pero manteniendo el orden relativo dentro de (S) y (S'), será equivalente al original fórmula Φ '(este es otro resultado básico en el cálculo de predicados de primer orden en el que confiamos). A saber, formamos Ψ de la siguiente manera:
y tenemos .
Ahora es una fórmula de grado k y, por lo tanto, por suposición, es refutable o satisfactoria. Sies satisfactoria en una estructura M , entonces, considerando, vemos eso es satisfactorio también. Si es refutable, entonces también lo es , que es equivalente a él; por lo tantoes demostrable. Ahora podemos reemplazar todas las apariciones de Q dentro de la fórmula demostrablepor alguna otra fórmula dependiente de las mismas variables, y todavía obtendremos una fórmula demostrable. ( Este es otro resultado básico del cálculo de predicados de primer orden. Dependiendo del formalismo particular adoptado para el cálculo, puede verse como una simple aplicación de una regla de inferencia de "sustitución funcional", como en el artículo de Gödel, o puede ser ser probado considerando la prueba formal de, reemplazando en él todas las apariciones de Q por alguna otra fórmula con las mismas variables libres, y observando que todos los axiomas lógicos en la demostración formal siguen siendo axiomas lógicos después de la sustitución, y todas las reglas de inferencia aún se aplican de la misma manera. )
En este caso particular, reemplazamos Q (x ', y') en con la formula . Aquí (x, y | x ', y') significa que en lugar de ψ estamos escribiendo una fórmula diferente, en la que xey se reemplazan con x 'e y'. Q (x, y) simplemente se reemplaza por.
entonces se convierte en
y esta fórmula es demostrable; ya que la parte bajo negación y después de la signo es obviamente demostrable, y la parte bajo negación y antes de la signo es, obviamente, φ, sólo con x e y sustituida por x ' e y' , vemos quees demostrable y φ es refutable. Hemos probado que φ es satisfactorio o refutable, y esto concluye la demostración del Lema .
Tenga en cuenta que no podríamos haber utilizado en lugar de Q (x ', y') desde el principio, porque no habría sido una fórmula bien formada en ese caso. Por eso no podemos utilizar ingenuamente el argumento que aparece en el comentario que precede a la prueba.
Demostrar el teorema para fórmulas de grado 1
Como se muestra en el Lema anterior, solo necesitamos demostrar nuestro teorema para las fórmulas φ en R de grado 1. φ no puede ser de grado 0, ya que las fórmulas en R no tienen variables libres y no usan símbolos constantes. Entonces la fórmula φ tiene la forma general:
Ahora definimos un orden de las k- tuplas de números naturales de la siguiente manera: debería aguantar si cualquiera , o , y precede en orden lexicográfico . [Aquí denota la suma de los términos de la tupla.] Denota la enésima tupla en este orden por .
Establecer la fórmula como . Entonces pon como
Lema : para cada n , φ.
Prueba : por inducción en n; tenemos, donde la última implicación se cumple por sustitución de variable, ya que el orden de las tuplas es tal que . Pero la última fórmula es equivalente aφ.
Para el caso base, es obviamente un corolario de φ también. Entonces el Lema está probado.
Ahora si es refutable para algún n , se sigue que φ es refutable. Por otro lado, suponga queno es refutable para ninguna n . Entonces, para cada n hay alguna forma de asignar valores de verdad a las distintas subproposiciones (ordenado por su primera aparición en ; "distinto" aquí significa predicados distintos o variables vinculadas distintas) en, tal que será verdadera cuando cada proposición se evalúe de esta manera. Esto se sigue de la integridad de la lógica proposicional subyacente .
Ahora mostraremos que existe tal asignación de valores de verdad a , para que todos será verdad: El aparecen en el mismo orden en todos los ; Definiremos inductivamente una asignación general para ellos mediante una especie de "voto mayoritario": dado que hay infinitas asignaciones (una para cada) afectando , o infinitamente muchos hacen verdadero, o infinitamente muchos lo hacen falso y solo un número finito de ellos lo hacen verdadero. En el primer caso, elegimosser verdad en general; en el segundo lo consideramos falso en general. Luego, de los infinitos n para los cuales mediante se les asigna el mismo valor de verdad que en la asignación general, elegimos una asignación general para en la misma moda.
Esta asignación general debe conducir a cada uno de los y siendo verdad, ya que si uno de los eran falsos bajo la asignación general, también sería falso para cada n> k . Pero esto contradice el hecho de que para la colección finita de asignaciones que aparecen en , hay infinitos n donde la asignación que hace true coincide con la asignación general.
De esta asignación general, que hace que todos los cierto, construimos una interpretación de los predicados del lenguaje que hace que φ sea verdadero. El universo del modelo serán los números naturales . Cada predicado i-ario debería ser cierto de los naturales precisamente cuando la proposición es verdadera en la asignación general, o no es asignada por ella (porque nunca aparece en ninguna de las ).
En este modelo, cada una de las fórmulas es cierto por construcción. Pero esto implica que φ en sí mismo es cierto en el modelo, ya que elrango sobre todas las k-tuplas posibles de números naturales. Entonces φ es satisfactorio, y hemos terminado.
Explicación intuitiva
Podemos escribir cada B i como Φ (x 1 ... x k , y 1 ... y m ) para algunas xs, que podemos llamar "primeros argumentos" y ys que podemos llamar "últimos argumentos".
Tome B 1 por ejemplo. Sus "últimos argumentos" son z 2 , z 3 ... z m + 1 , y para cada combinación posible de k de estas variables hay algo de j, de modo que aparecen como "primeros argumentos" en B j . Así, para n 1 suficientemente grande , D n 1 tiene la propiedad de que los "últimos argumentos" de B 1 aparecen, en todas las combinaciones posibles de k de ellos, como "primeros argumentos" en otros B j -s dentro de D n . Para cada B i hay un D n i con la propiedad correspondiente.
Por lo tanto, en un modelo que satisface todos los D n -s, hay objetos correspondientes a z 1 , z 2 ... y cada combinación de k de estos aparece como "primeros argumentos" en algún B j , lo que significa que para cada k de estos objetos z p 1 ... z p k hay z q 1 ... z q m , lo que hace Φ (z p 1 ... z p k , z q 1 ... z q m ) satisfecho. Al tomar un submodelo con solo estos objetos z 1 , z 2 ..., tenemos un modelo que satisface φ.
Extensiones
Extensión al cálculo de predicados de primer orden con igualdad
Gödel redujo una fórmula que contiene instancias del predicado de igualdad a otras sin él en un lenguaje extendido. Su método implica reemplazar una fórmula φ que contiene algunas instancias de igualdad con la fórmula
Aquí denotar los predicados que aparecen en φ (con sus respectivas aridades), y φ 'es la fórmula φ con todas las ocurrencias de igualdad reemplazadas con el nuevo predicado Eq . Si esta nueva fórmula es refutable, la φ original también lo era; lo mismo ocurre con la satisfacibilidad, ya que podemos tomar un cociente de modelo satisfactorio de la nueva fórmula por la relación de equivalencia que representa la ecuación . Este cociente está bien definido con respecto a los otros predicados y, por lo tanto, satisfará la fórmula original φ.
Extensión a conjuntos contables de fórmulas
Gödel también consideró el caso en el que hay una colección infinita de fórmulas. Utilizando las mismas reducciones que antes, pudo considerar solo aquellos casos en los que cada fórmula es de grado 1 y no contiene usos de igualdad. Para una colección contable de fórmulas de grado 1, podemos definir como anteriormente; entonces define ser el cierre de . El resto de la prueba se desarrolló como antes.
Extensión a conjuntos arbitrarios de fórmulas
Cuando hay una colección infinita de fórmulas, se necesita el axioma de elección (o al menos alguna forma débil). Usando el AC completo, uno puede ordenar bien las fórmulas y probar el caso incontable con el mismo argumento que el contable, excepto con inducción transfinita . Se pueden utilizar otros enfoques para demostrar que el teorema de completitud en este caso es equivalente al teorema del ideal primo de Boole , una forma débil de AC.
Referencias
- Gödel, K (1929). "Über die Vollständigkeit des Logikkalküls". Tesis doctoral. Universidad de Viena. Cite journal requiere
|journal=
( ayuda ) La primera prueba del teorema de completitud. - Gödel, K (1930). "Die Vollständigkeit der Axiome des logischen Funktionenkalküls". Monatshefte für Mathematik (en alemán). 37 (1): 349–360. doi : 10.1007 / BF01696781 . JFM 56.0046.04 . S2CID 123343522 . El mismo material que la disertación, excepto con pruebas más breves, explicaciones más sucintas y omitiendo la introducción extensa.
enlaces externos
- Enciclopedia de Filosofía de Stanford : " Kurt Gödel " —por Juliette Kennedy .
- Biografía de MacTutor: Kurt Gödel.