...del día en que Kurt Gödel levantó la mano en el congreso de Königsberg y anunció por primera vez sus teoremas de incompletitud.
Mostrando las entradas con la etiqueta Gödel. Mostrar todas las entradas
Mostrando las entradas con la etiqueta Gödel. Mostrar todas las entradas
12.4.15
Adenda a "¿La mente humana?"
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.
2.4.15
¿La mente humana?
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".
12.8.13
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.
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.
22.6.11
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.
10.3.11
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
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.
9.3.11
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.
8.3.11
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.
5.3.11
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)....
2.3.11
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.
26.2.11
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.
25.2.11
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).
23.2.11
La autorreferencia en la demostración de Gödel (Parte 1)
¿Qué decimos cuando decimos "Esta oración no es demostrable"?
En estos últimos años, por diversos motivos y en diferentes ámbitos, me ha tocado discutir extensamente la demostración de los teoremas de Gödel. En esas ocasiones he notado que hay ciertas dudas que aparecen recurrentemente en el público y que, tal vez, sean compartidas por algunos de los lectores de este blog.
La intención de esta serie de entradas es tratar de despejar esas dudas. No intentaré desarrollar en detalle las demostraciones de los teoremas de Gödel, sino que haré un bosquejo general poniendo énfasis especial en dos puntos:
1. El llamado Primer Teorema de Incompletitud de Gödel dice que, dado un sistema axiomático para la Aritmética que cumpla ciertas condiciones (que recordaremos más adelante), siempre es posible encontrar una afirmación aritmética que no puede ser demostrada ni refutada a partir de esos axiomas.
Suele decirse (yo mismo lo he dicho en más de una ocasión) que la demostración de este teorema consiste en construir una afirmación aritmética que dice: "Esta oración no es demostrable".
Pero ¿es realmente así? ¿Habla realmente la afirmación de su propia no-demostrabilidad? La respuesta es que la afirmación no habla de sí misma. Más exactamente, veremos que la afirmación puede llegar a considerarse autorreferente solamente si se aceptan ciertas convenciones arbitrarias que son externas al sistema de axiomas.
El segundo punto que trataremos es éste:
2. Tomemos, a modo de ejemplo, los axiomas de Peano (que son axiomas de la Aritmética). Aceptemos que esos axiomas forman un sistema consistente (como, de hecho, suele aceptarse). Del llamado Segundo Teorema de Incompletitud de Gödel se deduce que la afirmación "Los axiomas de Peano son consistentes" no puede demostrarse ni refutarse a partir de esos axiomas.
Ahora bien, si una afirmación P no puede demostrarse ni refutarse a partir de un sistema de axiomas (llamémoslo A) entonces tanto la afirmación P como su negación pueden ser agregadas al sistema A y en ambos casos se obtendrá un sistema consistente. (El ejemplo histórico clásico es tomar A como los primeros cuatro postulados de Euclides y como P, el postulado de las paralelas.)
En particular, esto quiere decir que la afirmación "Los axiomas de Peano no son consistentes" puede agregarse a los axiomas de Peano de modo que el sistema resultante ¡sea consistente!. Ahora... ¿no es raro? ¿Cómo puede ser consistente con los axiomas de Peano la afirmación que niega (falsamente) que esos axiomas sean consistentes? Como veremos, la paradoja es sólo aparente y resulta de una mala interprertación de lo que realmente dice el enunciado aritmético "Los axiomas de Peano no son consistentes".
La tarea está planteada. Sólo falta arremangarse y llevarla a cabo.
Continuará...
1.2.11
5.7.09
La paradoja de Gödel
Como ya se ha dicho en otra parte, la demostración del Teorema de Gödel consiste esencialmente en construir (en el lenguaje apropiado) una afirmación cuyo significado es: "Yo no soy demostrable".
Esa afirmación es, o bien verdadera, o bien falsa. Si es falsa, por lo que ella misma dice, sería demostrable y habría así una falsedad demostrable (lo que es imposible). Entonces debe ser verdadera, y entonces, por lo que ella misma dice, no es demostrable. Hay así una verdad no demostrable.
Pero, veamos, hemos probado que la afirmación es verdadera. Es decir, hemos demostrado la afirmación. Por lo tanto es demostrable y falsa. Existe entonces una falsedad demostrable.
Esa afirmación es, o bien verdadera, o bien falsa. Si es falsa, por lo que ella misma dice, sería demostrable y habría así una falsedad demostrable (lo que es imposible). Entonces debe ser verdadera, y entonces, por lo que ella misma dice, no es demostrable. Hay así una verdad no demostrable.
Pero, veamos, hemos probado que la afirmación es verdadera. Es decir, hemos demostrado la afirmación. Por lo tanto es demostrable y falsa. Existe entonces una falsedad demostrable.
2.7.09
Gödel gráfico
(El dibujo es de Pablo Ingrassia. La "foresta" representa los razonamientos matemáticos.)
20.6.09
Un poco de historia
La ciudad alemana de Königsberg [1] fue testigo de varios importantes nacimientos. Allí, en 1724, nació el célebre filósofo Emmanuel Kant y fue allí también donde nació, en 1862, el brillante matemático David Hilbert. A mediados del siglo XVIII nació en Königsberg un famoso problema matemático (que habla de siete puentes que cruzan un río que atraviesa la ciudad [2
]) en el curso cuya resolución Leonhard Euler fundó un nuevo campo de la matemática: la teoría de grafos.
Y fue también en Königsberg donde vio por primera vez la luz el famoso Teorema de Gödel. Sucedió el 7 de septiembre de 1930 durante un congreso sobre fundamentos de la matemática, es decir, durante una reunión en la que los especialistas discutían qué es la matemática, cuál es su objeto de estudio y cuáles son sus métodos. Desde hacía más de dos décadas se venía desarrollando una ácida controversia acerca de esas cuestiones, una discusión en la que sus protagonistas sostenían posiciones aparentemente irreconciliables. En la década previa a 1930 esas posiciones irreconciliables reconocían dos claros representantes: en un rincón el ya mencionado David Hilbert, fundador de la llamada Escuela Formalista y en el otro, L.E.J. Brouwer, creador de la llamada Escuela Intuicionista.
A pesar de tanta controversia, aquél septiembre de 1930 parecía lleno de buenos augurios. En la sesión final del congreso Arend Heyting (uno de los principales discípulos de Brouwer) afirmó que la “guerra” entre los formalistas y los intuicionistas podía darse por terminada, pues si el programa propuesto por Hilbert para la matemática lograba completarse con éxito entonces los intuicionistas aceptarían gustosamente las ideas de Hilbert. En otras palabras, los intuicionistas presentaban una rendición en toda regla por lo que la larga controversia parecía llegar a su fin.
Sin embargo, en medio de tan optimistas manifestaciones un joven matemático austriaco pidió la palabra. Tímidamente este joven anunció que acababa de demostrar un teorema (que sería publicado unos meses más tarde) en el que demostraba que el programa de Hilbert, el programa formalista que todos, amigos y enemigos, acababan de aceptar gustosamente, era completamente irrealizable. Ese joven era Kurt Gödel y el teorema que estaba anunciando era, por supuesto, el hoy famoso Teorema de Incompletitud de Gödel.
¿Cómo se llegó a esa escena de 1930? ¿Por qué apenas a principios del siglo XX, después de más de dos mil quinientos años de trabajo matemático, se planteó la necesidad de definir el objeto y los métodos de esa ciencia? Para entender las respuestas a estas preguntas, así como el enunciado del Teorema de Gödel, debemos remontarnos algunos años hacia atrás en el tiempo, a la década de 1870, a la ciudad de Halle, en Alemania, lugar y tiempo en el que Georg Cantor (1845–1918) revolucionó la forma de entender el infinito.
Desde Aristóteles se entendía, tanto en filosofía como en matemática, que el infinito era inalcanzable. Por ejemplo, sabemos que hay infinitos números naturales: 0, 1, 2, 3, 4, 5,... pero según la forma de pensar de Aristóteles, la infinitud de los números significa solamente que si nos proponen cualquier número natural siempre existirá uno mayor. La imposibilidad de alcanzar el infinito implica que no hay ningún lugar (concreto o abstracto) en el que estén reunidos al mismo tiempo todos los números naturales. El infinito no existe en acto, sólo en potencia, decía Aristóteles, y en consecuencia sería un error hablar de los números como de una totalidad acabada y completa. Esta visión del infinito dominó la matemática y la filosofía a los largo de los siglos.
En 1872 Georg Cantor (nacido en San Petersburgo, aunque vivió casi toda su vida en Halle, Alemania) trabajaba en un problema relativamente menor de análisis matemático. Cantor buscaba demostrar una propiedad relativa a cierto tipo de funciones y en el transcurso de ese trabajo se encontró ante la necesidad de expresar de un modo claro y concreto algunas condiciones muy complejas, las cuales debían cumplirse para que valieran las conclusiones a las que Cantor quería llegar [4].
Se trataba en principio de un problema de lenguaje y para resolverlo Cantor inventó un nuevo concepto, el de conjunto derivado. Sin entrar en detalles, basta decir que definió un mecanismo por el cual a partir de un conjunto P de puntos se puede obtener un nuevo conjunto P’, llamado el derivado de P. A partir de P’ se obtiene a su vez un nuevo derivado P”. Y luego el derivado de P”, que es P(3), y luego P(4), P(5), etc.
Pero Cantor observó que no había motivo para detenerse y que era perfectamente posible definir P(infinito). Más aún observó también que era posible aplicar el mismo mecanismo a P(infinito) obteniendo así P(infinito + 1, P(infinito + 2), P(infinito + 3).... Es decir no sólo era posible llegar al infinito sino que inclusive era posible ir más allá de él [5].
Esta nueva forma de ver el infinito, totalmente opuesta a la que había impuesto Aristóteles, habilitó la idea de ver a los conjuntos infinitos como totalidades acabadas y completas; es decir, permitió crear la teoría de conjuntos. En los años posteriores a 1880 Cantor inició el proyecto de refundar toda la matemática sobre la base de esta teoría. Todos los demás conceptos matemáticos se definían a partir de la noción de conjunto. Así por ejemplo para Cantor el número 0 se definía como la cantidad de elementos del conjunto vacío, el número 1 sería la cantidad de elementos del conjunto formado solamente por el 0, y así sucesivamente. Todas las operaciones numéricas se definían desde las operaciones entre conjuntos.
Por la misma época Richard Dedekind (amigo y colega de Cantor) desarrolló ideas similares. Sin embargo, quien llevó más lejos la idea de fundar la matemática sobre bases conjuntistas fue Gottlob Frege quien a lo largo de casi veinte años elaboró una obra monumental en la que construyó con todo detalle un lenguaje para hablar de los conjuntos (y que es la base del actual lenguaje formal de la lógica) y a su vez, usó los conjuntos como base de la construcción de toda la matemática.
En junio de 1902 Frege acababa de enviar a la imprenta el segundo tomo de la obra fundamental de su vida cuando recibió una carta del por entonces muy joven filósofo y matemático Bertrand Russell. En esta carta Russell, que había leído el primer tomo de la obra de Frege (publicado en 1893), le señalaba un error en la misma base de su sistema.
Para Frege un conjunto es la reunión en un todo de los objetos (reales o imaginarios) que cumplen una determinada propiedad en común. Por ejemplo, la propiedad de “ser un caballo blanco” corresponde, obviamente, al conjunto formado por todos los caballos blancos. Pues bien de esta definición de la noción de conjunto Russell extrajo una contradicción [6], por lo tanto la misma noción de conjunto era contradictoria.
Frege admitió inmediatamente el error y agregó una nota adicional a su obra en la que admitía humildemente que todo el sistema por él concebido dejaba de tener validez pues se había derrumbado desde su misma base.
Ahora bien, por ese entonces la teoría de conjuntos se había transformado en una herramienta básica de la matemática y las nociones conjuntistas estaban en los cimientos de muchos nuevos desarrollos, especialmente en análisis matemático. El descubrimiento de Russell significó entonces una verdadera crisis en toda la matemática, pues si algo tan simple y natural como la noción de conjunto era contradictoria ¿cómo podía asegurarse la corrección de conceptos más complejos? Es precisamente a causa de esta crisis que a principios del siglo XX se planteó la necesidad de revisar los fundamentos de la matemática.
Ante la crisis provocada por el descubrimiento de Russell hubo inicialmente dos reacciones. Por una parte, el propio Bertrand Russell propuso rescatar el programa de Frege introduciendo en él las modificaciones que fueran necesarias para evitar todas las contradicciones posibles. Este programa fue extensamente expuesto en la obra Principia Matemática, que Russell escribió junto a Alfred Whitehead y cuyo primer tomo se publicó en 1910.
Otra reacción, contemporánea de la anterior, fue encabezada por el matemático holandés L.E.J. Brouwer. Según Brouwer era imposible evitar las contradicciones en la teoría de conjuntos y cualquier intento de reparar el sistema de Frege estaba condenado al fracaso, pues todas las contradicciones nacían simplemente de la introducción del infinito en acto. Brouwer proponía descartar la teoría de Cantor y retornar a una matemática finitista en la que el infinito, tal como quería Aristóteles, fuera inalcanzable.
Más aún, Brouwer sostenía que sólo puede decirse que un objeto matemático existe si se puede dar una receta (una serie finita de instrucciones, es decir un algoritmo) que permita construirlo en una cantidad finita de pasos a partir de los números naturales.
Un ejemplo de algoritmo:
Paso 1: asígnese al número x el valor 2.
Paso 2: asígnese a x un nuevo valor, el que resulta de promediar el valor actual de x con el valor de 2/x (2 dividido por x).
Paso 3: repítase el paso anterior 10 veces más.
Cuantas más veces se aplique el paso 3, más se acercará el valor de x al de la raíz cuadrada de 2. El algoritmo, entonces, permite construir aproximaciones sucesivas de ese número.
Brouwer decía también que sólo tiene sentido definir una propiedad si al mismo tiempo se da un método algorítmico para verificar en una cantidad finita de pasos si un objeto cumple o no esa propiedad.
Hacia 1920 el programa de Russell comenzó a desmoronarse, especialmente a causa de ciertos axiomas que éste se vio obligado a incluir, pero cuya validez resultaba ser especialmente dudosa. A causa de ello, la escuela de Brouwer comenzó a dominar el pensamiento matemático y como consecuencia la teoría de Cantor comenzó a estar en peligro de ser eliminada. Fue entonces cuando entró en escena David Hilbert.
Hilbert fue desde siempre amigo y defensor de Cantor y bajo el lema “del paraíso que Cantor creó para nosotros nadie podrá expulsarnos” decidió contrarrestar las ideas de Brouwer. Además de gran matemático, Hilbert era un gran político y por eso decidió crear una filosofía de la matemática que diera cabida al infinito en acto pero que al mismo tiempo pudiera ser aceptada por los intuicionistas, es decir por Brouwer y sus seguidores.
Los intuicionistas, dijimos, exigían que todo objeto matemático fuese construido mediante un algoritmo y que toda propiedad fuera verificada asimismo algorítmicamente. La idea central de Hilbert fue llevar esta exigencia algorítmica, de los objetos y sus propiedades, a los razonamientos.
Para Hilbert toda teoría matemática debía fundarse en axiomas, que son afirmaciones que se aceptarían como verdaderas. Todas las demás verdades de la teoría se deducirían de los axiomas mediante razonamientos o demostraciones. Estos razonamientos debían ser finitistas al estilo intuicionista, es decir, debía existir un algoritmo (una receta) que, en una cantidad finita de pasos, permitiera determinar si un razonamiento es válido o no. En palabras modernas, debería ser posible programar una computadora de tal modo que fuera capaz de decidir si un razonamiento es correcto o no.
Los axiomas podían hablar del infinito en acto, de totalidades infinitas acabadas y completas, siempre que los razonamientos para deducir otras verdades a partir de ellos fueran finitistas y siempre que, además, por esos mismos razonamientos finitstas se pudiera demostrar que no habría paradojas o contradicciones.
El Programa de Hilbert se proponía entonces refundar la matemática bajo estas especificaciones. Y tan afortunada fue la idea de Hilbert que, como ya dijimos, en 1930 los intuicionistas finalmente “se rindieron” y aceptaron su programa. Pero en 1930 fue también cuando Gödel demostró que el Programa de Hilbert era irrealizable al probar (y ése es el enunciado del Teorema de Incompletitud) que los métodos finitistas que Hilbert proponía son incapaces de demostrar todas las verdades matemáticas. En aquel dramático septiembre de 1930 el Teorema de Gödel marcó un punto crucial en la historia de la lógica matemática. Sus consecuencias han sido llevadas, no siempre justificadamente, a la filosofía, la sociología y otras ramas del saber muy alejadas de su ámbito original.
Notas:
[1] La ciudad de Königsberg ya no es alemana, ni se llama Königsberg, en la actualidad la ciudad es rusa y se llama Kaliningrado.
[2] El río se llama Pregel y en él, cuenta la historia, hay dos islas y siete puentes: un puente conecta las dos islas entre sí, dos puentes más conectan a la isla menor con cada una de las dos orillas del río, otros dos puentes conectan a la isla mayor con una de las orillas del río y los últimos dos conectan a la isla mayor con la otra orilla del río. El problema pide hallar un camino que recorra los siete puentes de Königsberg, una vez cada uno sin repetir. Leonhard Euer demostró que esa tarea es irrealizable.
[3] Había también argumentos teológicos para sostener esta idea, según estos argumentos el infinito es un concepto solamente accesible para Dios e inalcanzable para la mente finita de los humanos.
[4] El problema en el que trabajaba Cantor está bien descripto en Ferreirós y Grattan-Guiness. En último dice en su libro que el problema en el que trabajaba Cantor era muy relevante, aquí nos permitimos disentir respetuosamente con esa opinión pues entendemos que hay varias razones para afirmar que el problema era menor, es probable que al dar su opinión Grattan-Guiness se deje llevar por su admiración hacia Georg Cantor.
[5] “Fui llevado por la lógica de mis investigaciones a romper con tradiciones que había aprendido a venerar”, escribió Cantor en 1883.
[6] Observemos que el conjunto de todos los conjuntos es un miembro de sí mismo (pues al ser él mismo un conjunto es miembro del conjunto de todos los conjuntos). La contradicción, conocida como la Paradoja de Russell, surge al considerar los conjuntos que no se tienen a sí mismos entre sus propios miembros. Razonando a partir de estos objetos Russell llega a la conclusión de que la noción de conjunto que usa Frege (que es una elaboración más precisa de la que usan Cantor y Dedekind) es contradictoria.
]) en el curso cuya resolución Leonhard Euler fundó un nuevo campo de la matemática: la teoría de grafos.Y fue también en Königsberg donde vio por primera vez la luz el famoso Teorema de Gödel. Sucedió el 7 de septiembre de 1930 durante un congreso sobre fundamentos de la matemática, es decir, durante una reunión en la que los especialistas discutían qué es la matemática, cuál es su objeto de estudio y cuáles son sus métodos. Desde hacía más de dos décadas se venía desarrollando una ácida controversia acerca de esas cuestiones, una discusión en la que sus protagonistas sostenían posiciones aparentemente irreconciliables. En la década previa a 1930 esas posiciones irreconciliables reconocían dos claros representantes: en un rincón el ya mencionado David Hilbert, fundador de la llamada Escuela Formalista y en el otro, L.E.J. Brouwer, creador de la llamada Escuela Intuicionista.
A pesar de tanta controversia, aquél septiembre de 1930 parecía lleno de buenos augurios. En la sesión final del congreso Arend Heyting (uno de los principales discípulos de Brouwer) afirmó que la “guerra” entre los formalistas y los intuicionistas podía darse por terminada, pues si el programa propuesto por Hilbert para la matemática lograba completarse con éxito entonces los intuicionistas aceptarían gustosamente las ideas de Hilbert. En otras palabras, los intuicionistas presentaban una rendición en toda regla por lo que la larga controversia parecía llegar a su fin.
Sin embargo, en medio de tan optimistas manifestaciones un joven matemático austriaco pidió la palabra. Tímidamente este joven anunció que acababa de demostrar un teorema (que sería publicado unos meses más tarde) en el que demostraba que el programa de Hilbert, el programa formalista que todos, amigos y enemigos, acababan de aceptar gustosamente, era completamente irrealizable. Ese joven era Kurt Gödel y el teorema que estaba anunciando era, por supuesto, el hoy famoso Teorema de Incompletitud de Gödel.
¿Cómo se llegó a esa escena de 1930? ¿Por qué apenas a principios del siglo XX, después de más de dos mil quinientos años de trabajo matemático, se planteó la necesidad de definir el objeto y los métodos de esa ciencia? Para entender las respuestas a estas preguntas, así como el enunciado del Teorema de Gödel, debemos remontarnos algunos años hacia atrás en el tiempo, a la década de 1870, a la ciudad de Halle, en Alemania, lugar y tiempo en el que Georg Cantor (1845–1918) revolucionó la forma de entender el infinito.
Desde Aristóteles se entendía, tanto en filosofía como en matemática, que el infinito era inalcanzable. Por ejemplo, sabemos que hay infinitos números naturales: 0, 1, 2, 3, 4, 5,... pero según la forma de pensar de Aristóteles, la infinitud de los números significa solamente que si nos proponen cualquier número natural siempre existirá uno mayor. La imposibilidad de alcanzar el infinito implica que no hay ningún lugar (concreto o abstracto) en el que estén reunidos al mismo tiempo todos los números naturales. El infinito no existe en acto, sólo en potencia, decía Aristóteles, y en consecuencia sería un error hablar de los números como de una totalidad acabada y completa. Esta visión del infinito dominó la matemática y la filosofía a los largo de los siglos.
En 1872 Georg Cantor (nacido en San Petersburgo, aunque vivió casi toda su vida en Halle, Alemania) trabajaba en un problema relativamente menor de análisis matemático. Cantor buscaba demostrar una propiedad relativa a cierto tipo de funciones y en el transcurso de ese trabajo se encontró ante la necesidad de expresar de un modo claro y concreto algunas condiciones muy complejas, las cuales debían cumplirse para que valieran las conclusiones a las que Cantor quería llegar [4].
Se trataba en principio de un problema de lenguaje y para resolverlo Cantor inventó un nuevo concepto, el de conjunto derivado. Sin entrar en detalles, basta decir que definió un mecanismo por el cual a partir de un conjunto P de puntos se puede obtener un nuevo conjunto P’, llamado el derivado de P. A partir de P’ se obtiene a su vez un nuevo derivado P”. Y luego el derivado de P”, que es P(3), y luego P(4), P(5), etc.
Pero Cantor observó que no había motivo para detenerse y que era perfectamente posible definir P(infinito). Más aún observó también que era posible aplicar el mismo mecanismo a P(infinito) obteniendo así P(infinito + 1, P(infinito + 2), P(infinito + 3).... Es decir no sólo era posible llegar al infinito sino que inclusive era posible ir más allá de él [5].
Esta nueva forma de ver el infinito, totalmente opuesta a la que había impuesto Aristóteles, habilitó la idea de ver a los conjuntos infinitos como totalidades acabadas y completas; es decir, permitió crear la teoría de conjuntos. En los años posteriores a 1880 Cantor inició el proyecto de refundar toda la matemática sobre la base de esta teoría. Todos los demás conceptos matemáticos se definían a partir de la noción de conjunto. Así por ejemplo para Cantor el número 0 se definía como la cantidad de elementos del conjunto vacío, el número 1 sería la cantidad de elementos del conjunto formado solamente por el 0, y así sucesivamente. Todas las operaciones numéricas se definían desde las operaciones entre conjuntos.
Por la misma época Richard Dedekind (amigo y colega de Cantor) desarrolló ideas similares. Sin embargo, quien llevó más lejos la idea de fundar la matemática sobre bases conjuntistas fue Gottlob Frege quien a lo largo de casi veinte años elaboró una obra monumental en la que construyó con todo detalle un lenguaje para hablar de los conjuntos (y que es la base del actual lenguaje formal de la lógica) y a su vez, usó los conjuntos como base de la construcción de toda la matemática.
En junio de 1902 Frege acababa de enviar a la imprenta el segundo tomo de la obra fundamental de su vida cuando recibió una carta del por entonces muy joven filósofo y matemático Bertrand Russell. En esta carta Russell, que había leído el primer tomo de la obra de Frege (publicado en 1893), le señalaba un error en la misma base de su sistema.
Para Frege un conjunto es la reunión en un todo de los objetos (reales o imaginarios) que cumplen una determinada propiedad en común. Por ejemplo, la propiedad de “ser un caballo blanco” corresponde, obviamente, al conjunto formado por todos los caballos blancos. Pues bien de esta definición de la noción de conjunto Russell extrajo una contradicción [6], por lo tanto la misma noción de conjunto era contradictoria.
Frege admitió inmediatamente el error y agregó una nota adicional a su obra en la que admitía humildemente que todo el sistema por él concebido dejaba de tener validez pues se había derrumbado desde su misma base.
Ahora bien, por ese entonces la teoría de conjuntos se había transformado en una herramienta básica de la matemática y las nociones conjuntistas estaban en los cimientos de muchos nuevos desarrollos, especialmente en análisis matemático. El descubrimiento de Russell significó entonces una verdadera crisis en toda la matemática, pues si algo tan simple y natural como la noción de conjunto era contradictoria ¿cómo podía asegurarse la corrección de conceptos más complejos? Es precisamente a causa de esta crisis que a principios del siglo XX se planteó la necesidad de revisar los fundamentos de la matemática.
Ante la crisis provocada por el descubrimiento de Russell hubo inicialmente dos reacciones. Por una parte, el propio Bertrand Russell propuso rescatar el programa de Frege introduciendo en él las modificaciones que fueran necesarias para evitar todas las contradicciones posibles. Este programa fue extensamente expuesto en la obra Principia Matemática, que Russell escribió junto a Alfred Whitehead y cuyo primer tomo se publicó en 1910.
Otra reacción, contemporánea de la anterior, fue encabezada por el matemático holandés L.E.J. Brouwer. Según Brouwer era imposible evitar las contradicciones en la teoría de conjuntos y cualquier intento de reparar el sistema de Frege estaba condenado al fracaso, pues todas las contradicciones nacían simplemente de la introducción del infinito en acto. Brouwer proponía descartar la teoría de Cantor y retornar a una matemática finitista en la que el infinito, tal como quería Aristóteles, fuera inalcanzable.
Más aún, Brouwer sostenía que sólo puede decirse que un objeto matemático existe si se puede dar una receta (una serie finita de instrucciones, es decir un algoritmo) que permita construirlo en una cantidad finita de pasos a partir de los números naturales.
Un ejemplo de algoritmo:
Paso 1: asígnese al número x el valor 2.
Paso 2: asígnese a x un nuevo valor, el que resulta de promediar el valor actual de x con el valor de 2/x (2 dividido por x).
Paso 3: repítase el paso anterior 10 veces más.
Cuantas más veces se aplique el paso 3, más se acercará el valor de x al de la raíz cuadrada de 2. El algoritmo, entonces, permite construir aproximaciones sucesivas de ese número.
Brouwer decía también que sólo tiene sentido definir una propiedad si al mismo tiempo se da un método algorítmico para verificar en una cantidad finita de pasos si un objeto cumple o no esa propiedad.
Hacia 1920 el programa de Russell comenzó a desmoronarse, especialmente a causa de ciertos axiomas que éste se vio obligado a incluir, pero cuya validez resultaba ser especialmente dudosa. A causa de ello, la escuela de Brouwer comenzó a dominar el pensamiento matemático y como consecuencia la teoría de Cantor comenzó a estar en peligro de ser eliminada. Fue entonces cuando entró en escena David Hilbert.
Hilbert fue desde siempre amigo y defensor de Cantor y bajo el lema “del paraíso que Cantor creó para nosotros nadie podrá expulsarnos” decidió contrarrestar las ideas de Brouwer. Además de gran matemático, Hilbert era un gran político y por eso decidió crear una filosofía de la matemática que diera cabida al infinito en acto pero que al mismo tiempo pudiera ser aceptada por los intuicionistas, es decir por Brouwer y sus seguidores.
Los intuicionistas, dijimos, exigían que todo objeto matemático fuese construido mediante un algoritmo y que toda propiedad fuera verificada asimismo algorítmicamente. La idea central de Hilbert fue llevar esta exigencia algorítmica, de los objetos y sus propiedades, a los razonamientos.
Para Hilbert toda teoría matemática debía fundarse en axiomas, que son afirmaciones que se aceptarían como verdaderas. Todas las demás verdades de la teoría se deducirían de los axiomas mediante razonamientos o demostraciones. Estos razonamientos debían ser finitistas al estilo intuicionista, es decir, debía existir un algoritmo (una receta) que, en una cantidad finita de pasos, permitiera determinar si un razonamiento es válido o no. En palabras modernas, debería ser posible programar una computadora de tal modo que fuera capaz de decidir si un razonamiento es correcto o no.
Los axiomas podían hablar del infinito en acto, de totalidades infinitas acabadas y completas, siempre que los razonamientos para deducir otras verdades a partir de ellos fueran finitistas y siempre que, además, por esos mismos razonamientos finitstas se pudiera demostrar que no habría paradojas o contradicciones.
El Programa de Hilbert se proponía entonces refundar la matemática bajo estas especificaciones. Y tan afortunada fue la idea de Hilbert que, como ya dijimos, en 1930 los intuicionistas finalmente “se rindieron” y aceptaron su programa. Pero en 1930 fue también cuando Gödel demostró que el Programa de Hilbert era irrealizable al probar (y ése es el enunciado del Teorema de Incompletitud) que los métodos finitistas que Hilbert proponía son incapaces de demostrar todas las verdades matemáticas. En aquel dramático septiembre de 1930 el Teorema de Gödel marcó un punto crucial en la historia de la lógica matemática. Sus consecuencias han sido llevadas, no siempre justificadamente, a la filosofía, la sociología y otras ramas del saber muy alejadas de su ámbito original.
Notas:
[1] La ciudad de Königsberg ya no es alemana, ni se llama Königsberg, en la actualidad la ciudad es rusa y se llama Kaliningrado.
[2] El río se llama Pregel y en él, cuenta la historia, hay dos islas y siete puentes: un puente conecta las dos islas entre sí, dos puentes más conectan a la isla menor con cada una de las dos orillas del río, otros dos puentes conectan a la isla mayor con una de las orillas del río y los últimos dos conectan a la isla mayor con la otra orilla del río. El problema pide hallar un camino que recorra los siete puentes de Königsberg, una vez cada uno sin repetir. Leonhard Euer demostró que esa tarea es irrealizable.
[3] Había también argumentos teológicos para sostener esta idea, según estos argumentos el infinito es un concepto solamente accesible para Dios e inalcanzable para la mente finita de los humanos.
[4] El problema en el que trabajaba Cantor está bien descripto en Ferreirós y Grattan-Guiness. En último dice en su libro que el problema en el que trabajaba Cantor era muy relevante, aquí nos permitimos disentir respetuosamente con esa opinión pues entendemos que hay varias razones para afirmar que el problema era menor, es probable que al dar su opinión Grattan-Guiness se deje llevar por su admiración hacia Georg Cantor.
[5] “Fui llevado por la lógica de mis investigaciones a romper con tradiciones que había aprendido a venerar”, escribió Cantor en 1883.
[6] Observemos que el conjunto de todos los conjuntos es un miembro de sí mismo (pues al ser él mismo un conjunto es miembro del conjunto de todos los conjuntos). La contradicción, conocida como la Paradoja de Russell, surge al considerar los conjuntos que no se tienen a sí mismos entre sus propios miembros. Razonando a partir de estos objetos Russell llega a la conclusión de que la noción de conjunto que usa Frege (que es una elaboración más precisa de la que usan Cantor y Dedekind) es contradictoria.
Suscribirse a:
Entradas (Atom)