martes, 8 de marzo de 2011

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.