^ (Parte 1)

Definición comentada de la operación de potenciación

La intención de esta breve serie de entradas es exponer la definición de la operación de potenciación tal como es aceptada universalmente por la comunidad matemática, agregando algunos comentarios que normalmente son omitidos en los textos. Hago la aclaración de que las limitaciones de Blogger me obligan a indicar la operación con el símbolo "^", aunque todos sabemos que usualmente se indica poniendo el exponente en tamaño pequeño y un poco elevado por sobre la línea de escritura.

El primer punto a tomar en cuenta es que la potenciación es una operación que se define por casos sucesivos, según el conjunto numérico en el que se encuentre el exponente. Iniciaré con un caso muy básico:

Caso 1: a^2 = a.a. (El número a puede ser cualquier número real.)

[René Descartes fue el primero, o al menos uno de los primeros, en usar esta notación.]

Pregunta: ¿Por qué a^2 es a.a? ¿Podría ser a^2 = a + a?

Respuesta: Que a^2 sea igual a a.a es sólo una convención de notación que, evidentemente, fue elegida porque resultaba útil (podemos conjeturar que el producto de un número por sí mismo aparecía muchas veces en los cálculos y eso justificó el uso de una notación específica para esa operación. La respuesta a la segunda pregunta es claramente que sí. Las notaciones matemáticas dependen muchas veces de elecciones arbitrarias que pudieron haber sido muy diferentes.

Pregunta: ¿Es un abuso de notación el usar el mismo símbolo ^ (en realidad, la notación del exponente) para (-2)^2 o para 3^2.

Respuesta: Obviamente, no. En ambos casos hablamos de multiplicar un número por sí mismo así que ¿por qué sería un abuso de notación? Si Ud. le hubiera planteado esa pregunta a Descartes, seguramente le habría tirado un borrador por la cabeza, como un par de siglos después haría otro francés, Galois, con un examinador que le hacía preguntas de ese estilo (claro que aquél borrador no era de madera como los nuestros, sino que era una esponja).

Caso 1 (ampliado): a^n = a.a....a (Donde a se repite n veces.)

El número a puede ser cualquier número real. El valor de n sólo puede ser un entero estrictamente positivo, es decir: 1, 2, 3, 4,... ya que sólo para esos valores puede hablarse de "cantidad de veces". Puee darse una definición inductiva de este caso, pero es sólo una formalización más elegante de la misma idea.

Propiedades:

Importante: Hasta ahora sólo hemos definido el cálculo de potencias con exponente entero estrictamente positivo y, como consecuencia, las propiedades se refieren sólo a ese caso. En el punto 3 el valor de a debe ser distinto de cero, en los demás puede ser cualquier número real.

1. (a^n).(a^m) = a^(n + m)

2. (a^n)^m = a^(n.m)

3. a^n/a^m = a^(n - m). Esta propiedad vale (por ahora) solamente si n es estrictamente mayor que m, porque de lo contrario en el miembro derecho tendríamos una potencia que todavía no hemos definido. Obviamente a debe ser distinto de cero.

Pregunta: ¿Qué pasa con a^0?

Respuesta: Todavía no lo hemos definido, aparecerá en el caso siguiente.

Continuará...

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

(A la parte 8)

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.

(A la parte 7 - A la parte 9)

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.

(A la parte 6 - A la parte 8)

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.

(A la parte 5 - A la parte 7)

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)....

(A la parte 4 - A la parte 6)

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.

(A la parte 3 - A la parte 5)