Prueba original del teorema de completitud de Gödel

Kurt Gödel (1925)

La prueba del teorema de completitud de Gödel dada por Kurt Gödel en su disertación doctoral de 1929 (y una versión más corta de la prueba, publicada como artículo en 1930, titulada "La completitud de los axiomas de el cálculo funcional de la lógica (en alemán)) no es fácil de leer hoy en día; utiliza conceptos y formalismos que ya no se utilizan y una terminología que suele ser 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 reafirma la prueba en el lenguaje moderno de la lógica matemática. Este esquema no debe considerarse una prueba rigurosa del teorema.

Supuestos

Trabajamos con cálculo de predicados de primer orden. Nuestros lenguajes permiten símbolos constantes, de función y de 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 algunas axiomatizaciones (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 bien conocidas servirá. La prueba original de Gödel asumió el sistema de prueba de Hilbert-Ackermann.

Asumimos sin prueba todos los resultados básicos conocidos sobre nuestro formalismo que necesitamos, como el teorema de la forma normal o el teorema de la 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 (objeto) como un símbolo de relación especial. Una vez demostrada la forma básica del teorema, será fácil extenderlo al caso del cálculo de predicados con igualdad.

Enunciado del teorema y su demostración

A continuación, establecemos dos formas equivalentes del teorema y mostramos su equivalencia.

Más tarde, demostramos el teorema. Esto se hace en los siguientes pasos:

1. Reducir el teorema a oraciones (formulas sin variables libres) en forma prenex, es decir, con todos los cuantificadores (О y ∃Al principio. Además, lo reducemos a fórmulas cuyo primer cuantificador es О. Esto es posible porque por cada frase, hay un equivalente en forma prenex cuyo primer cuantificador es О.
2. Reducir el teorema a las oraciones de la forma Оx₁Оx₂...x_k ∃Sí.₁∃Sí.₂...Sí._m φ(x₁...x_k, Sí.₁...Sí._m). Si bien no podemos hacer esto simplemente reorganizando los cuantificadores, mostramos que todavía es suficiente probar el teorema para oraciones de esa forma.
3. Finalmente demostramos el teorema de oraciones de esa forma.
   • Esto se hace notando primero que una frase como B =x₁Оx₂...x_k ∃Sí.₁∃Sí.₂...Sí._m φ(x₁...x_k, Sí.₁...Sí._m) o es refutable (su negación es siempre verdadera) o satisfizo, es decir, hay un modelo en el que sostiene (puede incluso ser siempre cierto, es decir, una tautología); este modelo simplemente está asignando valores de verdad a las subproposiciones de las cuales se construye B. La razón de ello es la integridad de la lógica proposicional, con los cuantificadores existenciales que no juegan ningún papel.
   • Ampliamos este resultado a frases más complejas y largas, D_n (n=1,2...), construido de B, para que cualquiera de ellos sea refutable y por lo tanto es φ, o todos ellos no son refutables y por lo tanto cada sostiene en algún modelo.
   • Finalmente utilizamos los modelos en los que el D_n mantener (en caso de que todos no sean refutables) para construir un modelo en el que φ sostiene.

Teorema 1. Toda fórmula válida (verdadera en todas las estructuras) es demostrable.

Esta es la forma más básica del teorema de completitud. Inmediatamente lo reafirmamos 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,F> (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" semblante posiblemente conjuntos vacíos para U. Para obtener más información sobre 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 se cumple el Teorema 1 y φ no se puede satisfacer en ninguna estructura, entonces ¬φ es válido en todas las estructuras y, por lo tanto, demostrable, por lo que φ es refutable y el Teorema 2 sostiene Si, por el contrario, se cumple el Teorema 2 y φ es válido en todas las estructuras, entonces ¬φ no se satisface en ninguna estructura y, por lo tanto, es refutable; entonces ¬¬φ es demostrable y luego φ también, por lo que se cumple el Teorema 1.

Prueba del teorema 2: primer paso

Nos acercamos a la prueba del Teorema 2 restringiendo sucesivamente la clase de todas las fórmulas φ para las que necesitamos demostrar que "φ es refutable o satisfactorio". Al principio necesitamos probar esto para todas las posibles fórmulas φ en nuestro lenguaje. Sin embargo, supongamos 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 satisfactoria" → "φ es refutable o satisfactorio". Entonces, una vez probada esta afirmación (expresada en la oración anterior), será suficiente probar que "φ es refutable o satisfactorio" solo para φ's pertenecientes a la clase C. Si φ es demostrablemente equivalente a ψ (es decir,, (φ≡ψ) es demostrable), entonces es cierto que "ψ es refutable o satisfactorio" → "φ es refutable o satisfactorio" (Se necesita el teorema de solidez para demostrar esto).

Existen técnicas estándar para reescribir una fórmula arbitraria en una que no use función o símbolos constantes, a costa de introducir cuantificadores adicionales; por lo tanto, supondremos 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 funciones ni símbolos constantes) y aplicamos el teorema de la forma prenex para encontrar una fórmula ψ en forma normal tal que φ≡ψ (siendo ψ en forma normal significa que todos los cuantificadores en ψ, si los hay, se encuentran al principio de ψ). Se sigue ahora que solo necesitamos probar el Teorema 2 para fórmulas φ en forma normal.

A continuación, eliminamos todas las variables libres de φ por cuantificarlas existencialmente: si, digamos, x₁...x_n son libres en φ, formamos ↑ ↑ =∃ ∃ x1...∃ ∃ xnφ φ {displaystyle psi =exists x_{1}exists x_{n}phi }. Si  es satisfiable en una estructura M, entonces ciertamente es φ y si י es refutable, entonces ¬ ¬ ↑ ↑ =О О x1...О О xn¬ ¬ φ φ {displaystyle neg psi =forall Para todos x_{n}neg phi } es provable, y entonces es ¬φ, por lo tanto φ es refutable. Vemos que podemos restringir φ para ser un sentencia, es decir, una fórmula sin variables libres.

Por último, quisiéramos, por razones de conveniencia técnica, que la prefijo de φ (es decir, la cadena de cuantificadores al principio de φ, que es en forma normal) comienza con un cuantificador universal y termina 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 solo lugar F no utilizado en φ, y dos nuevas variables Sí. y z.. Si φ = (P) Negotiat, donde (P) representa el prefijo de φ y Ё para el matriz (la parte restante, sin cuantificación de φ) formamos ↑ ↑ =О О Sí.()P)∃ ∃ z()CCPR CCPR ∧ ∧ [F()Sí.)Alternativa Alternativa ¬ ¬ F()z)]){displaystyle psi =forall y(P)exists z(Phi wedge [F(y)vee neg F(z)]}. Desde О О Sí.∃ ∃ z()F()Sí.)Alternativa Alternativa ¬ ¬ F()z)){displaystyle forall yexists z(F(y)vee neg F(z)} es claramente provable, es fácil ver que φ φ =↑ ↑ {displaystyle phi =psi } es provable.

Reduciendo 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 a la clase de todas estas fórmulas R. Nos enfrentamos a probar que cada fórmula en R es refutable o satisfactoria. Dada nuestra fórmula φ, agrupamos cadenas de cuantificadores de un tipo en bloques:

φ φ =()О О x1...О О xk1)()∃ ∃ xk1+1...∃ ∃ xk2).......()О О xkn− − 2+1...О О xkn− − 1)()∃ ∃ xkn− − 1+1...∃ ∃ xkn)()CCPR CCPR ){displaystyle phi =(forall x_{1}...forall x_{k_{1})(exists) x_{k_{1}+1}...exists x_{k_{2})...(forall) x_{k_{n-2}+1} #### x_{k_{n-1}+1} ¿Qué?

Definimos el grado de φ φ {displaystyle phi } ser el número de bloques cuantificadores universales, separados por bloques cuantificadores existenciales como se muestra anteriormente, en el prefijo de φ φ {displaystyle phi }. El siguiente lema, que Gödel adaptó de la prueba de Skolem del teorema de Löwenheim–Skolem, nos permite reducir marcadamente la complejidad de la fórmula genérica φ φ {displaystyle phi } Necesitamos probar 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 cada fórmula en R de grado k+1 .

Comentario: Tomar una fórmula φ de grado k+1 de la forma φ φ =()О О x)()∃ ∃ Sí.)()О О u)()∃ ∃ v)()P)↑ ↑ {displaystyle phi =(forall x)(exists y)(forall u)(exists v)(P)psi }, donde ()P)↑ ↑ {displaystyle (P)psi } es el resto de φ φ {displaystyle phi } (es así de grado k-1). φ afirma que para cada x hay un y tal que... (algo). Hubiera sido agradable tener un predicado Q ' así que por cada x, Q'(x,y) sería cierto si y sólo si usted es el requerido para hacer (algo) verdad. Entonces podríamos haber escrito una fórmula de grado k, que es equivalente a φ, es decir, ()О О x.)()О О x)()О О Sí.)()О О u)()∃ ∃ v)()∃ ∃ Sí..)()P)Q.()x.,Sí..)∧ ∧ ()Q.()x,Sí.)→ → ↑ ↑ ){displaystyle (forall x')(forall x)(forall you)(exists v)(exists y')(P)Q'(x',y')wedge (Q'(x,y)rightarrow psi)}. Esta fórmula es realmente equivalente a φ porque afirma que para cada x, si hay un y que satisfice Q'(x,y), entonces (algo) sostiene, y además, sabemos que hay tal y, porque para cada x', hay un y' que satisface Q'(x',y'). Por lo tanto φ sigue de esta fórmula. También es fácil mostrar que si la fórmula es falsa, entonces también es φ. Lamentablemente, en general no hay tal predicado Q'. Sin embargo, esta idea puede entenderse como base para la siguiente prueba del Lemma.

Demostración. Sea φ una fórmula de grado k+1; entonces podemos escribirlo como

φ φ =()О О x)()∃ ∃ Sí.)()О О u)()∃ ∃ v)()P)↑ ↑ {displaystyle phi =(forall x)(exists y)(forall u)(exists v)(P)psi }

Donde (P) es el resto del prefijo de φ φ {displaystyle phi } (es así de grado k-1) y ↑ ↑ {displaystyle psi } es la matriz sin cuantificación de φ φ {displaystyle phi }. x, Sí., u y v Denota aquí tuples de variables en lugar de variables individuales; Por ejemplo. ()О О x){displaystyle (forall x)} realmente significa О О x1О О x2...О О xn{displaystyle forall x_{1}forall Para todos x_{n} Donde x1...xn{displaystyle x_{1}...x_{n} son algunas variables distintas.

Sean ahora x' y y' tuplas de variables previamente no utilizadas de la misma longitud que x y y respectivamente, y sea Q un símbolo de relación no utilizado anteriormente que toma tantos argumentos como la suma de las longitudes de x e y; consideramos la formula

CCPR CCPR =()О О x.)()∃ ∃ Sí..)Q()x.,Sí..)∧ ∧ ()О О x)()О О Sí.)()Q()x,Sí.)→ → ()О О u)()∃ ∃ v)()P)↑ ↑ ){displaystyle Phi =(forall x')(exists y')Q(x',y')wedge (forall x)(forall y)(Q(x,y)rightarrow (forall u)(exists v)psi)}

Claramente, CCPR CCPR → → φ φ {displaystyle Phi rightarrow phi } es provable.

Ahora desde la cadena de cuantificadores ()О О u)()∃ ∃ v)()P){displaystyle (forall u)(exists v)(P)} no contiene variables x o Sí., la siguiente equivalencia es fácilmente provable con la ayuda de cualquier formalismo que estamos utilizando:

()Q()x,Sí.)→ → ()О О u)()∃ ∃ v)()P)↑ ↑ )↑ ↑ ()О О u)()∃ ∃ v)()P)()Q()x,Sí.)→ → ↑ ↑ ){displaystyle (Q(x,y)rightarrow (forall u)(exists v)(P)psi)equiv (forall u)(exists v)(P)(Q(x,y)rightarrow psi)}

Y como estas dos fórmulas son equivalentes, si reemplazamos la primera con la segunda dentro de Φ, obtenemos la fórmula Φ' tal que Φ≡Φ':

CCPR CCPR .=()О О x.)()∃ ∃ Sí..)Q()x.,Sí..)∧ ∧ ()О О x)()О О Sí.)()О О u)()∃ ∃ v)()P)()Q()x,Sí.)→ → ↑ ↑ ){displaystyle Phi '=(forall x')(exists y')Q(x',y')wedge (forall x)(forall y)(forall u)(exists v)(Q(x,y)rightarrow psi)}

Ahora ⋅" tiene la forma ()S)*** *** ∧ ∧ ()S.)*** *** .{displaystyle (S)rho wedge (S')rho '}, donde (S) y (S') son algunas cadenas cuantificadoras, ρ y ρ' son libres de cuantificadores, y, Más, ninguna variable (S) ocurre en ρ' y ninguna variable de (S') ocurre en ρ. En tales condiciones cada fórmula de la forma ()T)()*** *** ∧ ∧ *** *** .){displaystyle (T)(rho wedge rho)}, donde (T) es una cadena de cuantificadores que contienen todos los cuantificadores en (S) y (S') entrelazados entre sí de cualquier manera, pero manteniendo el orden relativo dentro (S) y (S'), será equivalente a la fórmula original ⋅'(este es otro resultado básico en cálculo predicado de primera orden que confiamos en). Para saber, formamos Ψ como sigue:

Ψ Ψ =()О О x.)()О О x)()О О Sí.)()О О u)()∃ ∃ Sí..)()∃ ∃ v)()P)Q()x.,Sí..)∧ ∧ ()Q()x,Sí.)→ → ↑ ↑ ){displaystyle Psi =(forall x')(forall x)(forall y)(forall u)(exists y')(exists v)(P)Q(x',y')wedge (Q(x,y)rightarrow psi)}

y tenemos CCPR CCPR .↑ ↑ Ψ Ψ {displaystyle Phi 'equiv Psi }.

Ahora Ψ Ψ {displaystyle Psi } es una fórmula de grado k y por lo tanto por suposición, ya sea refutable o satisfizo. Si Ψ Ψ {displaystyle Psi } es satisfizo en una estructura M, entonces, considerando Ψ Ψ ↑ ↑ CCPR CCPR .↑ ↑ CCPR CCPR ∧ ∧ CCPR CCPR → → φ φ {displaystyle Psi equiv Phi 'equiv Phi wedge Phi rightarrow phi }, vemos que φ φ {displaystyle phi } es satisfizo también. Si Ψ Ψ {displaystyle Psi } es refutable, entonces lo es CCPR CCPR {displaystyle Phi }, que es equivalente a él; por lo tanto ¬ ¬ CCPR CCPR {displaystyle neg Phi } es provable. Ahora podemos reemplazar todas las ocurrencias de Q dentro de la fórmula provable ¬ ¬ CCPR CCPR {displaystyle neg Phi } por alguna otra fórmula dependiente de las mismas variables, y todavía conseguiremos una fórmula provable. ()Este es otro resultado básico de cálculo predicado de primer orden. Dependiendo del formalismo particular adoptado para el cálculo, se puede ver como una simple aplicación de una regla de inferencia "sustitución funcional", como en el periódico de Gödel, o puede ser probado considerando la prueba formal de la inferencia ¬ ¬ CCPR CCPR {displaystyle neg Phi }, reemplazando en ella todas las ocurrencias de Q por alguna otra fórmula con las mismas variables libres, y observando que todos los axiomas lógicos en la prueba formal siguen siendo axiomas lógicos después de la sustitución, y todas las reglas de inferencia siguen siendo aplicables de la misma manera.)

En este caso en particular, reemplazamos Q(x',y') en ¬ ¬ CCPR CCPR {displaystyle neg Phi } con la fórmula ()О О u)()∃ ∃ v)()P)↑ ↑ ()x,Sí.Silenciox.,Sí..){displaystyle (forall u)(exists v)(P)psi (x,y sometidax',y')}. Aquí (x,y la vida eternax',y') significa que en lugar de ↓ estamos escribiendo una fórmula diferente, en la que x y y son reemplazados por x' y y'. Q(x,y) es simplemente reemplazado por ()О О u)()∃ ∃ v)()P)↑ ↑ {displaystyle (forall u)(exists v)(P)psi }.

¬ ¬ CCPR CCPR {displaystyle neg Phi } entonces se vuelve

¬ ¬ ()()О О x.)()∃ ∃ Sí..)()О О u)()∃ ∃ v)()P)↑ ↑ ()x,Sí.Silenciox.,Sí..)∧ ∧ ()О О x)()О О Sí.)()()О О u)()∃ ∃ v)()P)↑ ↑ → → ()О О u)()∃ ∃ v)()P)↑ ↑ )){displaystyle neg (forall x')(exists y')(forall u)(exists v)(P)psi (x,y',y')wedge (forall x)(forall y)(forall u)(exists v)(P)psi rightarrow (forall u)(expsiists v)

y esta fórmula es provable, ya que la parte bajo negación y después de la ∧ ∧ {displaystyle wedge } señal es obviamente provable, y la parte bajo negación y antes de la ∧ ∧ {displaystyle wedge } la señal es obviamente φ, sólo con x y Sí. sustituido por x ' y Sí. ', vemos que ¬ ¬ φ φ {displaystyle neg phi } es provable, y φ es refutable. Hemos demostrado que el φ es satisfizo o refutable, y esto concluye la prueba de la Lemma.

Note que no podríamos haber usado ()О О u)()∃ ∃ v)()P)↑ ↑ ()x,Sí.Silenciox.,Sí..){displaystyle (forall u)(exists v)(P)psi (x,y sometidax',y')} en lugar de Q(x',y') desde el principio, porque Ψ Ψ {displaystyle Psi } 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.

Comentario: La prueba hasta ahora parece tener el siguiente error importante: Ё, Ё', y Ψ son conocidos por ser de grado k, que se asume para la inducción en k, sólo bajo la suposición de que Q es de grado 0. El paso anterior que reemplaza Q(x',y') en ⌝ ⌝ {displaystyle urcorner } Negotiat with (О О {displaystyle forall }u)∃ ∃ {displaystyle exists }v)(P)Ψ(x,y',y') hace de Q a ser de grado k, violando esta suposición para k ≤ 0, invalidando así el paso de inducción del grado k al grado k+1.

Este argumento con más detalle:

Una parte importante de la prueba es la inducción sobre el grado de la fórmula sentencial arbitraria (significativa) φ, que muestra que para todo número entero k ≥ 1, si el teorema se cumple para una fórmula de grado k, entonces se cumple para uno de grado k+1, es decir, si toda fórmula oracional válida de grado k es demostrable (lo que equivale a que toda fórmula oracional de grado k sea refutable o satisfactoria), entonces toda fórmula de grado k+1 es demostrable (si es que equivalente para fórmulas oracionales de grado k+1). Para hacer esto, la prueba construye fórmulas Φ ≡ Φ' ≡ Ψ, cada uno conteniendo la relación Q e implicando un φ arbitrario de grado k+1, cada uno de los cuales tres es de grado k si y solo si Q es de grado 0, lo cual asume la prueba, de modo que por la hipótesis de inducción que el El teorema se cumple para cada fórmula proposicional de grado k, las tres fórmulas son refutables o satisfactorias. Entonces, si cualquiera de los tres es satisfacible, φ también lo es (por la estructura detallada de las fórmulas). Si alguno es refutable, entonces ¬Φ es demostrable. Sin embargo, la prueba luego reemplaza Q en ¬Φ con una fórmula de grado k, violando así la suposición de inducción de que Q es de grado 0, pero la prueba, no obstante, concluye que, debido a la hipótesis de inducción, si Φ no es satisfacible, entonces es refutable, entonces ¬Φ es demostrable, entonces (debido a la estructura detallada de Φ) ¬φ es demostrable, entonces φ es refutable, entonces si el teorema es verdadero para todas las fórmulas oracionales de grado k, es verdadero para todas las fórmulas de grado k+1, por lo que es cierto para todo k si se puede demostrar que es cierto para k = 1, lo que supuestamente se hace en la siguiente sección de la demostración. La violación de la prueba de la suposición esencial de que Q es de grado 0 invalida el argumento de inducción, por lo que invalida la prueba. Este aparente error se encuentra en el argumento original de Gödel, tal como figura en las Obras completas de Kurt Gödel, vol. 3, ed. por Solomon Feferman et al., Oxford University Press, 1995.

Referencias: Aristóteles para lógica básica, Lógica matemática de Joseph Shoenfield para teoría de prueba, Teoría de conjuntos de Thomas Jech para teoría de modelos

Demostración del teorema para fórmulas de grado 1

Como muestra el Lema anterior, solo necesitamos probar 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 tiene variables libres y no usa símbolos constantes. Entonces la fórmula φ tiene la forma general:

()О О x1...xk)()∃ ∃ Sí.1...Sí.m)φ φ ()x1...xk,Sí.1...Sí.m).{displaystyle (forall x_{1}...x_{k})(exists y_{1}...y_{m})phi (x_{1}...x_{k},y_{1}...y_{m}).}

Ahora definimos un orden de los k-tuples de números naturales como sigue: <math alttext="{displaystyle (x_{1}...x_{k})()x1...xk).()Sí.1...Sí.k){displaystyle (x_{1}...x_{k}) Se hizo(y_{1}...y_{k} }<img alt="(x_{1}...x_{k}) debe esperar si <math alttext="{displaystyle Sigma _{k}(x_{1}...x_{k}).. k()x1...xk)... k()Sí.1...Sí.k){displaystyle Sigma _{k}(x_{1}...x_{k} Sigma _{k}(y_{1}...y_{k}) }<img alt="Sigma _{k}(x_{1}...x_{k}), o .. k()x1...xk)=.. k()Sí.1...Sí.k){displaystyle Sigma _{k}(x_{1}...x_{k})= Sigma _{k}(y_{1}...y_{k}) }, y ()x1...xk){displaystyle (x_{1}...x_{k}} precedes ()Sí.1...Sí.k){displaystyle (y_{1}...y_{k}} en orden lexicográfico. [Aquí] .. k()x1...xk){displaystyle Sigma _{k}(x_{1}...x_{k}) } denota la suma de los términos del tuple.] Denota el nth tuple en este orden por ()a1n...akn){displaystyle (a_{1}{n}...a_{n}) }.

Establecer la fórmula Bn{displaystyle B_{n} como φ φ ()za1n...zakn,z()n− − 1)m+2,z()n− − 1)m+3...znm+1){displaystyle phi (z_{a_{1} {n}...z_{a_{k}{n},z_{(n-1)m+2},z_{(n-1)m+3}...z_{nm+1})}. Entonces ponte Dn{displaystyle D_{n} como

()∃ ∃ z1...znm+1)()B1∧ ∧ B2...∧ ∧ Bn).{displaystyle (exists z_{1}...z_{nm+1})(B_{1}wedge B_{2}...wedge B_{n}

LemmaPor todos n, φ→ → Dn{displaystyle rightarrow D_{n}.

Prueba: Por inducción en n; tenemos DkAlternativa Alternativa Dk− − 1∧ ∧ ()О О z1...z()n− − 1)m+1)()∃ ∃ z()n− − 1)m+2...znm+1)BnAlternativa Alternativa Dk− − 1∧ ∧ ()О О za1n...zakn)()∃ ∃ Sí.1...Sí.m)φ φ ()za1n...zakn,Sí.1...Sí.m){displaystyle D_{k}Leftarrow D_{k-1}wedge (forall z_{1}...z_{(n-1)m+1})(exists z_{(n-1)m+2}...z_{nm+1})B_{n}Leftarrow ¿Por qué? }, donde esta última implicación sostiene por sustitución variable, ya que el orden de los tuples es tal que <math alttext="{displaystyle (forall k)({a_{1}^{n}}...{a_{k}^{n}})()О О k)()a1n...akn).()n− − 1)m+2{displaystyle (forall k)({a_{1}{n}...{a_{n}} {n-1)m+2}<img alt="(forall k)({a_{1}^{n}}...{a_{k}^{n}}). Pero la última fórmula es equivalente a Dk− − 1∧ ∧ {displaystyle D_{k-1}wedge }φ.

Para el caso base, D1↑ ↑ ()∃ ∃ z1...zm+1)φ φ ()za11...zak1,z2,z3...zm+1)↑ ↑ ()∃ ∃ z1...zm+1)φ φ ()z1...z1,z2,z3...zm+1){displaystyle D_{1}equiv (exists z_{1}...z_{m+1})phi (z_{a_{1} {1}}...z_{a_ k} {1},z_{2},z_{3}...z_{m+1})equiv (exists z_{1}...z_{m+1})phi (z_{1}...z_{1},z_{2},z_{3}...z_{m+1}) } es obviamente un corolario de φ también. Así que... Lemma está probado.

Ahora si Dn{displaystyle D_{n} es refutable para algunos n, sigue que φ es refutable. Por otro lado, supongamos que Dn{displaystyle D_{n} no es refutable para ningún n. Entonces para cada uno n hay alguna manera de asignar valores de verdad a las distintas subproposiciones Eh{displaystyle E_{h} (ordenado por su primera aparición en Dn{displaystyle D_{n}; "distinto" aquí significa o bien distintos predicados, o variables ligadas distintas) en Bk{displaystyle B_{k}, tal que Dn{displaystyle D_{n} será verdad cuando cada propuesta sea evaluada de esta manera. Esto se deriva de la integridad de la lógica proposición subyacente.

Ahora demostraremos que hay una asignación de valores de verdad a Eh{displaystyle E_{h}Así que todo Dn{displaystyle D_{n} será verdad: El Eh{displaystyle E_{h} aparecen en el mismo orden en cada Dn{displaystyle D_{n}; definiremos inductivamente una asignación general a ellos por una especie de "voto mayoritario": Puesto que hay infinitamente muchas asignaciones (una para cada uno Dn{displaystyle D_{n}) afectando E1{displaystyle E_{1}, o infinitamente muchos hacen E1{displaystyle E_{1} verdadero, o infinitamente muchos lo hacen falso y sólo finitamente muchos lo hacen realidad. En el caso anterior, elegimos E1{displaystyle E_{1} ser verdad en general; en este último lo consideramos falso en general. Entonces desde el infinito muchos n para la cual E1{displaystyle E_{1} a través de Eh− − 1{displaystyle E_{h-1} se asigna el mismo valor de verdad que en la asignación general, escogemos una asignación general a Eh{displaystyle E_{h} de la misma manera.

Esta asignación general debe llevar a cada uno de los Bk{displaystyle B_{k} y Dk{displaystyle D_{k} ser verdad, ya que si uno de los Bk{displaystyle B_{k} eran falsos bajo la asignación general, Dn{displaystyle D_{n} también sería falso para cada uno n. Pero esto contradice el hecho de que para la colección finita de general Eh{displaystyle E_{h} asignaciones que aparecen en Dk{displaystyle D_{k}, hay infinitamente muchos n donde se realiza la asignación Dn{displaystyle D_{n} verdadero coincide con la asignación general.

De esta asignación general, que hace todo Dk{displaystyle D_{k} verdad, construimos una interpretación de los predicados del lenguaje que hace que φ sea verdad. El universo del modelo será los números naturales. Cada predicación i-ary Ψ Ψ {displaystyle Psi } debe ser verdad de los naturales ()u1...ui){displaystyle (u_{1}...u_{i}} precisamente cuando la proposición Ψ Ψ ()zu1...zui){displaystyle Psi (z_{u_{1}...z_{u_{i}) } es cierto en la asignación general, o no asignada por ella (porque nunca aparece en ninguna de las Dk{displaystyle D_{k}).

En este modelo, cada una de las fórmulas ()∃ ∃ Sí.1...Sí.m)φ φ ()a1n...akn,Sí.1...Sí.m){displaystyle (exists y_{1}...y_{m})phi (a_{1}{n}...a_{k}^{n},y_{1}...y_{m} } es cierto por la construcción. Pero esto implica que φ en sí es cierto en el modelo, ya que an{displaystyle a^{n} rango sobre todos los posibles k-tuples de números naturales. Así que φ es satisfizo, y hemos terminado.

Explicación intuitiva

Podemos escribir cada B_i como Φ(x₁...x_k,y₁...y_m) para algunos x-s, que podemos llamar "primeros argumentos" y y-s que podemos llamar "últimos argumentos".

Tome B₁ por ejemplo. Sus "últimos argumentos" son z₂,z₃...z_m+1, y para cada combinación posible de k de estas variables hay algo de j entonces que aparecen como "primeros argumentos" en B_j. Por lo tanto, para n₁ lo suficientemente grande, D_n1 tiene la propiedad de que los "últimos argumentos" de B₁ 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 existe un D_ni con la propiedad correspondiente.

Por lo tanto, en un modelo que satisface todos los D_n-s, hay objetos correspondientes a z₁, z₂... y cada combinación de k de estos aparece como "primeros argumentos" en algunos B_j, lo que significa que para cada k de estos objetos z_p1...z_pk hay z_q1...z_qm, lo que hace que Φ (z_p1...z_pk,z_q1...z_qm) satisfecho. Al tomar un submodelo con solo estos objetos z₁, z₂..., 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 contenía instancias del predicado de igualdad a otras que no lo tenían en un lenguaje extendido. Su método consiste en reemplazar una fórmula φ que contiene algunos casos de igualdad con la fórmula

()О О x)Eq()x,x)∧ ∧ ()О О x,Sí.,z)[Eq()x,Sí.)→ → ()Eq()x,z)→ → Eq()Sí.,z))]{displaystyle (forall x)Eq(x,x)wedge (forall x,y,z)[Eq(x,y)rightarrow (Eq(x,z)rightarrow Eq(y,z)]} ∧ ∧ ()О О x,Sí.,z)[Eq()x,Sí.)→ → ()Eq()z,x)→ → Eq()z,Sí.))]{displaystyle wedge (forall x,y,z)[Eq(x,y)rightarrow (Eq(z,x)rightarrow Eq(z,y)]}
∧ ∧ {displaystyle wedge }
()О О x1...xk,Sí.1...xk)[()Eq()x1,Sí.1)∧ ∧ ...∧ ∧ Eq()xk,Sí.k))→ → ()A()x1...xk)↑ ↑ A()Sí.1...Sí.k))]{displaystyle (forall x_{1}...x_{k},y_{1}...x_{k})[(Eq(x_{1},y_{1})wedge...wedge Eq(x_{k},y_{k}))rightarrow (A(x_{1}...x_{k})equiv A(y_{1}...y_{k})}]
∧ ∧ ...∧ ∧ {displaystyle wedge...wedge }
()О О x1...xm,Sí.1...xm)[()Eq()x1,Sí.1)∧ ∧ ...∧ ∧ Eq()xm,Sí.m))→ → ()Z()x1...xm)↑ ↑ Z()Sí.1...Sí.m))]{displaystyle (forall x_{1}...x_{m},y_{1}...x_{m})[(Eq(x_{1},y_{1})wedge...wedge Eq(x_{m},y_{m}))rightarrow (Z(x_{1}...x_{m})equiv Z(y_{1}...y_{m})}]}
∧ ∧ {displaystyle wedge }
φ φ ..{displaystyle varphi.}

Aquí. A...Z{displaystyle A...Z} denota los predicados que aparecen en φ (con k...m{displaystyle k...m} sus respectivas aridades), y φ' es la fórmula φ con todas las ocurrencias de igualdad reemplazadas por el nuevo predicado Eq. Si esta nueva fórmula es refutable, el φ original también fue; lo mismo es cierto de satisfiabilidad, ya que podemos tomar un cociente de modelo satisfactorio de la nueva fórmula por la relación de equivalencia que representa la Eq. 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 donde hay una colección contablemente infinita de fórmulas. Utilizando las mismas reducciones que antes, sólo pudo examinar los casos en que cada fórmula es del grado 1 y no contiene usos de la igualdad. Para una colección contable de fórmulas φ φ i{displaystyle phi ^{i} de grado 1, podemos definir Bki{displaystyle B_{k} {i} como arriba; entonces definir Dk{displaystyle D_{k} para ser el cierre de B11...Bk1,...,B1k...Bkk{displaystyle B_{1} {1}... B_{k}{1},... B_{k} {k}. El resto de la prueba pasó entonces como antes.

Extensión a conjuntos arbitrarios de fórmulas

Cuando hay una colección incontablemente infinita de fórmulas, se necesita el Axioma de Elección (o al menos alguna forma débil del mismo). 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 usar otros enfoques para probar que el teorema de completitud en este caso es equivalente al teorema del ideal primo booleano, una forma débil de AC.