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.

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.

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.

Sobre libros...

    Libros

      Ninguno de los libros de este mundo
      Te aportará la felicidad,
      Pero secretamente te devuelven
      A ti mismo.
      Allí está todo lo que necesitas,
      Sol, luna y estrellas,
      Pues la luz que reclamas
      Habita en tu interior.

      Ese saber que tú tanto buscaste
      Por bibliotecas resplandece
      Desde todas las lágrimas,
      Puesto que ese libro es tuyo ahora.

Creer en ti, en la realización de tus sueños...

    Demian (fragmento) de Herman Hesse

      Y me contó la historia de un muchacho enamorado de una estrella. Adoraba a su estrella junto al mar, tendía sus brazos hacia ella, soñaba con ella y le dirigía todos sus pensamientos. Pero sabía, o creía saber, que una estrella no podría ser abrazada por un ser humano. Creía que su destino era amar a una estrella sin esperanza; y sobre esta idea construyó todo un poema vital de renuncia y de sufrimiento silencioso y fiel que habría de purificarle y perfeccionarle. Todos sus sueños se concentraban en la estrella. Una noche estaba de nuevo junto al mar, sobre un acantilado, contemplando la estrella y ardiendo de amor hacia ella. En el momento de mayor pasión dio unos pasos hacia adelante y se lanzó al vacío, a su encuentro. Pero en el instante de tirarse pensó que era imposible y cayó a la playa destrozado. No había sabido amar. Si en el momento de lanzarse hubiera tenido la fuerza de creer firmemente en la realización de su amor, hubiese volado hacia arriba a reunirse con su estrella.

      (...) Las cosas que vemos son las mismas cosas que llevamos en nosotros. No hay más realidad que la que tenemos dentro. Por eso la mayoría de los seres humanos viven tan irrealmente; porque creen que las imágenes exteriores son la realidad y no permiten a su propio mundo interior manifestarse. Se puede ser muy feliz así, pero cuando se conoce lo otro, ya no se puede elegir el camino que elige la mayoría.