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: La diagonalización de Cantor

Posted by Carlos en marzo 14, 2007

Cuando hace algunas semanas hablábamos de Gödel, surgió evidentemente el tema de sus Teoremas de Incompletitud, y su relación con la noción de computabilidad. Esta última es realmente interesante, y merece la pena detenerse un poco en ella. Para ello, quizás sea bueno hacer primero una pequeña introducción informal a los resultados de Gödel, ya que como apuntaba Alf en el hilo de discusión, están sumamente relacionados con dicha noción. De hecho, hay un elemento previo que -aumentando un poco el nivel de abstracción- podemos encontrar tanto en el trabajo de Gödel, como en el de Turing, entre otros muchos. Se trata del corte diagonal de Cantor.

El corte diagonal -o diagonalización- de Cantor es una de las más poderosas herramientas a las que podemos recurrir cuando razonamos con conjuntos infinitos. De hecho, una de sus primeras aplicaciones fue la demostración de que la infinitud de los números reales es mayor que la infinitud de los números naturales. La base del argumento -que se puede extender a conjuntos infinitos arbitrarios- es demostrar que es imposible definir una relación 1-a-1 entre los elementos de un conjunto y otro. Siguiendo el ejemplo anterior, supongamos que efectivamente podemos establecer una relación de ese tipo, es decir, que existe una función biyectiva

f:\mathbb N \longrightarrow \mathbb R.

Ahora demostraremos que tal función no existe, ya que hay al menos un número real r que no es imagen de ningún número natural. Para ello, definamos la función Di(s) como el dígito i-ésimo del número real s. Podemos entonces considerar un número real r, tal que

D_i(r) = (D_i(f(i))+1) \mod 10.

Claramente, no existe ningún número natural n tal que f(n) = r, ya que la imagen de cualquier valor n difiere de r en el dígito n-ésimo. De hecho, podemos ver cómo se obtiene una contradicción si se sustituye r por f(n) en la expresión de Dn(r):

D_n(r) = D_n(f(n)) = (D_n(f(n))+1) \mod 10.

Esto también se puede ver gráficamente si nos imaginamos una matriz en la que la fila i-ésima representa la lista (infinita) de dígitos del número real asociado al número natural i. El número r que hemos definido se obtiene tomando la diagonal de la matriz, y sumando 1 (módulo 10) a cada dígito, con lo que claramente difiere de todas las filas de la matriz. La función f no es por lo tanto suprayectiva, dado que hay más números reales que naturales.

El resultado anterior fue generalizado por el propio Cantor en el teorema que lleva su nombre, y que afirma que el conjunto potencia de un conjunto (es decir, el conjunto de todos los subconjuntos de uno dado) tiene más elementos que el conjunto base. Esto que es obvio para conjuntos finitos, no era trivial para conjuntos infinitos, pero puede demostrarse de acuerdo con el anterior razonamiento: supongamos que existe una función que relaciona elementos de un conjunto base infinito S con subconjuntos de elementos de dicho conjunto:

f: S \longrightarrow 2^S.

Podemos ahora definir un subconjunto

T=\{s\in S\ |\ s\notin f(s)\}

Supongamos que existe un t tal que f(t)= T. Preguntémonos ahora si t pertenece a T o no:

  • Si t pertenece a T, entonces t pertenece a f(t)=T, luego no cumple la condición necesaria para pertenecer a T.
  • Si t no pertenece a T, entonces no pertenece a f(t), lo que por definición hace que pertenezca a T.

En ambos casos llegamos a una contradicción, lo que implica que nuestra suposición de partida, esto es, que existía un t cuya imagen era T es falsa. Por lo tanto, la cardinalidad de 2S es mayor que la de S. El mismo razonamiento puede aplicarse a su vez al conjunto potencia de 2S, ad infinitum, lo que resulta en una jerarquía de números transfinitos. En el caso concreto de que S sea el conjunto de los números naturales, obtenemos la secuencia:

\aleph_0,\ c,\ 2^c,\ 2^{2^c},\ \cdots ,

donde \aleph_0 es la cardinalidad de los naturales, y c=2^{\aleph_0} es la cardinalidad de los números reales. Cantor dedicó infructuosamente mucho tiempo a intentar demostrar si c=\aleph_1 o no, esto es, si la cardinalidad de los reales es el primer número transfinito mayor que \aleph_0. Esto es lo que se conoce como la hipótesis del continuo, cuya versión generalizada es

|A|=\aleph_i \Leftrightarrow |2^A|=\aleph_{i+1}

donde |X| representa la cardinalidad de un conjunto X. Fue precisamente Gödel el que demostraría en 1940 (22 años tras la muerte de Cantor) la futilidad de intentar una demostración en el sistema axiomático ZFC (Zermelo-Fraenkel con Axioma de elección), ya que la hipótesis del continuo es independiente del mismo.

Una vez presentado el corte diagonal de Cantor, la siguiente parada en el camino son los teoremas de incompletitud de Gödel. El próximo día hablamos de ello.

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

Anuncios

5 comentarios to “Gödel en una cáscara de nuez: La diagonalización de Cantor”

  1. Increible entrada ^^, parece que fué ayer cuando me explicaron el “método diagonal de Cantor” en Teoria de la Computabilidad, por aquel entonces no le eché mucha cuenta, hasta hace poco no he sabido apreciar la genialidad de este señor. A ver si algún dia le echo valor y escribo sobre el, o sobre David Hilbert, que también fué un genio entre los genios, lástima que Kurt Gödel le arrebatase el sueño de crear un sistema axiomático perfecto xD. Lo dicho, un artículo muy interesante, un saludo.

  2. […] Gödel en una cáscara de nuez: La diagonalización de Cantor […]

  3. Carlos said

    Gracias, J. En relación con lo que comentas, una de las cosas que me llaman la atención tanto de la técnica del corte diagonal de Cantor, como de las ideas básicas de los teoremas de Gödel por ejemplo, es que la primera impresión es la de decir “es obvio”. Son conceptos que en esencia (aparte de que los detalles de la formulación puedan ser más o menos complejos) destacan por su simplicidad y elegancia. Creo que a veces eso no nos permite apreciar en primera instancia el mérito que tuvieron estas personas en tener esa idea brillante, y formalizarla convenientemente.

  4. […] https://singularidad.wordpress.com/2007/03/14/godel-en-una-cascara-de-nuez-la-diagonalizacion-de-cant… […]

  5. Felipe said

    Tengo una duda estúpida. Si dices que r es un número real y como se parte de que existe una ordenación de R, entonces r está en una posición k-ésima, pero ¿qué digito es su k-ésimo dígito? ya que sería el propio dígito k-ésimo (que aún no conocemos) más uno. Por lo que r no es un número real, con lo que llegamos a una contradicción. ¿concluiriamos así que no existe esa función biyectiva?

Sorry, the comment form is closed at this time.

 
A %d blogueros les gusta esto: