Rosabelen Blog: Gödel

Mostrando entradas con la etiqueta Gödel. Mostrar todas las entradas

Adenda a "¿La mente humana?"

Con respecto a la entrada ¿La mente humana?, hace unos días recibí un mensaje privado de Hernán Echegoyemberry en el que, y se lo agradezco, me menciona que había allí un error de tipeo que cambiaba completamente el sentido de una frase; error que, merced a esa observación, ya fue corregido.

La frase en cuestión dice: "el teorema de Gödel implica que hay problemas que no son resolubles algorítmicamente". Ahora bien, en referencia a ella, en su mensaje privado Hernán agrega: eso aplica más para el teorema de Turing pero se entiende el punto. Quiero aprovechar este comentario de Hernán para hacer un agregado a la entrada original, un agregado que en aquel momento preferí omitir para no desviarme del tema central.

Es verdad que se le atribuye a Alan Turing (con justicia hay que decir) el descubrimiento de que existen problemas matemáticos que no son resolubles algorítmicamente; concretamente Turing probó que el Halting Problem es irresoluble. Pero no es menos cierto que la existencia de problemas matemáticos que no son resolubles algorítmicamente también se deduce (como dije en la entrada original) del teorema de incompletitud de Gödel. Veamos...

El teorema de Gödel dice que no es posible dar un sistema de axiomas para la Aritmética que sea al mismo tiempo consistente, recursivo y completo. "Consistente" significa que no existe un enunciado P tal que tanto P como su negación sean demostrables. "Recursivo" significa que existe un algoritmo que reconoce si un enunciado es, o no, un axioma. "Completo" es que para todo enunciado P, o bien él, o bien su negación, es demostrable.

Supongamos ahora que propongo como sistema de axiomas a todos los enunciados aritméticos verdaderos. No es difícil probar que este sistema es consistente y completo (ambas características se deducen del hecho de que todos los enunciados verdaderos, y sólo los verdaderos, resultan ser demostrables). Por el teorema de Gödel, entonces, el sistema no puede ser recursivo. En otras palabras, no existe un algoritmo que permita decidir si un enunciado es, o no, un axioma; es decir: no existe un algoritmo que permita decidir si un enunciado aritmético es, o no, verdadero. El problema de determinar la verdad de un enunciado aritmético no es resoluble algorítmicamente.

Ahora bien, si Gödel demostró su teorema en 1931 y el trabajo de Turing es de 1937 ¿por qué se le atribuye a Turing el descubrimiento? Porque en su artículo Gödel propone una definición posible de la idea de algoritmo "aritmético", pero reconoce que no está claro que su definición abarque todos los algoritmos posibles (de hecho, según se vio después, no los abarca). El gran mérito de Turing fue el haber dado una definición (una "modelización matemática", según la idea de la entrada anterior) de la idea de algoritmo lo suficientemente amplia como para abarcar (hasta donde se sabe) a todos los algoritmos posible. Es por eso que, recién después del trabajo de Turing pudo darse por demostrado la existencia de problemas no resolubles algorítmicamente; y fue asimismo después del trabajo de Turing (según Gödel reconoció en una posdata a su artículo) que pudo establecerse el alcance real del teorema de Gödel.

Un último comentario: así como la definición que dio Gödel para la idea de algoritmo resultó ser insuficiente, en el sentido de que hay algoritmos que la definición de Gödel no abarca, del mismo modo nada asegura que no haya algoritmos que queden "fuera" de la definición de Turing, aunque hasta el día de hoy nadie ha sido capaz de dar ni siquiera la insinuación de un ejemplo concreto.

¿La mente humana?

El año pasado Miguel Ángel, administrador del excelente y bien conocido blog Gaussianos, tuvo la gentileza de invitarme a escribir allí una entrada sobre el teorema de Gödel, la que puede leerse haciendo clic aquí. En los comentarios a esa entrada (y también en los comentarios a esta otra) surgió la cuestión de si el teorema de Gödel permite, o no, demostrar que existe una diferencia esencial entre la mente humana y una computadora. En otras palabras ¿la mente humana es "computable", o no?

En esos comentarios sostuve la postura de que el teorema de Gödel no permite demostrar que la mente humana no es computable (a pesar de que lo contrario ha sido afirmado muchas veces por pensadores muy respetables). Algunos de mis interlocutores en aquel intercambio entendieron que yo estaba afirmando que no hay una diferencia esencial entre mente y computadora, cuando en realidad simplemente estaba afirmado que el teorema de Gödel no permite demostrar que esa diferencia existe. (En el mismo sentido, afirmar que el teorema de Gödel no permite demostrar la conjetura de Goldbach no es lo mismo que afirmar que la conjetura de Goldbach sea falsa).

Ahora bien... ¿por qué el teorema de Gödel no permite demostrar que la mente humana no es computable?

El teorema de Gódel es un teorema matemático que habla de entes matemáticos (ciertos conjuntos de enunciados) y que dice que si esos objetos cumplen ciertas hipótesis específicas entonces esos entes verifican ciertas propiedades claramente enunciadas. El punto a destacar aquí es que el teorema de Gödel es un teorema matemático que habla de ciertos objetos matemáticos. Por lo tanto, para que el teorema sea aplicable a una situación cualquiera, ésta debe haber sido, previamente, modelizada matemáticamente.

El teorema de Gódel, por ejemplo, permite demostrar que existen problemas matemáticos bien definidos que no puede ser resueltos algorítmicamente. ¿Por qué? Porque existe una definición matemática del concepto de algoritmo: matemáticamente, un "algoritmo" es una "máquina de Turing". En otras palabras, las máquinas de Turing modelizan matemáticamente el concepto de algoritmo. Si se acepta que este modelo es correcto (es decir, si se acepta que verdaderamente el concepto intuitivo de algoritmo está bien representado por la idea de máquina de Turing) entonces debe aceptarse que el teorema de Gödel implica que hay problemas que no son resolubles algorítmicamente Si hubiera algoritmos no representables por máquinas de Turing entonces esa conclusión no estaría justificada.

Creo que ahora puede verse hacia dónde voy... Para que el teorema de Gödel pueda decir algo acerca de la mente humana debería existir, previamente, una definición matemática (un modelo matemático) de la mente. Debería haber una definición que nos diga (o nos permita demostrar) qué puede hacer, o qué no puede hacer la menta humana. Todas las supuestas demostraciones de que mente humana no es computable suelen caer en la falacia de atribuirle a la mente, sin ninguna justificación, aquellas propiedades que el razonamiento necesita que verifique. (El razonamiento típico dice: un algoritmo no puede hacer H, pero la mente sí, luego mente y computadora son diferente. Pero.. ¿por qué la mente puede hacer H? Respuesta: porque sí.)

¿Cómo podría definirse matemáticamente la mente? Por ejemplo, podríamos decir que la mente es una máquina de Turing con un oráculo que resuelve el halting problem. Desde luego, si aceptáramos esta definición entonces podríamos deducir inmediatamente que existe una diferencia esencial entre mente y computadora, pero... ¿esa que hemos dado es una definición aceptable de la mente? La respuesta, creo, es "claramente no". Y mientras no haya una definición matemática, aceptable, del concepto de "mente humana" el teorema de Gödel no podrá (legítimamente, al menos) decir nada al respecto.

"Dénme un punto de apoyo y moveré el mundo", dicen que dijo Arquímedes. Parafraseando a Arquímedes, Gödel podría haber dicho; "Dénme una definición matemática de la mente y les diré si es computable o no".

Algunos conceptos relacionados con el Teorema de Gödel

1. El Programa de Hilbert

Los teoremas de Gödel, publicados en 1931, nacieron en el contexto de una larga polémica sobre los fundamentos de la matemática cuyos orígenes se remontan a la década de 1870 con el descubrimiento por parte de Georg Cantor de los cardinales transfinitos, y que se había intensificado a partir de 1902 tras el hallazgo de la paradoja de Russell.

El campo de batalla de esta polémica era nada menos que el infinito. La escuela constructivista, encabezada por L.E.J. Brouwer, sostenía que la introducción del infinito en acto en matemática era absurda e injustificada y que la teoría de los transfinitos de Cantor era solamente un juego de palabras sin sentido. Los únicos objetos matemáticos válidos, sostenía esta escuela, son aquellos que se pueden construir mecánicamente en una cantidad finita de pasos.

Hacia 1920, con el objetivo fundamental de defender a la teoría de Cantor (y bajo el lema “Del paraíso que Cantor creó para nosotros nadie podrá expulsarnos”), interviene en la polémica el matemático alemán David Hilbert quien, en una serie de artículos publicados a lo largo de siguientes diez años, propone el que hoy es conocido como el Programa de Hilbert y que, en esencia, quitaba la exigencia de finitud y de constructividad de los objetos matemáticos para desplazarla a los razonamientos matemáticos.

Con más precisión, Hilbert proponía la creación de una nueva ciencia a la que él llamaba metamatemática. Esta ciencia tendría como objetivo el verificar la validez de los razonamientos matemáticos. Para evitar polémicas, y para asegurarse de que no surgieran paradojas, esta ciencia sería puramente sintáctica: la metamatemática trataría a los enunciados y a los razonamientos matemáticos como si fueran simples secuencias de símbolos sin significado a los que manipularía mecánicamente.

Se ha dicho en muchos textos de divulgación que el Programa de Hilbert proponía reducir la matemática a un juego de símbolos carente de significado; se ha dicho también que para Hilbert el concepto de "verdad matemática" carecía de sentido. Nada de esto es correcto. Hilbert era ante todo un investigador matemático, el mejor de su tiempo, por lo que es inimaginable que pudiera pensar de esa manera. Hilbert atribuía la reducción a simples manipulaciones de símbolos a la metamatemática, no a la matemática en sí. Los matemáticos, para Hilbert, seguirían trabajando como siempre han hecho a nivel semántico, un nivel lleno de significados. El matemático, en el día a día, trabaja, crea, conjetura y demuestra, como si lo que tuviera entre manos fueran objetos reales. La metamatemática, según la idea de Hilbert, trabajaría a nivel sintáctico y sólo proveería los métodos para verificar si los razonamientos que el matemático ha hecho son correctos.
En concreto, el Programa de Hilbert proponía dar un conjunto de axiomas para la aritmética que cumpliera las siguientes cuatro condiciones:

a) El sistema debía ser consistente; es decir, no debía existir un enunciado P tal que P y su negación fueran simultáneamente demostrables.
b) La validez de cualquier demostración debía ser verificable por manipulaciones mecánicas en una cantidad finita de pasos. Traducida a un lenguaje moderno, esta condición dice que debía ser posible, al menos en teoría, programar una computadora de tal modo que fuese capaz de verificar la validez de los razonamientos matemáticos,
c) Dado cualquier enunciado P, o bien él o bien su negación debía ser demostrable.
d) La consistencia de los axiomas debía ser verificable mecánicamente en una cantidad finita de pasos.

Como se ha dicho, Hilbert fue dando forma a este programa a lo largo de la década de 1920; sin embargo, en 1931 los teoremas de Gödel demostraron que esas cuatro condiciones no pueden cumplirse a la vez.

Concretamente, el primer teorema de incompletitud de Gödel dice que si se cumplen las condiciones a) y b) entonces necesariamente la condición c) falla. Por su parte, el llamado segundo teorema de incompletitud de Gödel, del que no nos ocuparemos aquí, prueba que si se cumplen las condicoiones a) y b) entonces es la condición d) la que falla.

2. La numeración de Gödel

En lo que sigue, expondremos las ideas principales de la demostración del primer teorema de Gödel. Supongamos, entonces, que se ha dado un conjunto de axiomas para la aritmética que cumple las condiciones a) y b). En realidad, a los efectos de nuestro desarrollo, y para evitar tecnicismos, supondremos que todos los axiomas propuestos son enunciados verdaderos.

Estrictamente hablando, esta última hipótesis no es necesaria para demostrar el primer teorema de Gödel, sin embargo, por una parte, es obvio que se trata de una suposición perfectamente razonable (nadie propondría seriamente basar la aritmética en axiomas falsos). Por otra parte, además, suponer que los axiomas son enunciados verdaderos implica inmediatamente que estos satisfacen la condición a); en efecto, si todos los axiomas son verdaderos entonces los teoremas que se deducen de ellos son también enunciados verdaderos. En otras palabras, es imposible demostrar un enunciado falso, por lo que, tal como pide la condición a), nunca sucederá que exista un enunciado P tal que él y su negación sean a la vez demostrables.

Como se ha dicho más arriba, supondremos también que se cumple la condición b), es decir, que la validez de toda demostración basada en los axiomas elegidos es verificable algorítmicamente en una cantidad finita de pasos.

El comienzo de la demostración del primer teorema de Gödel consiste en asignar a cada enunciado aritmético un número natural, llamado el número de Gödel de ese enunciado. Por ejemplo, al enunciado “2 es un número par” podría corresponderle el número de Gödel 23.627; o al enunciado “22 es un número primo” podría corresponderle el número de Gödel 11.705.

Debemos hacer aquí varias aclaraciones. La primera es que el enunciado “22 es un número primo” es evidentemente falso; en efecto, Gödel le asigna un número a cada enunciado aritmético, tanto a los verdaderos como a los falsos. La segunda aclaración, muy importante, es que la asignación de los números de Gödel no se hace al azar; los ejemplos mostrados más arriba son puramente hipotéticos y tienen el único objetivo de ejemplificar la idea de que a cada enunciado se le asigna un número. Estos ejemplos no deben ser tomados de ninguna manera como representativos del modo en que los números de Gödel son asignados. En realidad, antes de hacer la asignación cada enunciado debe ser traducido a un lenguaje formal estrictamente definido; sólo después de que esa traducción se ha completado el número de Gödel correspondiente al enunciado en cuestión es calculado mediante un procedimiento algorítmico rigurosamente especificado. En la práctica, de hecho, el número de Gödel de cualquier enunciado, aun de los más simples, tiene siempre una gran cantidad de cifras.

Una vez que se ha asignado un número de Gödel a cada enunciado, queda bien definido el conjunto de los números de Gödel de todos los enunciados que son demostrables a partir de los axiomas propuestos. El grueso de la demostración del primer teorema de Gödel consiste en probar que ese conjunto de números puede definirse apelando únicamente a propiedades aritméticas (que son las propiedades referidas a los números naturales que son expresables en términos de la suma, el producto y las operaciones lógicas usuales). Es decir, la propiedad lógica “Es el número de Gödel de un enunciado demostrable” puede traducirse a una propiedad puramente aritmética (aunque no siempre lo explicitemos, debe entenderse en todo momento que “demostrable” significa “demostrable a partir de los axiomas aritméticos propuestos”). Por ejemplo, podría suceder que los números de Gödel de los enunciados demostrables sean exactamente los números primos terminados en 7. Una vez más debemos aclarar que este último ejemplo es puramente hipotético y sólo tiene la intención de mostrar lo que entendemos por “propiedad aritmética”. En la práctica, la propiedad aritmética que define a los números de Gödel de los enunciados que son demostrables a partir de un cierto conjunto de axiomas es siempre muy compleja de enunciar.

Es importante destacar también que es en este punto de la demostración donde entra en juego la hipótesis b). En efecto, puede probarse que si se admiten métodos de demostración que no son verificables algorítmicamente entonces no es necesariamente cierto que la propiedad de ser el código de Gödel de un enunciado demostrable sea expresable mediante propiedades aritméticas.

3. El método de autorreferencia

Planteemos un nuevo ejemplo hipotético; imaginemos que al enunciado “23.409 es un número par” le correspondiera el número de Gödel 23.409. Podríamos entonces parafrasear este enunciado como diciendo, falsamente, que “Mi número de Gödel es par”.

Ahora bien ¿es razonable suponer que existe un enunciado que se refiera a su propio número de Gödel? En realidad sí es razonable, porque Gödel probó que, dada cualquier propiedad aritmética, como por ejemplo “Es un número par” o “Es un número primo”, siempre existe un enunciado aritmético que puede parafrasearse como diciendo que su propio número de Gödel cumple esa propiedad. Es decir, existe necesariamente un número n tal que al enunciado “n es par” le corresponde el número de Gödel n y un número m tal que al enunciado “m es primo” le corresponde el número de Gödel m. En otras palabras, Gödel mostró un método para obtener enunciados autorreferentes.

Dijimos antes que la propiedad “Es el número de Gödel de un enunciado demostrable” es traducible a una propiedad aritmética; de la misma forma, también es traducible la propiedad “No es el número de Gödel de un enunciado demostrable” (en el contexto del ejemplo hipotético dado más arriba, “No es el número de Gödel de un enunciado demostrable” equivaldría a “No es cierto que es un número primo terminado en 7”).
En consecuencia, por lo dicho más arriba, existe necesariamente un número k tal que al enunciado “k no el número de Gödel de un enunciado demostrable” (que en el ejemplo hipotético equivale a “No es cierto que k es un número primo terminado en 7”) le corresponde el número k. En otras palabras, ese enunciado dice, “Mi número de Gödel no corresponde a un enunciado demostrable” o, dicho más simplemente, el enunciado afirma “Yo no soy demostrable”. Veamos a continuación que este enunciado es verdadero, pero no es demostrable a partir de los axiomas propuestos.

Para probar que “Yo no soy demostrable” es verdadero pero no demostrable supongamos, en primer lugar, que fuera falso. En ese caso, lo que enuncia es incorrecto, por lo que sí sería demostrable. Es decir, sería falso y demostrable a la vez, pero esto es imposible porque los axiomas son enunciados verdaderos.

Entonces “Yo no soy demostrable” es necesariamente verdadero, pero entonces lo que enuncia es verdad y, por lo tanto, es verdadero y no demostrable.

Notemos que esto implica, tal como queríamos probar, que la condición c) falla. En efecto, el enunciado aritmético que expresa que “Yo no soy demostrable” no es demostrable, pero tampoco lo es su negación, ya que esta negación es un enunciado falso, y si los axiomas son enunciados verdaderos entonces ningún enunciado falso puede ser demostrable. Hemos probado así que, contradiciendo lo que pide condición c), existe siempre un enunciado P tal que ni él, ni su negación, son demostrables. De este modo, termina nuestra exposición de las ideas centrales de la demostración del primer teorema de Gödel.

4. Conclusión

El programa de Hilbert proponía que se diera un conjunto de axiomas aritméticos que cumpliera las condiciones a), b), c) y d) enunciadas más arriba. La condición a) puede parafrasearse diciendo que el sistema no debe permitir que se demuestren enunciados falsos, en otras palabras, los axiomas nunca deben conducir a una paradoja; la condición d) pide, además, que la validez de la condición a) sea verificable de un modo claro y objetivo. La condición b), por su parte, pide que también exista un método claro, objetivo y concreto para verificar la validez de los razonamientos matemáticos. La condición c), finalmente, pide esencialmente que todas las verdades aritméticas sean demostrables.

Los teoremas de Gödel prueban que estas cuatro condiciones no pueden cumplirse simultáneamente. En particular, el primer teorema demuestra que si sólo admitimos razonamientos cuya validez sea verificable objetivamente entonces siempre habrá verdades matemáticas que no podamos demostrar. En otras palabras, tenemos que elegir entre la certeza absoluta de que no cometeremos errores y la certeza absoluta de que podremos resolver todos los problemas matemáticos. Tenemos que elegir, dice Gödel, entre una de esas dos certezas porque nunca podemos tener ambas al mismo tiempo.

Sobre la indecidibilidad de la indecidibilidad

Una pequeña demostración basada en el Segundo Teorema de Gödel

Vamos a demostrar que el problema de determinar si un enunciado P es decidible con respecto a una teoría T no es resoluble algorítmicamente.

Hagamos la demostración por el absurdo. Supongamos que sí hubiera un algoritmo A que resuelve ese problema y lleguemos a una contradicción.

Sea T una teoría "que contiene suficiente aritmética" y CON un enunciado que expresa (en cierto nivel de lectura) que T es consistente. Recordemos que el Segundo Teorema de Gödel dice que si T es consistente entonces CON es indecicible con respecto a T.

Apliquemos el algoritmo A para determinar si CON es decidible con respecto a T. Si la respuesta de A es que CON es decidible, entonces T es inconsistente (por el Segundo Teorema). Si la respuesta de A es que CON es indecidible entonces T es consistente (porque sólo las teorías consistentes admiten enunciados indecidibles).

Por lo tanto, si A existiera tendríamos un algoritmo que permite determinar si una teoría es consistente, o no. Pero una consecuencia del Segundo Teorema de Gödel es que tal algoritmo no puede existir. Llegamos a un absurdo. Por lo tanto A no existe.

La autorreferencia en la demostración de Gödel (Parte 9 y última)

(A la parte 8)

Todo enunciado aritmético verdadero es demostrable

La intención principal de esta serie de entradas fue despejar algunas "preguntas frecuentes" relativas a los teoremas de Gödel. Por ejemplo: ¿Cómo es posible que un sistema axiomático sea consistente con la afirmación que dice que ese sistema no es consistente? ¿Puede ser demostrable un enunciado falso? Etc.

Como vimos, en los teoremas de Gödel hay tres niveles de análisis del lenguaje. Por un lado está el nivel sintáctico, en el que los símbolos del lenguaje se manipulan sin tomar en cuenta su posible significado (en este nivel se enuncian y demuestran los teoremas de Gödel).

Tenemos después el nivel semántico, en el que los enunciados se entienden como referidos a un cierto universo del discurso. Este universo puede ser el de los números naturales u otro universo más amplio. Este es el nivel en el que los matemáticos se mueven en su trabajo diario y es, en general, el nivel en el que nos sentimos más cómodos.

En el tercer nivel (que en el capítulo anterior di en llamar supra-aritmético), gracias a una codificación arbitrariamente definida, algunos enunciados pueden entenderse como referidos a propiedades metamatemáticas de sí mismos o de otros enunciados. Es sólo en este tercer nivel de análisis donde aparece la autorreferencia o la referencia a la consistencia de un sistema de axiomas.

La mayoría de las confusiones relativas a los teoremas de Gödel nacen de mezclar indebidamente conceptos pertenecientes a niveles diferentes. En efecto es un error mezclarlos porque, por ejemplo, tal como vimos en el capítulo anterior, hay enunciados que son equivalentes en un nivel, pero no equivalentes en otro nivel diferente.

Como dije en un capítulo anterior, la autorreferencia no es esencial para la demostración de los teoremas de Gödel. La interpretación de un enunciado como diciendo "Yo no soy demostrable" solamente ayuda a hacer más aceptable, o más creíble, la prueba de Gödel, pero no forma parte esencial de ella. ¿Por qué se hace tanto hincapié en la autorreferencia, entonces? Porque los matemáticos, créase o no, no son frías máquinas de calcular, sino seres humanos, y las demostraciones (especialmente aquellas que el matemático A hace para que el matemático B se convenza de que lo que está diciendo es cierto) no sólo deben ser correctas, sino también convincentes.

No quiero terminar esta serie de entradas sin antes referirme a otro error frecuente en relación al Primer Teorema de Gödel. Este error aparece, por ejemplo, en la novela El Tío Petros y la Conjetura de Goldbach. El Tío Petros, el protagonista de la novela, es un matemático bastante talentoso que, a una edad relativamente temprana, se obsesiona con la idea de demostrar la Conjetura de Goldbach.

Unos años después de iniciar su empresa, Petros se entera de la noticia de la demostración de Gödel y se plantea la duda de si la Conjetura de Goldbach no será una afirmación indecidible. Petros cree tener el talento suficiente como para encontrar una demostración de la Conjetura, si es que esta demostración existe. Pero ante la posibilidad de que tal vez la Conjetura sea verdadera, pero indemostrable, decide abandonar el intento de probarla y, de hecho, abandona toda investigación matemática.

Ahora bien, en los capítulos anteriores hemos hablado siempre de "demostrable con respecto a cierto sistema de axiomas" o "indecidible con respecto a tal sistema de axiomas". Pero ¿existen afirmaciones indecidible en sentido absoluto? ¿Hay verdades indemostrables? ¿Por qué digo "sistema de axiomas" y no "conjunto de axiomas?

Respondo primero a la segunda pregunta. Cuando hablamos de demostraciones, consistencia, etc. no sólo debemos tener en cuenta a los axiomas de la teoría en cuestión, sino que también debemos tener en cuenta la lógica subyacente y las reglas de inferencia. Hablo de "sistema de axiomas" como equivalente a "conjunto de axiomas + lógica subyacente + reglas de inferencia".

La lógica subyacente está formada los enunciados del lenguaje que son "universalmente válidos". Es decir, enunciados que son verdaderos cualquiera sea la interpretación que se dé a los símbolos del lenguaje. Nótese que esta definición es semántica. Un ejemplo es "P o no-P", donde P es un enunciado cualquiera. Se habla de "lógica subyacente" porque estos enunciados pueden formar parte (y, de hecho, forman parte) de cualquier razonamiento.

Si el lenguaje respeta las restricciones que comentamos en un capítulo anterior, entonces es posible dar un sistema recursivo de axiomas que permita deducir todos los enunciados universalmente válidos expresables en ese lenguaje. Este hecho, que fue probado por Gödel en 1929 (sus teoremas de incompletitud son de 1931), nos habilita a dar una definición sintáctica de la noción de "enunciado universalmente válido": son todos aquellos que se deducen, modus ponens mediante, del sistema de axiomas que Gödel dio en 1929 (o de cualquier otro equivalente a él).

Los lenguajes que respetan las restricciones antes indicadas se llaman lenguajes de primer orden. Se dice, entonces, que la lógica de primer orden es formalizable o que es recursivamente axiomatizable. Como la lógica de primer orden es recursivamente axiomatizable entonces existen chances de que una teoría expresada en un lenguaje así pueda cumplir las condiciones del Programa de HIlbert (la Aritmética no las cumple, eso probó Gödel, pero otras teorías sí pueden cumplirlas).

Aumentemos ahora la potencia del lenguaje mediante el artilugio de agregarle variables que se refieran a enunciados o a fórmulas (una fórmula es una expresión en la que hay "variables libres", que pueden ser reemplazadas por números cualesquiera, como por ejemplo "x es par").

Tenemos ahora un lenguaje de segundo orden, o de orden superior. En este tipo de lenguaje podemos decir, por ejemplo (en un lenguaje de primer orden no se puede expresar el enunciado que sigue):

"a = b si y sólo si para toda fórmula P(x), P(a) es equivalente a P(b)"

En los lenguajes de segundo orden tenemos también el concepto de "enunciados universalmente válidos" (y que constituyen la "lógica subyacente" de las teorías expresadas en esos lenguajes). Sin embargo, se puede probar que es imposible dar un conjunto recursivo de axiomas que permita demostrar todos los enunciados universalmente válidos de segundo orden.

En la lógica de segundo orden, entonces, no hay una definición sintáctica para la lógica subyacente y, por ende, el Programa de Hilbert es de plano irrealizable en teorías expresadas en lenguajes de este tipo.

Toda demostración expresada en un lenguaje de segundo orden es no-finitista, en el sentido de que la lógica subyacente no es definible sintácticamente (y no porque tenga una cantidad infinita de pasos). La regla de inferencia que se usa en las lógicas de segundo orden, y que tampoco es finitista, es la siguiente: "Q se deduce de P si para toda interpretación de los símbolos para la cual P es verdadera resulta que Q también es verdadera".

Ahora bien, si al lenguaje que dimos antes para la Aritmética le agregamos variables para los enunciados y fórmulas (y lo transformamos en un lenguaje de segundo orden) entonces es posible dar un conjunto finito de axiomas (concretamente, los Axiomas de Peano) tal que todo enunciado aritmético verdadero es demostrable a partir de ellos.

Insisto, todo enunciado aritmético verdadero es demostrable a partir de los Axiomas de Peano, si admitimos una lógica de segundo orden. (La teoría tiene indecidibles, pero no son enunciados aritméticos). En particular, si la Conjetura de Goldbach es verdadera entonces es demostrable.

Aunque es imposible prever qué tan difícil será encontrar una demostración de ella, ni tampoco será posible dar un algoritmo que verifique su corrección. De modo que el Tío Petros hizo muy mal en abandobar su búsqueda.

Termina aquí esta serie de entradas. Espero haber resuelto algunas dudas, pero, principalmente, espero haber sembrado dudas nuevas, mejores y más resistentes.

Fin

(A la parte 8)

La autorreferencia en la demostración de Gödel (Parte 8)

(A la parte 7 - A la parte 9)

La Paradoja de Gödel

El Segundo Teorema de Incompletitud de Gödel dice que, si tenemos un sistemas de axiomas como el que les han dado a Kurt y a David, entonces la afirmación de que ese sistema es consistente no puede ser demostrada ni refutada a partir de los axiomas del sistema. Es decir, esa afirmación es indecidible para el sistema.

Una consecuencia de esto es que el sistema de axiomas es consistente con la afirmación que dice ¡que el sistema de axiomas es inconsistente!. Si al sistema le agregamos la afirmación que dice "El sistema es inconsistente" igualmente seguiremos teniendo un sistema que es consistente.. ¿Cómo puede resolverse esta paradoja?

Para comenzar, observemos que nuestro lenguaje solamente permite escribir enunciados aritméticos, entonces ¿cómo puede un enunciado aritmético afirmar que un sistema de axiomas es consistente (o que es inconsistente)?

Un hecho que es fácil de probar en los cursos de Lógica es que si un sistema de axiomas es inconsistente entonces todo enunciado es demostrable a partir de él. Por lo tanto, para decir que un sistema es consistente es suficiente con afirmar que existe algún enunciado que no es demostrable.

Volvamos a la codificación de Kurt. Recordemos que, según ella, los enunciados demostrables (para el sistema de axiomas específico que nos han dado) son exactamente aquellos cuyo código es un número primo que se puede escribir como suma o resta de tres primos consecutivos.

Por lo tanto, según la codificación de Kurt, un modo de afirmar que el sistema es consistente es decir que:

CONS(1): "Existe algún primo que no es suma o resta de tres primos consecutivos."

(El enunciado, como siempre, debe traducirse al lenguaje formal.) Es interesante observar que, según la codificación de David, este enunciado CONS no dice nada acerca de la consistencia o inconsistencia del sistema.

Ahora bien, tomemos un enunciado específico P cualquiera. Si el sistema es inconsistente entonces, por lo dicho más arriba, tanto P como no-P son ambos demostrables. Si el sistema es consistente, en cambio, al menos uno de los dos enunciados (P o su negación) no será demostrable. Es decir, dado el enunciado específico P, el sistema es consistente si y sólo si P o no-P (al menos uno de ambos) no es demostrable.

Supongamos que, según la codificación de Kurt, la negación del enunciado de código 29 sea el enunciado de código 101. Por lo tanto, el siguiente enunciado también nos muestra una forma de afirmar que el sistema es consistente:

CONS(2): "29 o 101, al menos uno de ambos, no puede escribirse como suma o resta de tres primos consecutivos."

Por otra parte, como ya sabemos, el sistema permite demostrar todos los enunciados finitistas verdaderos. En particular, permite demostrar el enunciado "no-(1 + 1 = 1)". Por lo tanto, el sistema es consistente si y sólo si el enunciado "1 + 1 = 1" no es demostrable. Supongamos que a este último enunciado le corresponde, según Kurt, el número 2. Tenemos entonces otra forma de afirmar que el sistema es consistente:

CONS(3): "2 no se puede escribir como suma o resta de tres primos consecutivos."

Tomemos los tres enunciados:

CONS(1): "Existe algún primo que no es suma o resta de tres primos consecutivos."

CONS(2): "29 o 101, al menos uno de ambos, no puede escribirse como suma o resta de tres primos consecutivos."

CONS(3): "2 no se puede escribir como suma o resta de tres primos consecutivos."

¿Estos tres enunciados son equivalentes? Estos quiere decir: ¿tomando a uno cualquiera de ellos como premisa, podemos deducir los otros dos? Sintácticamente, la respuesta es no. El segundo o el tercer enunciado permite deducir el primero, pero del primero no se deduce ninguna de los otos dos. Además, del segundo no se deduce el tercero, ni viceversa.

¿Qué sucede desde el punto de vista semántico? En este caso el universo del discurso debe ser el de los números naturales (ya que estamos pensando en términos de códigos) y es claro que, semánticamente, a nivel aritmético, los enunciados tampoco son equivalentes.

Sin embargo, los tres enunciados equivalen a: "El sistema es consistente" ¡y si los tres equivalen a una misma afirmación entonces son equivalentes entre sí! Vuelvo a preguntar: ¿cómo se resuelve esta paradoja?

La respuesta es la misma que dimos antes al hablar de la autorreferencia. CONS(1), CONS(2) y CONS(3) son enunciados aritméticos. La interpretación de su significado como refiriéndose a la consistencia de un sistema de axiomas es puramente extramatemática (supra-aritmética podríamos decir) y depende de la elección de una codificación específica (elección que es ajena a la Aritmética).

La negación de CONS(1) es (debe traducirse al lenguaje formal): "Todo primo es suma o resta de tres primos consecutivos". El Segundo Teorema de Gödel dice que el sistema de axiomas es consistente con ese enunciado. La consistencia, como ya dijimos, es un concepto sintáctico y la interpretación de no-CONS(1) como "El sistema no es consistente" está en otro nivel de lenguaje (más allá de la Aritmética) por lo que no choca con la noción de consistencia. Ésa es, ni más ni menos, la resolución de la paradoja planteada al principio: la aparente paradoja surge del hecho de mezclar conceptos sintácticos, como la consistencia, con conceptos (permítaseme la palabra) supra-semánticos, como la interpretación de CONS(1) en términos de la consistencia del sistema. (1)

Una pequeña metáfora: usualmente el color rojo significa "peligro" y el verde significa "seguridad". Al mezclarlos obtenemos el color violeta (o algo así). ¿El violeta representa entonces una mezcla entre peligro y seguridad? ¿violeta = seguligro? ¿violeta = peliguro? Es obvio que la pregunta carece de sentido y solamente surge de poner al mismo nivel la mezcla de colores (aspecto físico o sintáctico) con la interpretación que, culturalmente, le damos a esos colores (aspecto supra-cromático). De la misma forma, la paradoja de Gödel surge de mezclar conceptos que están en niveles de análisis muy diferentes.

Continuará...

Nota:

(1) Si nos adentramos en ese nivel supra-semántico y vemos a CONS(1) como la afirmación de que el sistema es consistente, entonces CONS(1) es un enunciado verdadero pero no demostrable en el sistema. Como el sistema permite demostrar todos los enunciados finitistas verdaderos entonces obtenemos la conclusión de que el hecho de que el sistema sea consistente no puede ser verificado mecánicamente en una cantidad finita de pasos. Esto demuestra la imposibilidad de concretar una de las exigencias del Programa de Hilbert: tener un sistema recursivo y completo para la Aritmética cuya consistencia sea verificable algorítmicamente.

(A la parte 7 - A la parte 9)

La autorreferencia en la demostración de Gödel (Parte 7)

(A la parte 6 - A la parte 8)

¿La afirmación: "La afirmación: "La afirmación: "Esta afirmación no es demostrable" es demostrable" no es demostrable" es demostrable?

Resumen de lo publicado: Kurt y David han elegido sendas codificaciones para los enunciados y para las sucesiones finitas de enunciados escritos en el lenguaje formal. Una vez hecho esto, ambos han recibido un mismo sistema de axiomas aritméticos que es recursivo y consistente y que permite demostrar todos los enunciados finitistas verdaderos. [Como decíamos en el capítulo anterior, vamos a suponer que estamos reproduciendo la demostración de Gödel para un sistema de axiomas específico]

Kurt observa que, para ese sistema de enunciados y según la codificación por él elegida, el conjunto de los códigos de los enunciados demostrables es exactamente el conjunto de todos los primos que se pueden escribir como suma o resta de tres primos consecutivos. [Obviamente, para otros sistemas de axiomas, o para otras codificaciones, la propiedad aritmética que define al conjunto de los códigos de los enunciados demostrables será diferente.]

Finalmente, siguiendo la demostración de Gödel, Kurt ha probado sintácticamente que el enunciado G: "43 es un primo que no se puede escribir como suma o resta de tres primos consecutivos" es indecidible para el sistema de axiomas que le han dado. Es decir, ni G ni su negación son demostrables a partir de esos axiomas.

Tomemos ahora la función g(x) definida de esta manera: g(x) es el x-ésimo número primo. Por ejemplo g(1) = 2, g(2) = 3, g(3) = 5, etc. Admitamos, sin demostración, que la función g(x) es definible mediante el lenguaje formal de la Aritmética. Es decir, que es posible expresar en ese lenguaje formal una propiedad, en función de la variable x, que sólo es cumplida por el x-ésimo primo. Debido a las restricciones del lenguaje formal la construcción de esta definición no es un problema trivial, sin embargo, con algo de ingenio, puede hacerse (1).

El enunciado G de Kurt equivale entonces a:

Ax (no-(43 es primo y 43 = +/- g(x) +/- g(x + 1) +/- g(x + 1 + 1)))

Donde la "A" indica "para todo" y el +/- indica que hay que hacer las ocho combinaciones posibles de sumas y restas entre g(x), g(x + 1) y g(x + 1 + 1).

Llamemos P(x) a la expresión (no-(43 es primo y 43 = +/- g(x) +/- g(x + 1) +/- g(x + 1 + 1))). Entonces, el enunciado G de Kurt tiene la forma AxP(x).

Observemos que P(1) afirma que 43 es un primo que no se puede obtener como suma o resta de los números 2, 3 y 5. Es decir, P(1) es un enunciado finitista verdadero y entonces, por hipótesis, es demostrable a partir del sistema de axiomas dado.

P(1 + 1) afirma que 43 es un primo que no se puede obtener como suma o resta de los números 3, 5 y 7. P(1 + 1) es también un enunciado finitista verdadero y, por lo tanto, es demostrable a partir del sistema dado.

De igual manera, P(1 + 1 + 1), P(1 + 1 + 1 + 1),... son todos demostrables. Sin embargo, G: AxP(x) no es demostrable. Cada instancia individual es demostrable, pero la afirmación general no lo es. En realidad, el enunciado G que construye la demostración de Gödel siempre tiene la forma AxP(x) donde P(1), P(1 + 1),... son todos demostrables, pero AxP(x) no lo es, ni tampoco su negación.

En el caso del enunciado de Kurt. la negación de G dice: "43 no es primo o puede escribirse como suma o resta de tres primos consecutivos" (en realidad la negación de G es una traducción al lenguaje formal de esta afirmación). Ahora bien, como G es indecidible, podemos perfectamente agregar axiomas al sistema original de Kurt de tal modo que el sistema así ampliado, sin dejar de ser recursivo y consistente, permita demostrar no-G. [Una forma simple y directa de lograr esto es agregar como axioma al propio enunciado no-G.]

¡Un momento! Pero no-G es falso... ¿Cómo puede ser demostrable? ¿A la demostración de no-G le corresponde como código un número "no estándar"?

Respondo primero a la segunda pregunta. Como he insistido en decir, la codificación estaba ya definida desde antes de que nos dieran el sistema de axiomas. Esa codificación le asigna a cada sucesión finita de enunciados un número natural "común y corriente". La demostración de no-G a partir del sistema de axiomas ampliado es, en particular, una sucesión finita de enunciados y, como tal, le corresponde como código un número natural. [Si no-G es un axioma, la demostración de no-G consta, como único enunciado, del propio no-G.]

En cuanto a la primera pregunta, ya vimos en un capítulo anterior que el concepto de "demostrable" o "no demostrable" no tiene, en principio, ninguna relación con el de "falso" o "verdadero". No hay contradicción en el hecho de que un enunciado "falso" sea "demostrable" para algún sistema de axiomas, aun siendo éste consistente.

Por otra parte, para calmar la ansiedad semántica, podemos decir que no-G es "falso" solamente si entendemos que se refiere al universo de los números naturales. Según un famoso teorema lógico, si un sistema de axiomas es consistente entonces existe un universo del discurso en el que sus enunciados son "verdaderos". Por lo que no-G es verdadero en algún universo diferente del de los números naturales. [Cuando el sistema dado es el de los axiomas de Peano, a estos universos alternativos se los suele llamar "modelos no estándar" de la Aritmética, de allí la referencia anterior a "números no estándar".] Pero estas son consideraciones semánticas ajenas a la demostración de Gödel. (2)

Continuará...

Notas:

(1) Una restricción importante del lenguaje formal es que no admite "puntos suspensivos". Así por ejemplo, la expresión (la "A" indica "para todo"):

Ax (x = 1 + 1 + ... + 1 (x veces))

no es un enunciado del lenguaje formal. En cambio (la "E" indica "existe"):

Ex (x = 1 + 1 + ... + 1 (10 veces))

aunque, estrictamente hablando, tampoco es un enunciado, sí puede aceptarse como la abreviatura de:

Ex (x = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1)

que, definitivamente, sí es un enunciado escrito en el lenguaje formal.

(2) Un pequeño ejemplo: tomemos el enunciado Ex (1 + 1 = (1 + x)(1 - x)). Si consideramos el universo de los números naturales entonces el enunciado es "falso". Pero si a ese universo le agregamos todos los números complejos de la forma a + bi con a y b enteros, entonces, en ese universo así extendido, pasa a ser "verdadero", ya que 2 = (1 + i)(1 - i).

Una idea similar nos ayuda a entender semánticamente por qué puede suceder que P(1), P(2), P(3),... sean todos demostrables sin que AxP(x) lo sea. Puede haber un universo en el que la propiedad P valga para 1, 2, 3, 4,... pero falle en otros números, en números que no se obtienen sumando el 1 sucesivamente.

(A la parte 6 - A la parte 8)

La autorreferencia en la demostración de Gödel (Parte 6)

(A la parte 5 - A la parte 7)

"Este enunciado no es autorreferente"

- ¿Ahora sí llegamos a la autorreferencia?

- Sí, ahora sí.

Nos han dado un sistema de axiomas que es recursivo y consistente, y que permite demostrar todos los enunciados aritméticos finitistas verdaderos (1). Debemos probar que existe un enunciado G tal que ni él, ni su negación, son demostrables a partir de esos axiomas. [Como decía en el capítulo anterior, vamos a suponer que estamos reproduciendo la demostración de Gödel para un sistema de axiomas específico.]

Recordemos que, inclusive antes de que nos dieran los axiomas, ya habíamos establecido una codificación, es decir una función que que a a cada enunciado y a cada sucesión de enunciados le asigna un número natural. (Ésa fue la primera parte de la demostración de Gödel.)

Con fines didácticos, vamos a imaginar que hay dos matemáticos, a los que llamaremos Kurt y David, que están estudiando la demostración de Gödel. Kurt ha elegido la misma codificación que nosotros (cuyos detalles técnicos no hemos dado), mientras que David, de puro testarudo, ha elegido una codificación completamente diferente.

Vamos a suponer que en la codificación de Kurt (que es también la nuestra) a los enunciados les corresponden siempre números primos (2). Más exactamente, supondremos que para la codificación de Kurt vale que "n es el código de un enunciado si y sólo si n es primo". Para la codificación de David la situación es completamente diferente y en ella ningún enunciado tiene como código un número primo (esto último sucede, por ejemplo, en la codificación original de Gödel).

Una vez que tenemos los axiomas, queda perfectamente establecido cuál es el conjunto de los enunciados que son demostrables a partir de ellos (y que incluye, entre otros, a los propios axiomas). También queda perfectamente establecido cuál es el conjunto de los códigos de esos enunciados demostrables (que es, por supuesto, un conjunto de números naturales).

Observemos que tanto para Kurt como para David el conjunto de los enunciados demostrables es exactamente el mismo. En cambio, ambos disienten en cuál es el conjunto de los códigos que corresponden a esos enunciados, ya que difieren en cuanto a qué número se le asigna a cada enunciado.

La segunda parte de la demostración de Gödel consiste en probar que, no importa cuál sea la codificación elegida, ni cuál sea el sistema de axiomas dado (siempre que se cumplan las hipótesis mencionadas en el capítulo anterior), existe una propiedad aritmética específica, expresable en el lenguaje formal, que define al conjunto formado por los códigos de los enunciados demostrables.

Por supuesto, Kurt y David diferirán en cuál es la propiedad que define a sus respectivos conjuntos de códigos (ya que ambos "ven" conjuntos de códigos diferentes), pero ambos serán capaces de describirlos en términos de propiedades aritméticas específicas (3).

Normalmente esa propiedad aritmética es terriblemente compleja de expresar, yo diría que en realidad es "humanamente imposible" de expresar con todo detalle. Por ese motivo, las exposiciones de la demostración de Gödel suelen decir que la propiedad en cuestión es, simplemente, la de "Ser el código de un enunciado demostrable" (o, más brevemente, la de "Ser demostrable").

Pero son precisamente esas "abreviaturas" la que suelen llevar a las confusiones que aquí tratamos de disipar. De modo que haremos uso, una vez más, de nuestra imaginación y supondremos que para Kurt el conjunto de de los códigos de los enunciados demostrables es exactamente el conjunto de todos los primos que se pueden escribir como suma o resta de tres primos consecutivos (4). [Queda como tarea para el lector interesado el verificar que esta propiedad puede expresarse en el lenguaje formal.]

Por ejemplo, 3 - 5 + 7 = 5, por lo que el número 5 es (para Kurt) el código de un enunciado demostrable; lo mismo sucede con el 13, que es -5 + 7 + 11. El 2, en cambio, no puede escribirse como suma o resta de tres primos consecutivos, por lo que 2 es el código de un enunciado que no es demostrable (siempre entendemos "demostrable a partir de los axiomas dados").

La tercera parte de la demostración del Primer Teorema de Gödel consiste en probar que existe un número n tal que el enunciado "n es un primo que no se puede escribir como suma o resta de tres primos consecutivos" (en alguna de las posibles traducciones al lenguaje formal) tiene como código, precisamente, al número n. Imaginemos que ese número n es el 43 (que, en efecto no se puede escribir como suma o resta de tres primos consecutivos).

En resumen, Kurt encuentra que el enunciado (en una de sus traducciones al lenguaje formal): "43 es primo y no se puede escribir como suma o resta de tres primos consecutivos" tiene código 43. Éste es el famoso enunciado indecidible G que construye la demostración de Gödel.

(Observemos que, por su parte, David ha encontrado un enunciado G completamente diferente. Cada codificación genera un enunciado indecidible diferente.)

¿El enunciado G: "43 es primo y no se puede escribir como suma o resta de tres primos consecutivos" es autorreferente?

Desde el punto de vista de Kurt, "43 es primo y no se puede escribir como suma o resta de tres primos consecutivos" equivale (¡semánticamente!) a la afirmación "43 es el código de un enunciado que no es demostrable". Y como a ese enunciado le corresponde el código 43 entonces equivale a: "Mi código no es el de un enunciado demostrable" o, como suele decirse, "Yo no coy demostrable". Para Kurt, sí es autorreferente.

¿Cómo ve David la situación? Para él, "43 es primo y no se puede escribir como suma o resta de tres primos consecutivos" no es autorreferente, porque su código (sea cual fuere) seguro que no es el número 43. El enunciado no habla de su código, dino de un número cualquiera. Más aún, 43, para David, ni siquiera es el código de un enunciado y "Ser la suma o resta de tres primos" es una propiedad aritmética que carece de toda relevancia metamatemática.

Para Kurt, su enunciado G es autorreferente, pero para David no lo es. en realidad, ningún enunciado aritmético es esencialmente autorreferente, todo depende de la codificación que se elija.

La cuarta, y última parte, de la demostración del Primer Teorema de Gödel consiste en probar que ni G ni su negación son demostrables a partir de los axiomas dados. Pero, ¡un momento! ¿esta demostración no depende de la autorreferencia de G? ¿Kurt puede demostrar solamente la indecidibilidad de "su" enunciado, y David solamente la del suyo? No, y no. La demostración de la indecidibilidad de G no depende de su supuesta autorreferencia. Esa demostración se basa puramente en conceptos sintácticos. Kurt demostrará que "su" G es indecidible y David podrá entender perfectamente esa demostración. De la misma manera, Kurt podrá entender perfectamente el razonamiento que haga David para probar que "su" enunciado es indecidible (para los axiomas dados).

Más aún, ni David ni Kurt necesitan siquiera saber que sus enunciados pueden ser interpretados como autorreferentes. La demostración no necesita de ese concepto.

¿Por qué se menciona tanto, entonces, la autorreferencia? Porque a nosotros, humanos, nos resulta muy incómodo manejarnos con conceptos puramente sintácticos y cuando tratamos con ellos necesitamos constantemente del uso de "muletas semánticas". La intepretación de G como "Yo no soy demostrable" se usa (como una de esas "muletas") para ayudarnos en la construcción del enunciado G. También, por qué no decirlo, se usa para que la demostración resulte más convincente (porque una demostración no sólo debe ser correcta, sino que también debe parecerlo).

La idea de la autorreferencia, con su sí-es-no-es de paradójica, suele robarse el protagonismo del teorema a la vez que oculta la naturaleza puramente sintáctica de su demostración. Insisto: el enunciado G en sí mismo no es autorreferente (sólo toma ese color cuando se lo ve a través del cristal de una determinada codificación) y la demostración de su indecidibilidad no necesita de esa supuesta autorreferencia.

Continuará...

Notas:

(1) Debido a su naturaleza metamatemática, los teoremas de Gödel se enuncian y se demuestran apelando a conceptos sintácticos. ¿Cómo es posible entonces que hablemos de "enunciados finitistas verdaderos", siendo que la noción de "verdad" es un concepto semántico. La explicación es que estamos tratando con un concepto restringido de "verdad": sólo hablamos de enunciados cuya verdad es verificable (y, de hecho, definible) mediante procedimientos sintácticos (léase algorítmicos). Tal vez sería preferible hablar de enunciados finitistas correctos.

(2) Es perfectamente posible definir una codificación que cumpla con esta condición, pero sería poco práctica si uno quisiera desarrollar con todo detalle la demostración de Gödel.

(3) No voy a desarrollar aquí los detalles técnicos de la demostración, que pueden verse en cualquiera de los libros mencionados en el capítulo anterior. También pueden verse esos detalles en el hilo de este foro titulado "El Teorema de Gödel" (de los centenares de comentarios, hay que desbrozar los que contienen los detalles de la demostración).

(4) Para que todo el ejemplo tenga sentido se deben cumplir tres condiciones: a) Debe haber infinitos primos que se puedan escribir como suma o resta de tres primos consecutivos; b) Debe haber infinitos primos que no se puedan escribir como suma o resta de tres primos consecutivos; c) El número 43 no se debe poder escribir como suma o resta de tres primos consecutivos. Conjeturo que las tres afirmaciones con verdaderas. Si resultaran ser falsas, esto no invalidaría los conceptos expuestos, sino que solamente obligaría a buscar un ejemplo diferente, o bien a imaginar que las afirmaciones son verdaderas.

(A la parte 5 - A la parte 7)

La autorreferencia en la demostración de Gödel (Parte 5)

(A la parte 4 - A la parte 6)

La codificación de Gödel

Vamos a comenzar la demostración del Primer Teorema de Incompletitud de Gödel. Imaginemos que van a darnos un sistema de axiomas para la Aritmética que es recursivo y consistente, y que además permite demostrar todos los enunciados finitistas verdaderos. Tendremos que demostrar que existe un enunciado P tal que tanto él como su negación no son demostrables a partir de esos axiomas. [Por razones didácticas no vamos a suponer que trabajamos con un sistema de axiomas general, sino que nos han dado un sistema específico y que vamos a reproducir en él la demostración de Gödel.]

Hablo en futuro y digo "van a darnos un sistema de axiomas" porque el primer paso de la demostración de Gödel (y esto es importante destacarlo) no depende del sistema de axiomas que vayan a darnos.

Este primer paso consiste en asignarle a cada enunciado y a cada sucesión finita de enunciados un número natural, al que llamaremos el código de ese enunciado o de esa sucesión finita de enunciados. Hay muchas formas de definir esta asignación, pero, no importa el modo que elijamos para hacerlo, se deben cumplir siempre las siguientes condiciones:

1. A cada objeto (ya sea un enunciado, ya sea una sucesión de enunciados) le debe corresponder un número natural diferente.

2. Debe existir un algoritmo que, dado un enunciado o una sucesión de enunciados, nos permita calcular qué número le corresponde.

3. Debe existir un algoritmo que, dado un número natural, nos permita determinar si este número es. o no es, el código de un enunciado o de una sucesión, y que, en caso de que sí lo sea, determine exactamente a qué objeto corresponde. (1)

Cuando hablamos de "algoritmo" estamos hablando de un procedimiento sintáctico, por lo tanto los códigos se asignan a los enunciados o a las sucesiones de enunciados siempre que estos objetos estén escritos en el lenguaje formal.

Como decía antes, hay muchas maneras de asignar los códigos. Raymond Smullyan, en su libro Gödel's Incompleteness Theorems, trabaja con un lenguaje de 13 símbolos (incluyendo un símbolo especial para separar los enunciados que forman parte de una sucesión) y, traduciendo cada símbolo a un "dígito", convierte a cada enunciado (o sucesión de enunciados) en un número natural escrito en base 13. En Gödel para Todos se procede de manera similar, pero usando secuencias de dígitos binarios. El propio Gödel en su demostración original usa productos de potencias de primos (2). Aquí evitaremos dar detalles de cómo se hace la asignación, asumiremos simplemente que la asignación ha sido definida.

En algunas charlas (y tal vez también en alguna entrada de este mismo blog) he dicho que, por ejemplo, al enunciado "2 es par" se le asigna un número natural. Sin embargo, esta forma de hablar, que tiene la virtud de la simplicidad, encierra el germen de un error: el de confundir los conceptos sintácticos con los conceptos semánticos.

Como dije antes, la asignación de códigos es un procedimiento puramente sintáctico. ¿Cómo traducimos "2 es par" al lenguaje formal? En realidad hay muchas formas diferentes de hacerlo, por ejemplo (en lo que sigue usamos la "E" para inidcar "existe"):

Ex((1 + 1) = (1 + 1).x)

Ex((1 + 1).x = (1 + 1))

Ey((1 + 1) = (1 + 1).y)

Ex((1 + 1).y = (1 + 1))

...y muchos más.

Sintácticamente los cuatro enunciados escritos más arriba son diferentes y, por lo tanto, a cada uno de ellos le corresponde un código diferente. No existe un código para "2 es par", existen diferentes códigos para cada una de las infinitas formas en que puede ser traducido al lenguaje formal. Por lo tanto, no debemos pensar a los códigos como asignados a frases escritas en castellano, sino a objetos sintácticos llamados "enunciados" o "sucesiones de enunciados".

La observación anterior puede parecer trivial, pero no lo es. Los conceptos semánticos nos resultan más familiares que los sintácticos y por eso tendemos a pensar, a hablar, a explicar e, inclusive, a escribir libros de Lógica convirtiendo lo sintáctico en semántico (para que sea más "digerible"), pero esta conversión puede llevarnos a confusión.

Veamos otro ejemplo en el que se ve claramente la diferencia entre conceptos semánticos y sintácticos (entre conceptos matemáticos y metamatemáticos). Supongamos que tomamos como axiomas los enunciados A1,.., An (que, me apresuro a aclarar, no cumplen las hipótesis del Teorema de Gödel) y que nos dicen que el enunciado "1 + 1 = 1" es demostrable a partir de esos axiomas. ¿Debemos concluir que A1,...,An es un sistema inconsistente? La respuesta es que no. Los axiomas podrían formar un sistema consistente. (Recordemos que consistente significa que P y no-P nunca son al mismo tiempo demostrables.)

¿Cómo es posible que "1 + 1 = 1" sea demostrable, pero que el sistema sea consistente? Si uno se hace esa pregunta es que está confundiendo "demostrable" con "verdadero" (sintaxis con semántica).

¿Qué quiere decir que A1,.., An permitan demostrar el enunciado "1 + 1 = 1"? Respuesta: significa que existe una sucesión finita de enunciados cuyo enunciado final es "1 + 1 = 1" y en la que cada uno de ellos es, o bien uno de los A1,.., An, o bien se deduce de enunciados anteriores por aplicación del modus ponens. Notemos que esta respuesta está basada en conceptos sintácticos y que en ella no tiene cabida el concepto de "verdad" (o de "falsedad"). Notemos además que esa demostración de "1 + 1 = 1", como toda sucesión finita de enunciados, tiene asignada (a manera de código) un número natural.

Si los axiomas cumplieran la hipótesis de que todo enunciado finitista verdadero es demostrable, entonces sí formarían un sistema inconsistente. En efecto, "-(1 + 1 = 1)" (el signo "-" indica negación) es un enunciado finitista verdadero y, si se cumpliera la hipótesis, entonces ese enunciado sería demostrable. Como también "1 + 1 = 1" es demostrable entonces el sistema sería inconsistente.

Sin embargo, es posible que A1,.., An (que, dijimos, no cumple las hipótesis de Gödel) no admita una demostración para el enunciado "-(1 + 1 = 1)" y que, por lo tanto, sea un sistema consistente.

Continuará...

Notas:

(1) Dos aclaraciones de lenguaje: A los efectos de esta serie de entradas, los números naturales son 1, 2, 3, 4, 5, 6, etc. y por algoritmo entendemos un procedimiento mecánico que se completa en una cantidad finita de pasos.

(2) Gödel le asigna a cada símbolo del lenguaje un número impar. Si un enunciado E está formado por lo símbolos s1, s2, s3,... entonces le corresponde el número 2^c(s1).3^c(s2).5^c(s3).7^c(s4).... conde c() es el código de cada símbolo. A la sucesión de enunciados E1, E2, E3,... le corresponde el código 2^c(E1).3^c(E2)....

(A la parte 4 - A la parte 6)

La autorreferencia en la demostración de Gödel (Parte 4)

(A la parte 3 - A la parte 5)

La dialéctica Verdadero / Demostrable

La escuela intuicionista, aquella a la Hilbert se oponía, sostiene, como ya dijimos, que los objetos matemáticos son construidos por los humanos y que no son preexistentes a esta construcción. Para ellos, la Matemática se crea, no se descubre y así, por ejemplo, un número que nunca haya sido calculado simplemente no existe. Por lo tanto los intuicionistas niegan sentido a toda afirmación que hable de totalidades infnitas, ya que necesariamente habla de objetos inexistentes.

Hilbert, en su programa, propone un enfoque más moderado. Por una parte Hilbert habla de afirmaciones finitistas (o finitarias, según algunas traducciones), que son aquellas cuya verdad o falsedad puede ser verficada mecánicamente en una cantidad finita de pasos (por ejemplo, "12 + 3 = 15" o "22 no es primo"). De estas afirmaciones puede decirse, sin problemas, que son verdaderas o falsas, según sea el caso [los propios intuicionistas estarían de acuerdo con esto].

Hilbert admite, por otro lado, que las afirmaciones que se refieren a totalidades infinitas son problemáticas y que no es sencillo atribuirles un valor de verdad. Pero, a diferencia de los intuicionistas, afirma que esa atribución debe hacerse. "Entender el infinito", dice Hilbert, "es un reto al espíritu humano", un reto que debemos afrontar y vencer.

Hilbert hace la siguiente comparación: en Matemáticas, tenemos por un lado las sumas de una cantidad finita de números, que pueden ser calculadas sin problema. Pero, por otro lado, tenemos también las series, que son sumas infinitas. Las series pueden llegar a ser muy problemáticas, sin embargo, gracias a la noción de límite, el Análisis ha podido darles un sentido claro y preciso. De la misma manera, dice Hilbert, la Lógica tiene el desafío de darle un sentido claro y preciso a las afirmaciones no finitistas.

Este sentido se daría a través de la noción de demostrabilidad. Dado un sistema de axiomas, diremos que un enunciado P es demostrable a partir de ellos si existe una demostración (basada en ese sistema de axiomas) cuyo último enunciado es P. [Es decir, si hay una demostración que termina con el enunciado P. La definición metamatemática de demostración la hemos visto en el capítulo anterior.]

El Programa de Hilbert propone, entonces, dar axiomas para la Aritmética de tal modo que, para empezar, todo enunciado finitista verdadero sea demostrable (es lo menos que podemos pedir) y tal que, además, para cualquier otro enunciado P, o bien P, o bien su negación sea demostrable.

Cada enunciado "demostrable" será "verdadero". Es decir, el programa de Hilbert buscaba una síntesis entre los conceptos de demostrabilidad y verdad. Dado que el concepto de demostrabilidad es sintáctico (verificable mecánicamente en una cantidad finita de pasos), obtendríamos una noción de verdad "segura" y libre de posibles paradojas.

Lamentablemente para Hilbert, el primer teorema de Gödel prueba que esto es imposible: en la Aritmética "verdad" y "demostrabilidad" no son equivalentes. Cualesquiera sean los axiomas que se elijan (siempre que cumplan las condiciones metamatemáticas de Hilbert) siempre habrá algún enunciado P tal que tanto él como su negación no son demosrables (por lo que P quedaría fuera de esta definición sintáctica de "verdad").

En su libro La Nueva Mente del Emperador, Roger Penrose dice que no entiende el "menosprecio" que los seguidores de Hilbert sienten por la noción de verdad Matemática, ya que admiten, según Penrose, la posibilidad de que haya enunciados que no son verdaderos ni falsos.

En realidad, Penrose se equivoca al hacer este comentario. Es cierto que si la afirmación P no es demostrable, y tampoco es demostrable su negación, entonces para el Programa de Hilbert P no sería verdadera ni falsa. Pero, en realidad, la idea de Hilbert era dar axiomas de tal modo que esta situación nunca sucediera. Todo enunciado, a través de la definición metamatemática de demostrabilidad, debía ser, en última instancia, verdadero o falso. Fue Gödel quien le aguó la fiesta al probar que siempre habría enunciados indecidibles.

Antes de terminar recapitulemos un poco lo que hemos visto hasta aquí. El Programa de Hilbert proponía dar un sistema de axiomas para la Aritmética que cumpliera estas condiciones:

1. El sistema debía ser recursivo (se debía poder verificar mecánicamente en una cantidad finita de pasos si un enunciado es, o no, un axioma).

2. El sistema debía ser consistente (no debía haber un enunciado P tal que él y su negación fueran simultáneamente demostrables, la regla de inferencia es el modus ponens).

3. Todo enunciado finitista verdadero debía ser demostrable (esta es la condición que a veces se enuncia como "Contiene suficiente Aritmética").

4. Para todo enunciado P, o bien P, o bien su negación debía ser demostrable.

5. Debía poder verificarse mecánicamente en una cantidad finita de pasos que el sistema es consistente.

Como ya dijimos, los teoremas de Gödel prueban que si se cumplen las tres primeras condiciones entonces las dos últimas fallan. A partir del próximo capítulo comentaremos la demostración de estos teoremas y llegaremos, finalmente, a la discusión sobre la autorreferencia.

(A la parte 3 - A la parte 5)

La autorreferencia en la demostración de Gödel (Parte 3)

(A la parte 2 - A la parte 4)

Demostraciones

- Profesor, ¿cuándo llegamos a la autorreferencia?

- Paciencia, ya falta poco.

En el capítulo anterior dijimos que el Programa de Hilbert proponía dar axiomas para la Aritmética y que estos axiomas (así como las reglas de inferencia, que son las que nos dicen qué conclusiones podemos obtener a partir de ciertas hipótesis) debían ser elegidos de modo tal que la corrección de cualquier demostración basada en ellos pudiera ser verificada (desde el nivel de la Metamatemática) mecánicamente en una cantidad finita de pasos (es decir, debía ser posible programar una computadora para que verificara si una demostración es válida o no).

En concreto, las demostraciones que contemplaba el Programa de Hilbert como válidas debían ser traducibles a una sucesión finita de enunciados tales que cada uno de estos, o bien era un axioma, o bien podía deducirse de enunciados previamente ubicados en la sucesión por aplicación de ciertas reglas de inferencia específicas. (1)

Esta idea impone tres características a la formalización de la Aritmética. La primera es que sus enunciados deben poder traducirse a un lenguaje con símbolos bien definidos (requisito necesario para que haya un algoritmo que trabaje sobre esos enunciados -a nivel metamatemático-).

A los efectos de esta serie de entradas, el lenguaje que usaremos constará de los símbolos "+" y ".", la constante 1, a los que agregaremos paréntesis y símbolos para las operaciones lógicas. El lenguaje tendrá también variables, x, y, z,... que sólo podrán representar números naturales (nunca expresarán funciones, conjuntos u otros objetos (2)).

Observemos que la Metamatemática trabaja solamente a nivel sintáctico, por lo que la expresión:

(1 + 1).(1 + 1) = 1 + 1 + 1 + 1

será, a nivel metamatemático, diferente de la expresión:

1 + 1 + 1 + 1 = (1 + 1).(1 + 1)

porque, aunque ambas tienen los mismos símbolos, estos están escritos en diferente orden.

Asumamos que, para su tratamiento metamatemático, todos los enunciados han sido traducidos a este lenguaje formal. Asumamos también que tenemos una secuencia de enunciados y que queremos escribir un programa que verifique si esa secuencia es, o no, una demostración válida. El programa "tomará" entonces un enunciado de la secuencia y deberá verificar si se trata, o no, de un axioma.

La segunda característica es, entonces, que exista un algoritmo que verifique en una cantidad finita de pasos si un enunciado es, o no, un axioma.

Continuando con el proceso que debería seguir ese programa, si un enunciado no es un axioma, el programa debe se capaz de verificar si el enunciado puede deducirse de enunciados anteriores en la sucesión. La tercera característica es, entonces, que la relación "Q se deduce de las hipótesis H1, H2, H3,..." debe ser verificable algorítmicamente.

En realidad, podemos reducirnos a tomar una única regla de inferencia: la llamada Regla del Modus Ponens, que dice que de P y de P ---> Q se deduce Q. (La regla debe ser entendida a nivel sintáctico, sin apelación a posible significados.)

Diremos que una propiedad es recursiva si es verificable algorítmicamente. Podemos decir entonces que el sistema de axiomas y sus reglas de inferencia deben ser ambos recursivos.

Continuará...

Notas:

(1) Éste es el proceso de verificación metamatemática de las demostraciopnes que proponía el Programa de Hilbert. Desde luego, no es el proceso por el que los matemáticos encuentran esas demostraciones.

(2) Toda teoría tiene dos tipos de axiomas: sus axiomas específicos y también los axiomas lógicos, que son generales y comunes a todas las teorías. Estos últimos son enunciados que valen cualquiera sea el universo del discurso considerado (como por ejemplo, "Para todo x, x = x"). Si respetamos las restricciones para el uso de variables entonces es posible dar un sistema de axiomas que respeta las condiciones de Hilbert y que permite deducir todas esas afirmaciones universalmente válidas (esto fue probado por Gödel en 1929). Si admitiéramos variables que representaran funciones, conjuntos, etc. entonces el Programa de Hilbert sería irrealizable al nivel mismo de esta lógica subyacente.

(A la parte 2 - A la parte 4)

La autorreferencia en la demostración de Gödel (Parte 2)

(A la parte 1 - A la parte 3)

La dialéctica Sintaxis /Semántica

Los teoremas de Gödel, publicados en 1931, forman parte de una larga polémica sobre los Fundamentos de la Matemática que había comenzado en 1872 con el descubrimiento, por parte de Cantor, de los transfinitos, y que se había potenciado a partir de 1902 con el descubrimiento de la Paradoja de Russell.

El campo de batalla de la polémica era nada menos que el infinito. La escuela constructivista, encabezada por L.E.J. Brouwer, sostenía que la introducción del infinito actual en Matemáticas era absurda e injustificada y que la teoría de los transfinitos de Cantor era solamente un juego de palabras sin sentido. Los únicos objetos matemáticos válidos, sostenía esta escuela, son aquellos que se pueden construir mecánicamente en una cantidad finita de pasos. Por ejemplo, para ellos no podía hablarse de la totalidad de los números naturales, sino de una cantidad siempre finita y creciente de números que son calculados uno por uno. Los enunciados que hablan de totalidades infinitas, para los constructivistas carecían de significado.

Hacia 1920 interviene en la polémica David Hilbert quien, en una serie de papers publicados a lo largo de unos diez años, propone el que hoy es conocido como el Programa de Hilbert y que, en esencia, llevaba la exigencia de finitud y de constructividad de los objetos matemáticos a los razonamientos matemáticos.

Con más precisión, Hilbert proponía la creación de una nueva ciencia a la que él llamaba Metamatemática. Esta ciencia tendría como objetivo el verificar la validez de los razonamientos matemáticos. Para evitar polémicas (y para asegurarse de que no surgieran paradojas) esta ciencia sería puramente finitista: la Metamatemática trataría a los enunciados y a los razonamientos matemáticos como si fueran simples secuencias de símbolos sin significado a los que manipularía mecánicamente en una cantidad finita de pasos.

Se ha dicho en algunos textos de divulgación que el Programa de Hilbert proponía reducir la Matemática a un juego de símbolos carente de significado, se ha dicho también que para Hilbert el concepto de "verdad matemática" no existía. Nada más falso. Hilbert, comprendamos, era ante todo un investigador matemático (el mejor de su tiempo) por lo que es imposible, inimaginable, que pudiera pensar así. Esas características las atribuía Hilbert, no a la Matemática, sino a la Metamatemática.

La Matemática trabaja a un nivel semántico, lleno de significados. El matemático, en el día a día, siempre trabaja, crea, conjetura, demuestra y sufre, como si lo que tuviera entre manos fueran objetos reales.

La Metamatemática, según la idea de Hilbert, que trabaja a nivel sintáctico, provee los métodos para verificar si los razonamientos, que el matemático ha obtenido como fruto final de su trabajo creador, son correctos. Para hacer esta verificación los razonamientos serían cargados en una computadora que verificaría si el razonamiento es válido, o no. Hilbert, desde luego, no hablaba de computadoras, pero lo que he dicho en la oración anterior refleja la idea esencial de Hilbert: la validez del razonamiento es verificada mediante manipulaciones mecánicas de símbolos realizadas en una cantidad finita de pasos (la verificación del razonamiento, no su obtención).

En concreto, el Programa de Hilbert proponía dar un conjunto de axiomas para la Aritmética (1) que cumpliera estas cuatro condiciones:

1. El sistema debía ser consistente (es decir, no debía existir un enunciado P tal que P y su negación fueran simultáneamente demostrables).

2. La validez de cualquier demostración debía ser verificable por manipulaciones mecánicas (sintácticas) en una cantidad finita de pasos.

3. Dado cualquier enunciado P, o bien él o bien su negación debía ser demostrable.

4. La consistencia de los axiomas debía ser verificable mecánicamente en una cantidad fnita de pasos.

Nótese que estas condiciones no son matemáticas sino metamatemáticas. Si estas cuatro condiciones pudieran cumplirse entonces la noción de "demostrabilidad" (sintáctica) y de "verdad" (semántica) podrían considerarse equivalentes. Pero los teoremas de Gödel demostraron precisamente que esas cuatro condiciones no se pueden cumplirse a la vez. Si se cumplen 1 y 2 entonces 3 es falsa y 4, si el sistema es razonablemente potente, es irrealizable.

En el próximo capítulo precisaremos qué quiere decir "razonablemente potente" y comenzaremos a analizar la demostración de Gödel.

Continuará...

(1) Nota: La Aritmética es la teoría que habla de la suma y el producto de los números naturales. Hilbert consideraba que era ésta la teoría fundamental de la Matemática (y no la Teoría de Conjuntos).

(A la parte 1 - A la parte 3)