EL TEOREMA DE GÖDEL

Una parte del argumento de Gödel es muy complicada y realmente no es necesario que la examinemos. Pero la idea central era sencilla, bella y profunda; podremos apreciar esta idea. La parte complicada (que también contiene mucho ingenio) consistía en mostrar en detalle cómo se pueden codificar realmente las reglas de inferencia individuales del sistema formal, y también el uso de sus diversos axiomas, en operaciones aritméticas. (¡Sin embargo, un aspecto de la parte profunda era hacer comprender que esto era algo fructífero!).

Para llevar a cabo esta codificación necesitamos encontrar alguna forma conveniente de etiquetar las proposiciones mediante números naturales. Una forma consistiría simplemente en utilizar algún tipo de orden «alfabético» para las cadenas de símbolos del sistema formal con una longitud específica, dentro de una ordenación global según la longitud de la cadena. (Así, podrían ordenarse alfabéticamente las cadenas de longitud uno, seguidas de las cadenas de longitud dos, alfabéticamente ordenadas, seguidas de las cadenas de longitud tres, etc.). Esto se llama orden lexicográfico.^[4.5] En realidad, Gödel utilizó originalmente un sistema de numeración más complicado, pero las diferencias no son importantes en este momento.

Nos interesaremos especialmente en las funciones proposicionales que dependen de una sola variable, como es el caso de la G(w) anterior. Sea P_n(w) la n-ésima de estas funciones proposicionales (en el orden elegido para las cadenas de símbolos) aplicada a w.

(Podemos permitirnos, si queremos, que nuestra numeración sea un poco «chapucera», de forma que algunas de estas expresiones no sean sintácticamente correctas. Esto hace la codificación aritmética mucho más fácil que si tratáramos de omitir todas las expresiones sintácticamente incorrectas).

Si P_n(w) es sintácticamente correcta será algún enunciado aritmético perfectamente bien definido que concierne a los dos números naturales n y w. Cuál sea exactamente este enunciado dependerá de los detalles del sistema de numeración específico que hayamos elegido. Eso pertenece a la parte complicada del argumento y no nos interesa aquí.

Las cadenas de proposiciones que constituyen una demostración de algún teorema en el sistema pueden ser etiquetadas también mediante números naturales utilizando el esquema de ordenación escogido. Denotemos mediante

Π_n

la n-ésima demostración. (De nuevo, podemos utilizar una numeración «chapucera» en la que para algunos valores de n la expresión «Π_n» no es sintácticamente correcta y por lo tanto no demuestra ningún teorema).

Consideremos ahora la siguiente función proposicional, que depende del número natural w:

~∃x [Π_x demuestra P_w(w)].

El enunciado dentro del paréntesis cuadrado se da parcialmente en palabras, pero es un enunciado perfecta y exactamente bien definido. Afirma que la x-ésima demostración es realmente una demostración de la proposición que constituye P_w( ) aplicada al propio valor w. El cuantificador existencial negado, fuera del paréntesis, sirve para eliminar una de las variables («no existe un x tal que…»), de modo que nos queda una función proposicional aritmética que sólo depende de una variable w. La expresión global afirma que no existe demostración de P_w(w). Supondré que está estructurada de una manera sintácticamente correcta (incluso si P_w(w) no lo está —en cuyo caso el enunciado sería verdadero—, puesto que no puede haber demostración de una expresión sintácticamente incorrecta). De hecho, debido a las traducciones a la aritmética que se supone hemos llevado a cabo, el enunciado de arriba es en realidad un enunciado aritmético relativo al número natural w (siendo la parte contenida entre paréntesis cuadrados un enunciado aritmético bien definido relativo a dos números naturales x y w).

No resulta obvio que los enunciados puedan ser realmente codificados en la aritmética, aunque pueden serlo. Mostrar que tales enunciados pueden ser realmente codificados de esta forma es el principal «trabajo duro» incluido en la parte complicada del argumento de Gödel. Al igual que antes, cuál sea exactamente el enunciado aritmético dependerá de los detalles de numerosos sistemas, y dependerá en gran medida de la estructura detallada de los axiomas y reglas de nuestro sistema formal. Puesto que todo eso pertenece a la parte complicada, no nos interesaremos ahora por los detalles.

Hemos numerado todas las funciones proposicionales que dependen de una sola variable, de modo que la que acabamos de escribir debe tener asignado un número. Escribamos este número como k. Nuestra función proposicional es la k-ésima de la lista. Por consiguiente

~∃x [Π_x demuestra P_w(w)] = P_k(w)

Examinemos ahora esta función para el valor w particular: w = k. Tenemos

~∃x [Π_x demuestra P_k(k)] = P_k(k).

La proposición especifica P_k(k) es un enunciado aritmético perfectamente bien definido (sintácticamente correcto). ¿Tiene una demostración dentro de nuestro sistema formal? ¿Tiene demostración su negación ~P_k(k)? La respuesta a ambas preguntas debe ser «no». Podemos verlo examinando el significado subyacente en el procedimiento de Gödel. Aunque P_k(k) es sólo una proposición aritmética, la hemos construido de modo que afirma lo que se ha escrito en el lado izquierdo: «no existe demostración, dentro del sistema, de la proposición P_k(k)».

Si hemos sido cuidadosos al establecer nuestros axiomas y reglas de inferencia, y suponiendo que hayamos hecho bien nuestra numeración, entonces no puede haber ninguna demostración de esta P_k(k) dentro del sistema. En efecto, si hubiera tal demostración, el significado del enunciado que P_k(k) realmente afirma, a saber, que no existe demostración, sería falso, de modo que P_k(k) tendría que ser falsa como proposición aritmética. ¡Nuestro sistema formal no debería estar tan mal construido como para permitir que se demuestren proposiciones falsas! Por consiguiente, debe ser el caso que, de hecho, no hay demostración de P_k(k). Pero esto es precisamente lo que P_k(k) está tratando de decirnos. Por lo tanto, lo que afirma P_k(k) debe ser un enunciado verdadero, de modo que P_k(k) debe ser verdadera como proposición aritmética. Entonces ¡hemos encontrado una proposición verdadera que no tiene demostración dentro del sistema!

¿Qué sucede con su negación ~P_k(k)? Se concluye que haríamos mejor en no encontrar tampoco una demostración de esta otra. Acabamos de establecer que ~P_k(k) debe ser falsa (puesto que P_k(k) es verdadera), ¡pero se suponía que no podíamos demostrar proposiciones falsas dentro del sistema! Así, ni P_k(k) ni ~P_k(k) son demostrables dentro de nuestro sistema formal. Esto establece el teorema de Gödel.