La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Gödel en una cáscara de nuez: Primer Teorema de Incompletitud

Posted by Carlos en marzo 16, 2007

Tras haber visto anteriormente el corte diagonal de Cantor, podemos hacer ya una incursión en el terreno de los teoremas de incompletitud de Gödel. Para ello, hay que empezar por enmarcar el contexto en el que estos teoremas se formulan, tanto desde el punto de vista histórico, como desde el punto de vista formal. Con respecto a lo primero, hay que hacer mención sin duda a la enorme figura de David Hilbert, y en particular a su programa formalista. De acuerdo con la visión de Hilbert, todas las ramas de las matemáticas se podrían llegar formalizar en un sistema completo (en el que todo lo que fuera cierto fuera demostrable), consistente (en el que no se pudieran demostrar cosas falsas), y decidible (la verdad o falsedad de una afirmación matemática sería demostrable mediante un procedimiento mecánico bien definido). Esta última parte -la decibilidad- hace evidentemente referencia a la noción de algoritmo, que no obstante no estaba aún formalizada tal como la entendemos actualmente. Éste será precisamente el vínculo que nos permitirá enlazar los resultados de Gödel con los de Turing más adelante.

Fue en pleno apogeo del programa de Hilbert en el que Gödel presentó los teoremas de incompletitud que dieron al traste con el mismo. El marco formal en el que dichos teoremas se encuadran es el de la lógica de primer orden. En dicho marco empleamos predicados para razonar acerca de un conjunto de objetos. Mediante estos predicados podemos realizar afirmaciones sobre objetos concretos (por ejemplo, par(2), que podríamos interpretar como “2 es par”), o expresar afirmaciones más genéricas mediante el uso de variables y cuantificadores. Por ejemplo:

\forall x\left({\rm divisible}(x,6)\Rightarrow {\rm par(x)}\right)

Por supuesto, debemos disponer también de unos axiomas, que establezcan verdades básicas de partida, y un conjunto de reglas de inferencia que nos permitan demostrar la verdad o falsedad de una afirmación como la anterior. De hecho, si la ambición de Hilbert fuera factible, dada una afirmación cualquiera (y no sólo en el marco de la lógica de primer orden) se podrían aplicar de forma mecánica las reglas de inferencia hasta o bien demostrar dicha afirmación (en cuyo caso sería cierta) o su negación (en cuyo caso sería falsa). Gödel demostró que esto no es posible, ya que un sistema lo suficientemente complejo como para permitir expresar y demostrar verdades aritméticas sobre los números naturales (esto es, un superconjunto de la aritmética de Peano), será o bien inconsistente (en cuyo caso se podrá demostrar cualquier cosa), o incompleto (en cuyo caso habrá afirmaciones indemostrables e irrefutables).

La base de los teoremas de incompletitud es lo que se conoce como aritmetización, numeración de Gödel, o simplemente gödelización. Gödel definió un procedimiento que permite codificar una secuencia de símbolos en un número natural. Los detalles de como conseguir esto no son importantes en este momento, pero a grandes rasgos se basan en el hecho de que la descomposición en factores primos de un número es única. De esta forma, se puede asociar a cualquier fórmula lógica (o secuencia de fórmulas lógicas) F un número natural g(F). Esta posibilidad resulta crucial aquí, ya que es la que nos va a permitir expresar la auto-referencia y en última instancia aplicar el corte diagonal.

Una vez tenemos formulas y demostraciones codificadas mediante números naturales, es fácil expresar la noción de demostrabilidad mediante una fórmula lógica D(x,y), que interpretaremos como “x es el número de Gödel de una demostración de la fórmula cuyo número de Gödel es y“. Por lo tanto, una fórmula F será demostrable (cosa que indicaremos por P(x), donde x=g(F)) si tiene al menos una demostración, esto es:

P(x) \Leftrightarrow \exists y D(y,x)

Ya estamos listos para aplicar el corte diagonal. Definamos para ello la noción de auto-indemostrabilidad Q(x) como

Q(g(F))  \Leftrightarrow \sim\exists y D(y,g(F(g(F)))),

es decir, una formula F es auto-indemostrable si no se puede demostrar F(g(F)). ¿Qué ocurre cuando F=Q, esto es, es demostrable que no hay demostración para G=Q(g(Q))? Analicemos las posibilidades:

  • Supongamos que sí es demostrable, esto es, que P(g(G)) es cierto, y por lo tanto existe un y tal que D(y,g(G)) es cierto. En este caso, nótese que D(y,g(G)) = D(y,g(Q(g(Q)))). Sin embargo, que Q(g(Q)) sea cierto implica por su propia definición que no existe ningún y para el que D(y,g(Q(g(Q)))) sea cierto. Luego habríamos demostrado algo falso, y el sistema sería inconsistente.
  • Supongamos que no es demostrable. Volvamos entonces nuestra atención hacía su negación. Si existe un y tal que D(y,g(~G)) es cierto quiere decir que ~Q(g(Q)) es cierto, esto es, que existe un z tal que D(z,g(Q(g(Q)))) = D(z,g(G)) es cierto. Esto contradice nuestra suposición de partida de que G era indemostrable, y en cualquier caso produce una inconsistencia al haber una demostración de G y de ~G.

El razonamiento anterior puede ser algo farragoso, pero en esencia se reduce al hecho de que G afirma su propia indemostrabilidad. Si G es demostrable, entonces es falso y al haber demostrado algo falso nuestro sistema es inconsistente. Si su negación es demostrable, entonces por definición G es demostrable, con lo que el sistema es nuevamente inconsistente (ya que hemos demostrado algo y su negación). Por lo tanto, si el sistema es consistente, ni G ni ~G son demostrables, luego el sistema es incompleto.

Es importante notar el hecho de que en ningún momento se afirma que G sea cierta o no, sólo que ella y su negación son indemostrables si el sistema es consistente. Sin embargo, si analizamos la situación podemos llegar a la conclusión de que sí es cierta: desde nuestro punto de vista externo al sistema, está claro que no hay demostración de G, que es lo que G afirma, por lo que debe ser cierta. Que podamos percibir este hecho es uno de los argumentos más frecuentemente invocados para sostener que nuestra mente no es algorítmica, y por lo tanto negar la posibilidad de que pueda ser representada mediante un modelo computacional equivalente a una máquina de Turing. Esto merece comentario aparte en un futuro artículo.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Anuncios

7 comentarios to “Gödel en una cáscara de nuez: Primer Teorema de Incompletitud”

  1. Leí hace poco un ejemplo muy bueno para explicar ésto.

    Supongamos que tenemos un conjunto de libros en una biblioteca, y algunos de ellos son catálogos acerca de los propios libros de la biblioteca, pero por ejemplo, si un catálogo es sobre libros que tratan de cocina, tendrá que incluirse a si mismo, ya que el propio catálogo irá sobre cocina, ¿no?, hasta aquí bien, el problema viene cuando hacemos dos catálogos nuevos, uno para los libros que se incluyen a si mismos y otro para los que no. Todo parece muy sencillo, sin embargo, en el catalogo de los que no se incluyen a si mismos habrá que meter ese mismo catalogo, pero en el mismo momento en el que lo metamos, ya no deberá incluirse a si mismo (xD). Quiere decir que hay un problema en nuestra base, con el cual no tropezamos hasta que no llegamos a una contradiccion, ¿solución?, incluir un nuevo axioma que diga que los catálogos nunca podrán incluirse a si mismos, pero entonces habremos cambiado el sistema axiomático, y el nuevo sistema fallará por otro lado. Creo que esa era la idea, no se si ya conocerías el ejemplo xD, un saludo.

    P.D. Estaba preparando un articulo sobre el Teorema de la Incompletitud, pero creo que lo haré sobre otra cosa xD, esperaré impaciente el artículo sobre el segundo teorema, el que de verdad supuso un mazazo para las matemáticas (y sobre todo para los matemáticos) del momento.

  2. Carlos said

    Hola J. Antes de nada, si pensabas escribir sobre los teoremas de incompletitud, ¡hazlo! Es un tema muy interesante, sobre todo por las ramificaciones que puede tener en otros muchos campos. El tema no está agotado ni mucho menos. 🙂

    El ejemplo que comentas está en efecto muy relacionado, y de hecho es un ejemplo claro de corte diagonal: definimos S como el conjunto de todos los conjuntos que no se pertenecen a sí mismos. ¿Pertenece S a sí mismo? Es la denominada paradoja de Russell, y me encanta, ya que es la justificación para la teoría de tipos.

    Saludos.

  3. Tienes razón, escribiré sobre ello, por cierto me estoy leyendo un libro tremendamente interesante, se titula “El Enigma de Fermat”, y trata sobre todos los caminos por los que ha pasado la desmotración del “Último teorema de Fermat”, desde el teorema de Pitágoras hasta la conjetura de Taniyama-Shimura y su demostración por parte de Andrew Wiles, cuando lo termine escribiré una reseña en el blog xD, si puedes leelo, el autor es Simon Singh, yo estoy emocianodisimo mientras lo leo xD, un saludo.

  4. […] Gödel en una cáscara de nuez: Primer Teorema de Incompletitud […]

  5. […] por Carlos on 20/04/07 Cuando empezamos a hacer el recorrido por los resultados de Gödel ya teníamos en perspectiva cómo eventualmente […]

  6. […] dos teoremas de incompletitud se ha escrito, casi, demasiado (Carlos nos los explica muy bien aquí Gödel en una cáscara de nuez: Primer Teorema de Incompletitud y Gödel en una cáscara de nuez: Segundo Teorema de Incompletitud, y Teorema […]

  7. […] dos teoremas de incompletitud se ha escrito, casi, demasiado (Carlos nos los explica muy bien aquí Gödel en una cáscara de nuez: Primer Teorema de Incompletitud y Gödel en una cáscara de nuez: Segundo Teorema de Incompletitud, y Teorema […]

Sorry, the comment form is closed at this time.

 
A %d blogueros les gusta esto: