12.6.09

El ABCDEF del Teorema de Gödel

A) A principios del siglo XX (en buena medida a causa del descubrimiento de paradojas en la Teoría de Conjuntos) se desata en la Matemática una polémica acerca de qué tipo de razonamientos son aceptables. La polémica gira especialmente en torno a la cuestión de si son válidos los razonamientos que involucran totalidades infinitas.

Para zanjar la cuestión, en la década de 1920 David Hilbert propuso el Programa Formalista (hoy también llamado Programa de Hilbert). La propuesta consistía en elegir axiomas para la Aritmética (que es la teoría que habla de la suma y el producto de los números enteros positivos) de tal modo que toda verdad (y ninguna falsedad) de la teoría pudiera deducirse de esos axiomas.

¿Qué razonamientos serían válidos en esas deducciones? Hilbert proponía una verificación mecánica de los razonamientos: debería ser posible, podemos decir en términos modernos, programar una computadora de tal modo que sea esa computadora (mediante procedimientos puramente mecánicos) la que decida si el razonamiento es válido o no. Esta corroboración mecánica nos daría un criterio objetivo para determinar la validez de un razonamiento.

Conviene destacar aquí que Hilbert no decía que los razonamiento matemáticos debían transformarse en (o que debían ser) puras manipulaciones de símbolos, decía que esas manipulaciones debían servir para verificar la corrección de los razonamientos que ("creativamente") realizaban los matemáticos en su trabajo.

La teoría elegida por Hilbert era la Aritmética porque a partir de ella puede construirse todo el resto del edificio matemático. Una base sólida para los razonamientos aritméticos daría una base sólida para toda la matemática.

B) En 1931 Kurt Gödel demostró que si se eligen axiomas para la Aritmética de modo que los razonamientos que demuestran afirmaciones a partir de ellos siguen lo establecido por el programa de Hilbert entonces siempre habrá verdades que son indemostrables a partir de los axiomas elegidos. (Esta es la versión semántica del teorema de Gödel, basada en la noción de verdad. Hay una versión sintáctica, pero es demasiado extensa de explicar en este breve resumen.)

De alguna manera, el teorema de Gödel nos dice que si elegimos un criterio objetivo (y mecánico) para verificar la validez de los razonamientos, entonces habrá verdades cuya demostración está más allá de los razonamientos aceptados por esos criterios.

[Una suposición implícita en todo esto es que la Aritmética es lógicamente consistente, es decir, que no es contradictoria en sí misma. Si no fuera consistente, toda afirmación sería demostrable. La consistencia de la Aritmética, si es que lo es, es una verdad cuya demostración está más allá de los razonamientos verificables mecánicamente. En general, se acepta que la consistencia de la Aritmética es una "verdad evidente", pero lo mismo se creía de la Teoría de Conjuntos antes de que Russell expusiera su paradoja.]

C) Para que podamos traducir los razonamientos aritméticos a un lenguaje capaz de ser manipulado por una computadora, las afirmaciones deben estar escritas en un lenguaje preciso, con símbolos y reglas para manipularlos que estén fijados de antemano. Entre estos símbolos habrá los que representen operaciones numéricas (suma y producto), operaciones lógicas (conjunción, negación, etc.) y otros.

D) En el corazón de la demostración de Gödel está la idea de "numeración de Gödel": a cada afirmación aritmética (verdadera o falsa) se le asigna un número. Por ejemplo a "2 es par" podría corresponderle el número 23.450, a "7 es par" podría corresponderle el 34.508.

En realidad los números de Gödel se asignan de una manera específica. La afirmación primero es traducida al lenguaje formal y luego se calcula el número mediante operaciones claramente definidas. En general, además, los números que se obtienen tienen varias decenas de cifras. Los ejemplos que se mencionan más arriba sirven solamente para ejemplificar la idea.

Fijado un conjunto de axiomas que cumpla las condiciones del programa de Hilbert, el conjunto de todos los teoremas que se deducen de ellos forma un conjunto bien definido de afirmaciones. Y los números de Gödel de estas afirmaciones forman un conjunto bien definido de números. La primera parte de la demostración del teorema de Gödel (que no desarrollaremos aquí) consiste en ver que esos números (que en principio están definidos por la propiedad "lógica" de ser los números de Gödel de afirmaciones demostrables) tienen en común una propiedad aritmética expresable en términos de la suma y el producto.

Es decir, así como las propiedades "Ser un número par" o "Ser un número primo" se pueden definir en términos de la suma y el producto, del mismo modo la propiedad de "Ser el número de Gödel de un teorema" es una propiedad expresable en términos de la suma y el producto (como si dijéramos que los números de Gödel de los teoremas son exactamente aquellos que son primos que se obtiene sumando tres números cuadrados, la propiedad es mucho más compleja, pero ésa es la idea general).

E) Supongamos ahora que a la afirmación "23.444 es un número par" le correspondiera el número de Gödel 23.444. La afirmación diría entonces "Mi número de Gödel es par.

¿Es esto una casualidad? No. En realidad puede probarse que para toda propiedad expresable en términos de la suma y el producto existe una afirmación cuyo significado es "Mi número de Gödel cumple esa propiedad".

Explico un poco la idea de cómo se hace esto. Llamemos d(x) a la función definida de este modo (función diagonal, la llamaba Gödel): si n es el número de Gödel de la afirmación "x cumple la propiedad P", entonces d(n) es el número de Gödel de la afirmación "n cumple la propiedad P".

Tomemos entonces la afirmación "d(x) cumple la propiedad P" y sea m su número de Gödel. Entonces, por definición de la función diagonal, d(n) es el número de Gödel de "d(n) cumple la propiedad P". Es decir, la afirmación dice: "Mi número de Gödel cumple la propiedad P".

F) Como "Ser el número de Gödel de una afirmación demostrable" es expresable en términos de la suma y el producto, entonces existe una afirmación cuyo significa es "Mi número de Gödel es el número de Gödel de una afirmación demostrable", más brevemente, "Yo soy una afirmación demostrable". Como la negación es expresable entonces existe una afirmación expresable en términos de la suma y el producto cuyo significado es: "Yo no soy demostrable".

Si la afirmación es falsa, entonces sería demostrable. Esto no es posible, pues sería una falsedad demostrable. Luego, es verdadera y entonces no es demostrable. Es decir, es una verdad no demostrable, como queríamos probar.

Ésta es la idea general del Teorema de Incompletitud de Gödel (al menos en su versión semántica).

No hay comentarios.: