En este artículo se presenta un esbozo de una demostración del primer teorema de incompletitud de Gödel . Este teorema se aplica a cualquier teoría formal que satisfaga ciertas hipótesis técnicas, que se analizan según sea necesario durante el esbozo. Supondremos durante el resto del artículo que se ha seleccionado una teoría fija que satisface estas hipótesis.
En este artículo, la palabra "número" se refiere a un número natural (incluido el 0). La propiedad clave que poseen estos números es que cualquier número natural se puede obtener comenzando con el número 0 y sumando 1 un número finito de veces.
El teorema de Gödel se aplica a cualquier teoría formal que satisfaga ciertas propiedades. Cada teoría formal tiene una signatura que especifica los símbolos no lógicos en el lenguaje de la teoría. Para simplificar, supondremos que el lenguaje de la teoría está compuesto por la siguiente colección de 15 (y sólo 15) símbolos:
Este es el lenguaje de la aritmética de Peano . Una fórmula bien formada es una secuencia de estos símbolos que se forma de modo que tenga una lectura bien definida como una fórmula matemática. Por lo tanto, x = SS 0 está bien formada mientras que x = ∀+ no está bien formada. Una teoría es un conjunto de fórmulas bien formadas sin variables libres .
Una teoría es consistente si no existe una fórmula F tal que tanto F como su negación sean demostrables. La ω-consistencia es una propiedad más fuerte que la consistencia. Supongamos que F ( x ) es una fórmula con una variable libre x . Para ser ω-consistente, la teoría no puede demostrar tanto ∃ m F ( m ) como ¬ F ( n ) para cada número natural n .
Se supone que la teoría es eficaz, lo que significa que el conjunto de axiomas debe ser recursivamente enumerable . Esto significa que es teóricamente posible escribir un programa informático de longitud finita que, si se le permitiera ejecutarse indefinidamente, generaría los axiomas de la teoría (incluyendo necesariamente cada instancia bien formada del esquema axiomático de inducción ) uno a la vez y no generaría nada más. Este requisito es necesario; hay teorías que son completas , consistentes e incluyen aritmética elemental, pero ninguna teoría de ese tipo puede ser eficaz.
El esquema que se presenta aquí se divide en tres partes. En la primera parte, a cada fórmula de la teoría se le asigna un número, conocido como número de Gödel, de manera que se pueda recuperar la fórmula de manera efectiva a partir del número. Esta numeración se extiende para cubrir secuencias finitas de fórmulas. En la segunda parte, se construye una fórmula específica PF ( x , y ) de manera que para dos números cualesquiera n y m , PF ( n , m ) se cumple si y solo si n representa una secuencia de fórmulas que constituye una prueba de la fórmula que m representa. En la tercera parte de la prueba, construimos una fórmula autorreferencial que, informalmente, dice "No soy demostrable", y demostramos que esta oración no es demostrable ni refutable dentro de la teoría.
Es importante destacar que todas las fórmulas de la prueba se pueden definir mediante funciones recursivas primitivas , que a su vez se pueden definir en aritmética de Peano de primer orden .
El primer paso de la demostración es representar las fórmulas (bien formadas) de la teoría y las listas finitas de estas fórmulas como números naturales. Estos números se denominan números de Gödel de las fórmulas.
Comience asignando un número natural a cada símbolo del lenguaje de la aritmética, de manera similar a la manera en que el código ASCII asigna un número binario único a cada letra y a ciertos otros caracteres. En este artículo se empleará la siguiente asignación, muy similar a la que utilizó Douglas Hofstadter en su obra Gödel, Escher, Bach : [1]
El número de Gödel de una fórmula se obtiene concatenando los números de Gödel de cada símbolo que compone la fórmula. Los números de Gödel de cada símbolo están separados por un cero porque, por diseño, ningún número de Gödel de un símbolo incluye un 0. Por lo tanto, cualquier fórmula puede recuperarse correctamente a partir de su número de Gödel. Sea G ( F ) el número de Gödel de la fórmula F .
Dada la numeración de Gödel anterior, la oración que afirma que la adición conmuta , ∀ x ∀ x * ( x + x * = x * + x ) se traduce como el número:
(Se han insertado espacios a cada lado de cada 0 solo para facilitar la lectura; los números de Gödel son concatenaciones estrictas de dígitos decimales). No todos los números naturales representan una oración. Por ejemplo, el número
se traduce como " = ∀ + x ", que no está bien formado.
Como cada número natural se puede obtener aplicando la operación sucesora S a 0 un número finito de veces, cada número natural tiene su propio número de Gödel. Por ejemplo, el número de Gödel correspondiente a 4, SSSS 0 , es:
La asignación de números de Gödel se puede extender a listas finitas de fórmulas. Para obtener el número de Gödel de una lista de fórmulas, escriba los números de Gödel de las fórmulas en orden, separándolos por dos ceros consecutivos. Dado que el número de Gödel de una fórmula nunca contiene dos ceros consecutivos, cada fórmula de una lista de fórmulas se puede recuperar de manera efectiva a partir del número de Gödel de la lista.
Es crucial que la aritmética formal sea capaz de probar un conjunto mínimo de hechos. En particular, debe ser capaz de probar que cada número m tiene un número de Gödel G ( m ) . Un segundo hecho que la teoría debe probar es que dado cualquier número de Gödel G ( F ( x )) de una fórmula F ( x ) con una variable libre x y cualquier número m , existe un número de Gödel de la fórmula F ( m ) obtenido al reemplazar todas las ocurrencias de G ( x ) en G ( F ( x )) con G ( m ) , y que este segundo número de Gödel puede obtenerse efectivamente a partir del número de Gödel G ( F ( x )) de F ( x ) como una función de G ( x ) . Para ver que esto es de hecho posible, observe que dado el número de Gödel de F ( x ) , se puede recrear la fórmula original F ( x ) , hacer la sustitución de x por m y luego encontrar el número de Gödel G ( F ( m )) de la fórmula resultante F ( m ) . Este es un procedimiento uniforme.
Las reglas de deducción pueden entonces representarse por relaciones binarias en números de Gödel de listas de fórmulas. En otras palabras, supongamos que hay una regla de deducción D 1 , por la cual uno puede pasar de las fórmulas S 1 , S 2 a una nueva fórmula S . Entonces la relación R 1 correspondiente a esta regla de deducción dice que n está relacionado con m (en otras palabras, n R 1 m se cumple) si n es el número de Gödel de la lista de fórmulas que contiene S 1 y S 2 y m es el número de Gödel de la lista de fórmulas que contiene S 1 , S 2 y S . Debido a que cada regla de deducción es concreta, es posible determinar efectivamente para cualesquiera números naturales n y m si están relacionados por la relación.
La segunda etapa de la prueba consiste en utilizar la numeración de Gödel, descrita anteriormente, para demostrar que la noción de demostrabilidad puede expresarse dentro del lenguaje formal de la teoría. Supongamos que la teoría tiene reglas de deducción: D 1 , D 2 , D 3 , ... . Sean R 1 , R 2 , R 3 , ... sus relaciones correspondientes, como se describió anteriormente.
Cada enunciado demostrable es un axioma en sí mismo, o puede deducirse de los axiomas mediante un número finito de aplicaciones de las reglas de deducción. Una demostración de una fórmula S es en sí misma una cadena de enunciados matemáticos relacionados por relaciones particulares (cada uno es un axioma o está relacionado con enunciados anteriores mediante reglas de deducción), donde el último enunciado es S . Por tanto, se puede definir el número de Gödel de una demostración. Además, se puede definir una forma de enunciado Demostración ( x , y ) , que para cada dos números x e y es demostrable si y solo si x es el número de Gödel de una demostración del enunciado S e y = G ( S ) .
La demostración ( x , y ) es, de hecho, una relación aritmética, como lo es " x + y = 6 ", aunque mucho más complicada. Dada una relación como R ( x , y ) , para dos números específicos cualesquiera n y m , se puede demostrar tanto la fórmula R ( m , n ) , como su negación ¬R ( m , n ) , pero no ambas. Esto se debe a que la relación entre estos dos números se puede "comprobar" de forma sencilla. Formalmente, esto se puede demostrar por inducción, donde se construyen todas estas relaciones posibles (cuyo número es infinito) una por una. La construcción detallada de la fórmula Demostración hace uso esencial del supuesto de que la teoría es eficaz; no sería posible construir esta fórmula sin dicho supuesto.
Para cada número n y cada fórmula F ( y ) , donde y es una variable libre, definimos q ( n , G ( F )) , una relación entre dos números n y G ( F ) , tal que corresponde al enunciado " n no es el número de Gödel de una demostración de F ( G ( F )) ". Aquí, F ( G ( F )) puede entenderse como F con su propio número de Gödel como argumento.
Nótese que q toma como argumento G ( F ) , el número de Gödel de F . Para demostrar q ( n , G ( F )) , o ¬ q ( n , G ( F )) , es necesario realizar operaciones de teoría de números en G ( F ) que reflejen los siguientes pasos: decodificar el número G ( F ) en la fórmula F , reemplazar todas las ocurrencias de y en F con el número G ( F ) , y luego calcular el número de Gödel de la fórmula resultante F ( G ( F )) .
Nótese que para cada número específico n y fórmula F ( y ), q ( n , G ( F )) es una relación aritmética sencilla (aunque complicada) entre dos números n y G ( F ) , basada en la relación PF definida anteriormente. Además, q ( n , G ( F )) es demostrable si la lista finita de fórmulas codificadas por n no es una prueba de F ( G ( F )) , y ¬ q ( n , G ( F )) es demostrable si la lista finita de fórmulas codificadas por n es una prueba de F ( G ( F )) . Dados cualesquiera números n y G ( F ) , q ( n , G ( F )) o ¬ q ( n , G ( F )) (pero no ambos) son demostrables.
Cualquier prueba de F ( G ( F )) puede ser codificada por un número de Gödel n , tal que q ( n , G ( F )) no se cumple. Si q ( n , G ( F )) se cumple para todos los números naturales n , entonces no hay prueba de F ( G ( F )) . En otras palabras, ∀ y q ( y , G ( F )) , una fórmula sobre números naturales, corresponde a "no hay prueba de F ( G ( F )) ".
Definimos ahora la fórmula P ( x ) = ∀ y q ( y , x ) , donde x es una variable libre. La fórmula P tiene un número de Gödel G ( P ) como toda fórmula.
Esta fórmula tiene una variable libre x . Supongamos que la reemplazamos por G ( F ) , el número de Gödel de una fórmula F ( z ) , donde z es una variable libre. Entonces, P ( G ( F )) = ∀ y q ( y , G ( F )) corresponde a "no hay prueba de F ( G ( F )) ", como hemos visto.
Consideremos la fórmula P ( G ( P )) = ∀ y q ( y , G ( P )) . Esta fórmula relativa al número G ( P ) corresponde a "no hay prueba de P ( G ( P )) ". Tenemos aquí la característica autorreferencial que es crucial para la prueba: una fórmula de la teoría formal que de alguna manera se relaciona con su propia demostrabilidad dentro de esa teoría formal. Muy informalmente, P ( G ( P )) dice: "No soy demostrable".
Ahora demostraremos que ni la fórmula P ( G ( P )) , ni su negación ¬ P ( G ( P )) , son demostrables.
Supóngase que P ( G ( P )) = ∀ y q ( y , G ( P )) es demostrable. Sea n el número de Gödel de una demostración de P ( G ( P )) . Entonces, como se vio anteriormente, la fórmula ¬ q ( n , G ( P )) es demostrable. Probar tanto ¬ q ( n , G ( P )) como ∀ y q ( y , G ( P )) viola la consistencia de la teoría formal. Por lo tanto, concluimos que P ( G ( P )) no es demostrable.
Consideremos cualquier número n . Supongamos que ¬ q ( n , G ( P )) es demostrable. Entonces, n debe ser el número de Gödel de una prueba de P ( G ( P )) . Pero acabamos de demostrar que P ( G ( P )) no es demostrable. Puesto que tanto q ( n , G ( P )) como ¬ q ( n , G ( P )) deben ser demostrables, concluimos que, para todos los números naturales n , q ( n , G ( P )) es demostrable.
Supóngase que la negación de P ( G ( P )) , ¬ P ( G ( P )) = ∃ x ¬ q ( x , G ( P )) , es demostrable. Probar tanto ∃ x ¬ q ( x , G ( P )) como q ( n , G ( P )) , para todos los números naturales n , viola la ω-consistencia de la teoría formal. Por lo tanto, si la teoría es ω-consistente , ¬ P ( G ( P )) no es demostrable.
Hemos esbozado una prueba que muestra que:
Para cualquier teoría formal, recursivamente enumerable (es decir, efectivamente generada) de la aritmética de Peano ,
La prueba del teorema de incompletitud de Gödel que acabamos de esbozar es de tipo teórico-demostrativo (también llamada sintáctica ) en el sentido de que muestra que si existen ciertas pruebas (una prueba de P ( G ( P )) o su negación), entonces pueden manipularse para producir una prueba de una contradicción. Esto no hace referencia a si P ( G ( P )) es "verdadero", sino solo a si es demostrable. La verdad es un concepto teórico-modelo o semántico , y no es equivalente a la demostrabilidad excepto en casos especiales.
Analizando con más detalle la situación de la prueba anterior, es posible llegar a una conclusión sobre la verdad de P ( G ( P )) en el modelo estándar de números naturales. Como se acaba de ver, q ( n , G ( P )) es demostrable para cada número natural n , y por lo tanto es verdadera en el modelo . Por lo tanto, dentro de este modelo,
Esto es a lo que suele referirse la afirmación " P ( G ( P )) es verdadera": la oración es verdadera en el modelo pretendido. Sin embargo, no es verdadera en todos los modelos: si lo fuera, entonces, por el teorema de completitud de Gödel , sería demostrable, lo que, como acabamos de ver, no es el caso.
George Boolos (1989) simplificó enormemente la prueba del Primer Teorema, si uno acepta que el teorema es equivalente a:
"No existe ningún algoritmo M cuyo resultado contenga todas las oraciones aritméticas verdaderas y ninguna falsa".
"Aritmética" se refiere a la aritmética de Peano o Robinson , pero la prueba no invoca detalles específicos de ninguna de ellas, asumiendo tácitamente que estos sistemas permiten que '<' y '×' tengan sus significados habituales. Boolos demuestra el teorema en aproximadamente dos páginas. Su prueba emplea el lenguaje de la lógica de primer orden , pero no invoca hechos sobre los conectivos o cuantificadores . El dominio del discurso son los números naturales . La oración de Gödel se basa en la paradoja de Berry .
Sea [ n ] la abreviatura de n aplicaciones sucesivas de la función sucesora , comenzando desde 0 . Boolos afirma entonces (solo se esbozan los detalles) que existe un predicado definido Cxz que resulta verdadero si y solo si una fórmula aritmética que contiene z símbolos nombra el número x . Este esbozo de prueba contiene la única mención de la numeración de Gödel ; Boolos simplemente supone que cada fórmula puede numerarse de esa manera. Aquí, una fórmula F nombra el número n si y solo si lo siguiente es demostrable:
Boolos luego define los predicados relacionados:
Fx formaliza la paradoja de Berry. El resto de la prueba, que requiere sólo 12 líneas de texto, muestra que la oración ∀ x ( Fx ↔( x = [ n ])) es verdadera para algún número n , pero ningún algoritmo M la identificará como verdadera. Por lo tanto, en aritmética, la verdad supera a la prueba. QED.
Los predicados anteriores contienen los únicos cuantificadores existenciales que aparecen en toda la prueba. Los '<' y '×' que aparecen en estos predicados son las únicas nociones aritméticas definidas que requiere la prueba. La prueba no menciona en ningún lado funciones recursivas ni ningún hecho de la teoría de números , y Boolos afirma que su prueba prescinde de la diagonalización . Para más información sobre esta prueba, véase la paradoja de Berry .
