jueves, 3 de marzo de 2011

Qué dice el teorema de Gödel


Euclides basó toda la geometría griega en cinco postulados:

1. Por dos puntos solo pasa una recta.
2. Un segmento se puede prolongar indefinidamente.
3. Dados un punto y un radio, solo se puede trazar una circunferencia.
4. Todos los ángulos rectos son iguales.
5. Por un punto exterior a una recta sólo pasa una paralela.

Durante mucho tiempo se pensó que el quinto postulado era superfluo, y que debería poderse deducir de los anteriores. Hoy sabemos que es necesario para definir la geometría plana. Con un quinto postulado que diga que no hay ninguna paralela tendremos la geometría esférica (cerrada) y con uno que diga que hay más de una tenemos la geometría hiperbólica (abierta).

Una geometría con solo los primeros cuatro postulados es incompleta. La pregunta que sigue es sugerente: ¿Podemos saber si la geometría con los cinco postulados es completa? Es decir, ¿no será posible que en algún momento haya una proposición que no se pueda deducir (como cualquier versión del quinto postulado a partir de los cuatro anteriores) y que deba añadirse a la lisa de postulados? En ese caso, la geometría se dividiría otra vez, según se afirme o se niegue esa proposición.

La respuesta de Gödel es inquietante: Cualquier sistema formal consistente (que no contenga contradicciones) que permita describir la aritmética será necesariamente incompleto. Siempre habrá afirmaciones que se puedan expresar en el lenguaje del sistema cuya veracidad o falsedad no se puedan demostrar en ese sistema.

Demostrar una afirmación (o su negación) significa que, manipulando los símbolos del sistema según sus reglas, se puede construir tal afirmación (o su negación). Podría ser posible demostrar esa afirmación (o su negación) en otro sistema formal, pero ese otro sistema tendría, según el teorema, sus propias proposiciones indemostrables dentro de él.

Gödel demuestra su teorema haciendo ver que en un sistema formal T que reúna las características pedidas es posible enunciar una proposición X que diga lo siguiente: "La proposición X no es demostrable dentro del sistema T". Si la proposición X fuera demostrable, tendríamos una contradicción (sería demostrable porque la hemos demostrado, y no demostrable porque es lo que dice la proposición). Pero como no es demostrable, la proposición es cierta, porque dice justamente eso.

El teorema de Gödel dice, entonces, un par de cosas más. La primera es que existen proposiciones ciertas cuya veracidad no es demostrable dentro del sistema. La segunda es que hay que distinguir entre proposiciones bien construidas dentro de un sistema (las que se demuestran) y verdades deducidas fuera del sistema.

La veracidad de la proposición X se ha establecido fuera del sistema T. Se suele referir a esto como "saltar del sistema". Podemos ahora añadir esa proposición X al conjunto de axiomas del sistema T, pero entonces el sistema se habrá convertido en otro sistema, el T', que tendrá su propia proposición indecidible (indemostrable) X' que dirá "X' no puede demostrarse dentro del sistema T'.

Así pues tenemos que los sistemas formales que puedan describir los números serán necesariamente incompletos. Habrá proposiciones indecidibles. Las matemáticas no pueden ser completas.

No es el caso de la geometría euclidiana, que puede axiomatizarse para ser completa.

15 comentarios:

  1. En el Logicomix (a propósito de la viñeta del inicio de esta entrada) explican todo esto muy bien. La verdad es que es una lectura más que recomendable. Pobre Hilbert.

    ResponderEliminar
  2. No es el caso de la geometría euclidiana, que puede axiomatizarse para ser completa

    Odio la geometría euclidiana, ha condicionado todo, seres imaginarios (recta rectilínea e ingrávida, plano sin pliegues, punto infinitesimales, ...) ideas químicamentes puras, etéras e inexistentes propias de un filósofo.
    La odio.

    ResponderEliminar
  3. eulez:

    Bienvenido por estos lares. Gracias por la referencia.

    JL Salg:

    Pobre geometría euclidiana. Si es bastante inofensiva.

    ResponderEliminar
  4. Me parece que es importante dejar bien en claro que es un teorema matemático, sino después vienen los amigos de la New Age a hacer sus interpretaciones.

    Aprovecho a recomendar, al que le interese el tema, el libro "Gödel para todos": http://godelparatodos.blogspot.com

    ResponderEliminar
  5. Alejandro:

    Gracias por la referencia. Justamente tengo pensada una continuación sobre lo que no dice el teorema de Gödel.

    ResponderEliminar
  6. Gracias por el post y a los comentadores por las referências (no conocía e incluyo entre futuras lecturas el "Gödel para todos"; en Logicomix todavia no encontré algo sobre Gödel).

    Soy un no-matemático interesado en profundizar la comprensión sobre el teorema. Aprovecho la oportunidad para indicar otras obras:

    * Gödel, Escher, Bach (Douglas Hofstadter)
    Ganó el premio Pulitzer en 1980 (!). El tema mayor son los "strange loops" que hay en los dibujos de Escher, en fugas y canones de Bach, y en la estratégia por detrás de la prueba de Gödel que derrumbó a la presunta completud de los Principia Mathematica de Russel y Whitehead. Leo aún por la p. 112 de 742, donde no se fué fundo en el teorema, pero hasta aquí ya es fascinante. Debe haber una traducción al español; sé que hay una al portugués.

    * Gödel's proof (Nagel & Newman)
    Libro pequeño, especie de exegesis. Muy detallado en el principio - permite a un no iniciado comprender que es un sistema logico. Pero cuando llegaba cerca de tratar del teorema, el detalle desapareció (y llevó mi paciencia junto, lamentablemente). De toda manera, el echo de que Hofstadter le tiene al libro en alta cuenta es una credencial.

    Saludos,
    Vinícius Kern
    http://kern.ispeople.org

    ResponderEliminar
  7. Me acuerdo de un cartoon muy a proposito de la estratégia de Gödel para llegar a la prueba de la Incompletud:
    http://www.thetribe.com.br/wp-content/uploads/2010/11/genio.jpg

    También en Gödel, Escher, Bach hay una historia (Little Harmonic Labyrinth) con argumento semejante.
    Saludos.

    ResponderEliminar
  8. José Luis,

    Una explicación sobre lo que no es sí que hace falta. No es infrecuente encontrarse con gente que saca el teorema del ámbito de las matemáticas y lo aplica a las cosas más absurdas como, por ejemplo, para refutar a las matemáticas y a la ciencia!

    Saludos y felicitaciones por la entrada ;)

    ResponderEliminar
  9. Vinícius:

    Bem-vindo ao blog. Gracias por traer a colación el libro de Hofstadter. Se lo recomiendo encarecidamente a cualquiera que nos lea. Ya hablé de él en esta otra entrada sobre el holismo y el reduccionismo:

    http://todoloqueseaverdad.blogspot.com/2009/03/holismo-y-reduccionismo.html

    Polarizador:

    Prometo esa otra entrada en breve. Tengo la misma percepción sobre esos abusos que tú.

    ResponderEliminar
  10. Vinícius Kern: Sí hay traducción al español. De hecho hay dos. Yo recomiendo la de Tusquets, porque es más cuidada.

    Gracias, José Luis, Por compartir este fascinante tema. Estuvo a punto de ser el tema de mi tesis de maestría.

    Un abrazo

    ResponderEliminar
  11. La completitud, en Lógica, puede hacer referencia a dos cosas: 1) a que los postulados geométricos hacen referencia a TODAS las «cosas» geométricas únicamente o 2) a que los postulados geométricos hacen referencia a TODAS las verdades geométricas.

    Si es lo primero, efectivamente, puede crearse una axiomatización donde los postulados sólo hagan referencia a las «cosas» geométricas.

    Si es lo segundo, entonces no se puede tener una axiomatización que garantice la completitud: resulta que el quinto postulado garantiza la existencia de 1, 2, 3, ..., n líneas paralelas todas entre sí. Eso conlleva a los axiomas de Peano y, finalmente, a la aritmética. Entonces, en el segundo sentido de la palabra «completitud» la geometría también es necesariamente incompleta.

    Hace falta especificarlo. En Lógica se ha optado por distinguir la completitud de 1) como «suficiencia» y la completitud de 2) como «completitud» tal cual.

    Saludos.

    ResponderEliminar
    Respuestas
    1. Bienvenido al blog, Kurt Friedrich Gödel.

      Gracias por la aclaración, aunque no sé si he entendido bien el punto 1). ¿Qué pasa si tienes unos axiomas que hacen referencia a todas las cosas geométricas, pero se pueden interpretar también de otra manera? ¿Cómo sabemos cuáles son todas las cosas geométricas?

      Eliminar
    2. Es sencillo. Basta con definirlo, es decir, con definir lo que es o no geométrico.

      Puede que a los axiomas de Euclides se agregue el axioma «todo aquello deducido a partir de los axiomas de Euclides es geométrico» y con eso es suficiente.

      Así se resuelve el punto 1).

      Sin embargo, aun con los cinco axiomas de Euclides y el sexto que propongo no podría garantizarse que todas las verdades geométricas sean deducibles.

      Porque es posible deducirse que una cosa hace referencia a lo que es geométrico, pero demostrar si es o no verdadero es otra cosa que no es geométrica. Con ello quiero decir que la «suficiencia» de los axiomas de Euclides no garantiza la «completitud» de los mismos: no garantiza que éstos deduzcan todas las verdades geométricas, sino que deducen sólo cosas geométricas (pueden ser verdaderas o falsas).

      Saludos.

      Eliminar