Teorema de incompletitud de Gödel


Kurt F. Gödel, en «Sobre las proposiciones formalmente indecidibles de los Principia Mathematica y sistemas afines» [paráfrasis]:

«Existen argumentos lógicos imposibles de ser deducidos verdaderos o falsos; entre ellos, la coherencia de dichos razonamientos.»

La existencia verdadera o falsa de algo (por ejemplo, las piedras; al contrario, las hadas), no implica que la misma sea demostrable así, ni que deba o no tenerse fe en cualquiera de estas posibilidades.

·

La creatividad surge de hallar –pensando diferente del resto– ideas absurdas, para así nuevamente pensarlas y darles coherencia.

Ahí la importancia de la Lógica: porque sólo con ella es posible tanto hallar los absurdos como obtener la coherencia.

·

miércoles, 12 de diciembre de 2012

DEL TEOREMA DE GÖDEL


Esta entrada participa en la IV Edición del Carnaval de Humanidades alojado por Kurt Friedrich Gödel en el blog Literatura es aprehender a la realidad.] 
 
La importancia del teorema de Gödel es notable al conocer y desenvolverse en la Lógica y sus implicaciones. Sus términos y explicación así como tales implicaciones son simples, la demostración del teorema es de alto nivel. De allí la importancia de Gödel: demostró una situación que está al alcance de todos entender pero que no es tan evidente como parece.

En ese sentido, puesto que su demostración es difícil de entender (dados los medios que ocupa que son de Matemática avanzada), sólo cabe explicar de qué trata el teorema sin ahondar en cómo resolver un escollo que ha sido librado por otras personas (Kurt Gödel, George Boolos, entre otros que han demostrado el teorema). Esto es factible totalmente: haciendo una analogía con los autos, se pueden entender aspectos automotrices sin ser Ingeniero Automotriz. Esta es la pretensión: entender el teorema de Gödel sin tener que acudir mas que a ciertas ideas y ejemplos que no corresponden directamente con la demostración.

En 1930, Gödel se doctoraba con una tesis que publica posteriormente como artículo en una revista de Matemática (Monatsheft der Mathematik und Physik) y donde muestra que en la Lógica toda proposición válida es deducible. Una vez dada la base de la Lógica y la suficiencia de su validez fue posible demostrar lo que hoy se conoce como el teorema de Gödel y que aparece en su Sobre las proposiciones formalmente indecidibles de los Principia Mathematica y sistemas afines: Todo sistema formal coherente es necesariamente incompleto. En este mismo trabajo redacta un segundo teorema (aparte de los otros diez que ayudan a obtener tanto el primero como el segundo aquí expuestos) aún más inquietante: Todo sistema formal coherente no puede demostrar su coherencia por sus propios medios.

Hasta el momento no se ha definido nada sobre lógica, coherencia, completitud, etc. Así que la explicación procederá de aquí. Un ejemplo bastará para entender la terminología al respecto. Vale la pena aprehender esto para entender los alcances de nuestro propio pensamiento (que se rige por la Lógica).

Tomando un caso cotidiano, el cubo Rubik, creado en la década de los ochenta por el húngaro del mismo apellido, el atento jugador sabe que partiendo de la configuración con un sólo color para cada cara del cubo y revolviendo los colores posteriormente se debe llegar a la configuración inicial. Es fácil entender que no es imposible llegar a la configuración de inicio si una vez ya se encontraba allí. Este juego es el ejemplo más claro (y cotidiano, así como simple) de un concepto fundamental: es un ejemplo de sistema formal. Los sistemas formales son en el título del trabajo de Gödel los nombrados sistemas afines a los Principia Mathematica.

Un sistema formal es símbolos, reglas para manipular los símbolos, ambos que permiten obtener fórmulas. Una fórmula, en sentido análogo a cualquier idioma, es equivalente a una oración. Por ejemplo, los símbolos para cierto idioma son las palabras del vocabulario, las reglas de manipulación de símbolos son la gramática de dicho idioma y como ya se había mencionado, las fórmulas son las oraciones. Este ejemplo no es tan cotidiano y no es tan sencillo, de allí que la explicación que se pretende no parta de una idea como esta. Utilizando al cubo Rubik, los símbolos son los colores, las caras y el cubo mismo. Las reglas son todos los movimientos físicamente posibles, es decir, los giros del cubo. Las fórmulas son cada una de las formas que puede tomar el cubo; la configuración inicial de un cubo Rubik es una de muchas fórmulas (configuraciones del cubo).

Este ejemplo es más simple porque no requiere de la interpretación social de las lenguas, ni de conocimientos previos en Matemática, sino de conocimientos laicos y neutros además de empíricos que son accesibles a todos. Entendiendo lo que es un sistema formal (siempre es fácil remitirse al cubo para entender lo que es un sistema formal), cabe decirse lo que Lógica significa. Para ello se tiene otro aspecto del cubo: si bien la idea inicial es revolverlo y llegar a la configuración inicial, en principio la idea se puede ampliar para obtener diversas configuraciones a manera de reto (cruces, mosaicos, etc.). Con este nuevo aspecto del cubo la idea de sistema formal es adecuada para el ejemplo. Retomando a los idiomas, su intención inicial puede ser expresar exclusivamente una frase pero su utilidad radica en obtener una gran variedad de configuraciones, de frases.

Entonces, la Lógica sería, con el cubo, la aplicación de series de pasos que se tienen que seguir para llegar a las configuraciones. A la series de pasos (giros) que se tienen que seguir para llegar a una configuración del cubo se les llama, con terminología de Lógica, deducción. En este punto es fácil ver que la conclusión de la tesis doctoral de Gödel es cierta para el cubo, recordándola, todo proposición válida es deducible, y trasladándola al cubo, toda configuración válida del cubo es obtenible por giros.

Parece algo obvio, pero no lo es. Y es que las demostraciones de Gödel son un claro ejemplo de ideas simples que involucran un grado de complejidad amplio. Sin acudir a la demostración, es fácil de ver esto para el cubo. La palabra válida está resaltada porque sólo son válidas las configuraciones que admiten un cubo, los seis colores en el cubo, y giros. Así son validas tanto configuraciones físicamente comprobables como configuraciones imaginables que cumplan con estas características en su fundamentación. En la Lógica las proposiciones válidas están determinadas de un modo similar, con características bien conocidas (mismas que se expresan en los Principia Mathematica de Bertrand Russell).

Es necesario poner en contexto el trabajo de Gödel en la década de los años treinta. David Hilbert propone que la Matemática pueda ser obtenida como un sistema formal coherente, completo y deducible. Si tomamos al cubo, esto equivale a proponer un juguete del tipo cubo Rubik que pueda tener una y sólo una configuración cada vez entre movimientos (coherencia), que cumpla con todas las configuraciones válidas (completitud) y que cada una de estas configuraciones (las imaginadas y las físicamente observables) sean obtenibles por giros (deducibilidad). En esencia parece que es posible obtener un cubo de este tipo. Lo mismo se pensaba para la Matemática: una Matemática donde cada uno de sus aspectos no se contradigan entre sí (coherencia), una Matemática donde todos los teoremas imaginables válidos sean posibles (completitud) y una Matemática donde todos los aspectos de ésta sean deducibles (deducibilidad).

Gödel demuestra que ninguna de estas intenciones es posible a la vez que las demás. El primer teorema de Gödel dice que todo sistema formal coherente es necesariamente incompleto. Aplicado al cubo, todo cubo que implique tener una y sólo una configuración cada vez necesariamente implica que no todas las configuraciones válidas (como se definieron las válidas) son obtenibles (por giros). Una forma de ver esto es únicamente imaginando configuraciones del cubo que en efecto son imposibles de formarse a partir de la configuración inicial pero que admiten los seis colores y los giros, por ejemplo la disgregación de todos los colores en todas las caras, es decir, que cada cara tenga cada uno de los colores sin ser adyacentes entre sí. Es más, es imposible tener configuraciones donde dos colores no sean adyacentes entre sí. Esto muestra la incompletitud del cubo, o sea, no todas las configuraciones válidas son obtenibles.

Cabe notar lo siguiente: las configuraciones propuestas son refutables. Más claro, que sean refutables significa que con Lógica se puede decir si son imposibles o no. Sin embargo, no las podemos construir. En ello radica la incompletitud. Se puede decir si son posibles o no, pero a pesar de ello NO se pueden obtener. Esta consecuencia es crucial para la Matemática entera. Hay teoremas que si bien son verdaderos, no se pueden deducir. Así, Gödel demuestra que para todo sistema formal (incluyendo la Matemática y el cubo Rubik) hay aspectos o configuraciones que aún siendo verdaderos o verdaderas no se pueden deducir u obtener.

Estamos acostumbrados a que todas las verdades matemáticas son deducibles. El teorema de Pitágoras tiene deducción (y por tanto demostración), el teorema de Tales tiene deducción (y por tanto demostración), el número √2 se puede deducir (y por tanto demostrar) irracional, y aún así existen aseveraciones que son verdaderas y no tienen deducción (y por lo tanto tampoco demostración) en la Matemática. El problema es aún mayor: cada vez que un teorema imaginable y válido se propone, sólo se puede declarar 100% verdadero si tiene demostración. En ello se basa la importancia del primer teorema de Gödel. ¿Cómo saber qué proposiciones son de este tipo (indemostrables, no deducibles)? Según el teorema de Gödel, es imposible saberlo. ¿Por qué? Porque cualquier método para hallar teoremas de este tipo es una demostración de estos teoremas.

Retomando al cubo, ¿cómo saber qué configuraciones son de este tipo? En virtud del teorema de Gödel esto es imposible de saberse porque aún hallando “todas” (si es posible hallarlas) las configuraciones posibles, esto no garantiza que la configuración imaginada válida no pueda ser obtenida por otro método o algoritmo. Lo único que se garantiza son los métodos que no llegan a esta configuración. Aún más, se tendrían que conocer todos los algoritmos posibles para obtener configuraciones, situación que no es posible: tantos algoritmos como queramos son posibles.

Existe una salida que aún así se reduce al primer teorema de Gödel y es el segundo teorema de Gödel. Aquí es necesario remitirse a las configuraciones propuestas imposibles (la de colores disgregados y colores no adyacentes). Se sabe que son imposibles de formar pero esto no se demuestra construyendo todas las configuraciones posibles sino con métodos externos al cubo. Esto es, se puede demostrar que son imposibles por otros medios que no impliquen girar al cubo sino, por ejemplo usar teoremas de Topología. La Topología es un sistema formal externo (ajeno) al cubo y es posible que demuestre algo indemostrable para el cubo. No obstante la Topología para ser coherente (como dice Gödel) debe ser incompleta y el problema que queda resuelto para el cubo queda sin resolver para la Topología.

La Matemática es susceptible de esta situación. Para que la Matemática sea coherente tiene que ser incompleta y por lo tanto existen teoremas que no se pueden demostrar por medio de la Matemática sino con otros sistemas formales que igualmente son susceptibles de esto. Es el cuento de nunca acabar. Este es el segundo teorema de Gödel: todo sistema formal coherente no puede demostrar su propia coherencia por sus propios medios. Y es que demostrar la coherencia de un sistema formal implica que todos los teoremas no se contradigan entre sí.

Volviendo al cubo, demostrar que sólo se tiene una y sólo una configuración cada vez en el cubo implica obtener “todas” la configuraciones del cubo para saber si no se interponen entre sí, situación que en virtud del primer teorema es imposible (porque no se pueden obtener todas las configuraciones sólo girando el cubo). La Matemática llega a lo mismo: no se puede demostrar que todos los teoremas verdaderos de la Matemática no se contradicen entre sí porque simplemente (como ya se había dicho) no se puede deducir todos los teoremas de la Matemática. La coherencia de los sistemas formales en efecto es indemostrable por los métodos del mismo sistema.

Todo esto tiene una consecuencia muy importante: si se siguen los medios de la Lógica siempre es necesario recurrir a medios diversos y externos para demostrar todo lo que se desee demostrar. Debido a ello, si el cubo Rubik es indemostrable en una de sus partes, se recurre a otro medio (que incluso puede inventarse) para explicar y demostrar aquel aspecto indemostrable del cubo. Como este otro medio debe ser un sistema formal (para que sea coherente), se tiene algún aspecto nuevamente indemostrable del mismo y se recurre nuevamente a otro medio. ¿No es así como evoluciona el saber humano?

Hallamos el saber desde lo más sencillo y al no poder demostrar ciertas situaciones, el nivel de sofisticación de los medios empleados para demostrar es mayor y el conocimiento al respecto también. Así del cubo se pasa a la Topología (que en efecto es más compleja). En casos más profundos, de la Aritmética se pasa al Álgebra, del Álgebra a la teoría de cuerpos, etc. En la ciencia ocurre algo similar. De la ley de gases ideales a las ecuaciones cúbicas, de las ecuaciones cúbicas al concepto de fugacidad y sus métodos, etc.

El pensamiento lógico implica la incompletitud de los medios, la incompletitud implica saber más de otros medios y se garantiza la necesidad de saber ilimitadamente si se desean demostrar todos los teoremas verdaderos de TODO. 

3 de Noviembre de 2011
 
 

3 comentarios:

  1. Excelente explicación. Lo que más cuesta es recurrir a ejemplos y analogías, sin caer en la superficialidad. Es difícil, pero esta entrada se puede decir que es completa.

    ResponderEliminar
  2. Muy buena explicación. Lo más cerca que he estado de comprenderlo. Tendré que trabajarlo más.
    Muchas gracias.

    ResponderEliminar
  3. Ciertamente muy bien explicado para los legos interesados como yo. Muy buena la analogía del cubo. Nos viene bien a los que necesitamos pensar en algo físico para entender las cosas. :) Gracias

    ResponderEliminar