La diagonalización de Cantor
Este artículo está basado en una colaboración enviada por Daniel. Si estás interesado en colaborar con Gaussianos puedes enviar tus propuestas a gaussianos (arroba) gmail (punto) com.
Introducción
En las últimas semanas habéis podido leer en Gaussianos un par de artículos relacionados con los conjuntos infinitos y sus peculiaridades. A saber, Qué extraño es el infinito y El mALEPHicio del infinito. En este último se alude a la demostración de Cantor de la imposibilidad de poner en correspondencia biunívoca el conjuntos de los naturales, , con el conjunto de los reales,
. En este artículo vamos a desgranar dicha demostración.
La demostración de Cantor
Como hemos dicho antes, en El mALEPHicio del infinito vimos cómo poder en correspondencia uno a uno el conjunto de los naturales positivos con el conjunto de los enteros distintos de cero y con los racionales positivos (y por extensión con los racionales). Y comentamos que no podemos hacer lo mismo con los reales. Para demostrar este hecho comenzamos con un resultado previo:
Lema:
El cardinal del intervalo es el mismo que el cardinal de
.
Demostración:
La idea de la demostración es encontrar una función que pongan en correspondencia uno a uno el intervalo con
. Este tipo de funciones se llaman biyectivas.
La función que buscamos es composición de dos:
- La primera es la función
, que establece una biyección entre el intervalo
y el intervalo
. Es bien sencillo demostrar que esta función es biyectiva, es decir, que pone en correspondencia uno a uno a esos dos intervalo.
- La segunda es
. Esta función es una biyección entre el intervalo
y
, es decir, pone en correspondencia biunívoca ese intervalo con el conjunto de los números reales.
Realizando la composición de las dos obtenemos una biyección entre el intervalo y
. Por tanto ambos conjuntos tienen el mismo cardinal.
La idea ahora es demostrar que el infinito de los números reales es mayor que el de los naturales. Para ello veremos que el cardinal de estos últimos es menor que el de los primeros. Pero antes vamos a dar una definición sobre esto que nos va a echar una mano:
- Dados dos conjuntos,
, decimos que el cardinal de
es menor que el cardinal de
,
(
representa el cardinal de
), si podemos poner en correspondencia biunívoca el conjunto
con un subconjunto de
y no podemos hacer lo mismo entre
y
.
INCISO:
Es interesante recalcar que no basta con que
pueda ponerse en correspondencia uno a uno con un subconjunto de
para decir que
. La segunda condición es obligatoria para que la definición tenga sentido. Un ejemplo claro de esto es la relación entre los números pares y todos los números naturales: los números pares pueden ponerse en correspondencia biunívoca con un subconjunto de los naturales (de hecho con varios: los propios números pares, los impares,...), pero sabemos ya que los números pares también pueden ponerse en correspondencia uno a uno con los propios números naturales, por lo que el cardinal de los pares es el mismo que el de los naturales.
Recordando que dijimos que un conjunto infinito es numerable si puede ponerse en correspondencia biunívoca con los naturales, presentamos el enunciado del teorema de Cantor:
Teorema: (de Cantor):
El conjunto de los números reales, , no es numerable, es decir,
.
Demostración
La idea es utilizar la definición anterior. Por ello lo primero que debemos hacer es encontrar un subconjunto de que pueda ponerse en correspondencia uno a uno con
. Ese subconjunto va a ser el propio
, que como sabemos es un subconjunto de los reales. Ya tenemos entonces la primera parte: podemos poner en correspondencia biunívoca a
con un subconjunto de
.
Según el resultado demostrado anteriormente tenemos que . Por ello si demostramos que
ya tendremos que
. Para ello vamos a suponer que tenemos una correspondencia cualquiera entre
y
y encontraremos un elemento de
que no se corresponde con ninguno de
, es decir, veremos que no hay correspondencias uno a uno entre esos dos conjuntos.
Cualquier correspondencia biunívoca entre y
es básicamente una numeración de los elementos de
, es decir, creamos una lista con los elementos de ese intervalo, digamos
, y asociamos cada número natural con uno de esos elementos. Cada uno de ellos será un cero seguido de un cierto número (finito o infinito) de decimales. Evitando repeticiones (ya sabemos que
y
son el mismo número) tendríamos algo así:
La clave es la siguiente: vamos a encontrar un elemento del intervalo que no corresponde con ningún número natural. Para ello tomamos
y nos quedamos con su primer decimal, al que sumamos 1 obteniendo
; tomamos ahora
y nos quedamos con su segundo decimal, sumándole también 1, obteniendo
; y así sucesivamente (si alguno de ellos es un 9 ponemos un cero). Ahora formamos el número
siguiente:
Para que se entienda mejor pongo el siguiente ejemplo:
Si tenemos las siguientes relaciones:
![]()
construiríamos
.
Es evidente que, construido así, y también es claro que
no corresponde con ningún número natural, ya que difiere con
en (al menos) el primer decimal, con
en (al menos) el segundo, con
en (al menos) el tercero…
Hemos encontrado entonces un elemento del intervalo que no corresponde con ningún número natural en cualquier correspondencia que podamos crear entre estos dos conjuntos. Por tanto
y, en consecuencia:







Trackback | 20 Jul, 2009
Bitacoras.com
Trackback | 20 Jul, 2009
Bitacoras.com
Piteryon | 20 de July de 2009 | 10:35
Y por qué no lo explicarán así de clarito los libros… Muchas gracias a los dos!
Carlos | 20 de July de 2009 | 11:58
hola, saludos!!!!!!!!!!!
ya casi al finalizar la demostración-
gracias por el artículo
un comentario…falta una “|” al enunciar el teorema y un parentesis para el intervalo de
Tanháuser | 20 de July de 2009 | 13:56
Ya que hablamos de numerabilidad, os propongo el siguiente problema. Creo que es divertido.
1.- Probar que en plano podemos dibujar una cantidad no numerable de “ceros” disjuntos, entendiendo que un cero es una circunferencia.
2.- Probar que si cambiamos “ceros” por “ochos”, tan solo podemos dibujar una cantidad numerable.
Si alguien necesita pistas, estaré encantado de proporcionárselas.
Mouri | 21 de July de 2009 | 17:20
El artículo está muy bien, pero hay una cosa que no entiendo: ¿por qué el artículo se llama “La diagonalización de Cantor”?
Dani | 21 de July de 2009 | 18:02
El proceso que usa cantor para encontrar un número real en el intervalo
que no esté relacionado con ningún número natural (si se prefiere que no tenga preimagen por la aplicación
en cuestión, lo que implica que
no puede ser sobreyectiva) es escribir los números en su orden de numeración ( o escribirlos en una tabla según el orden de sus imágenes por
:


) y luego fijarse en la diagonal de esa tabla para construir un número real que es distinto de todos los listados en la tabla (en efecto difiere de
en el k-ésimo decimal). El hecho de fijarse en la diagonal da nombre al proceso usado en la demostración, que se conoce como la “diagonalización de cantor”.
Mouri | 22 de July de 2009 | 14:13
¡Muchas gracias Dani! Más claro imposible.
Dani | 22 de July de 2009 | 19:54
Tanháuser, hay una cosa que no entiendo de tu problema. Supongamos la primera parte, es decir, que se puede dibujar una cantidad de circumferencias no numerables en el plano. Bien, cada una de esas circumferencias tendrá un cierto area, que por supuesto dependerá de la circumferencia en cuestión, pero siempre será estrictamente positiva. Por lo tanto dentro de cada circumferencia podemos dibujar un “ocho”. Al estar los ochos estrictamente contenidos en las circumferencias, tenemos dibujados en el plano una cantidad no numerable de ochos disjuntos, en contra de la segunda parte del problema… :S?
Toro Sentado | 23 de July de 2009 | 00:05
Creo recordar que el mismo argumento de diagonalización se usa para demostrar que no existe ninguna máquina de Turing que pueda decir si un programa se va a detener o no, no recuerdo bien pero me parece que se llama el problema de la parada.
Saludos
ds | 23 de July de 2009 | 06:14
Alguien puede darme una biyeccion entre R y [0,1] ?
M | 23 de July de 2009 | 10:54
Respecto a la cuestión 1 de Tanhäuser (y guiado por el último comentario de Dani), claramente puede responderse tomando circunferencias concéntricas de radio irracional. La gracia estaría en ver si es posible elegir las circunferencias de modo que sus círculos no estén contenidos unos dentro de otros. Pero la respuesta es que no por lo siguiente:
Supongamos una familia
(indizada en un conjunto de índices genérico
) de circunferencias cuyos círculos sean disjuntos dos a dos en el plano:
(
>0), tales que
(
). Llamemos
y veamos que este conjunto es contable (y por tanto también
).
Como
es numerable, podemos tomar una función de elección
tal que
,
,
(en otras palabras, de cada subconjunto no vacío de
podemos extraer un elemento). Parecería aquí que estamos usando el axioma de elección, pero no es así ya que todo conjunto numerable admite una función de elección (por ejemplo, a cada subconjunto le asocias su elemento mínimo de acuerdo al orden que hereda el conjunto de su biyección con los naturales).
Con esto definimos la función
, como
(está bien definida pues los discos tienen radio positivo). Esta función es inyectiva, y por tanto
.
Para ver que
es inyectiva, hay que tener en cuenta que si
entonces
. Pero, al ser los discos disjuntos, debe ser que
.
En consecuencia las respuestas a la cuestión 1 pasan por considerar circunferencias en las que “la mayoría estén metidas dentro de otras”.
Con esto, ahora no necesariamente tiene porqué poder dibujarse un ocho dentro de una de esas circunferencias, pues por ejemplo si tomamos circunferencias concéntricas con sus radios cubriendo los irracionales de un intervalo dado ya no habría esa posibilidad.
M | 23 de July de 2009 | 11:05
Respecto a la pregunta que hace ds, yo ahora mismo no conozco ningún ejemplo explícito. Normalmente una biyección entre un intervalo abierto (como
) y otro cerrado o semicerrado (por ejemplo,
) se suele construir implícitamente siguiendo la demostración del teorema de Cantor-Schröder-Bernstein.
Así que para dar una biyección entre
y
, basta considerar
, que es biyección entre
y
, y luego de
en
puedes fijar los irracionales y como los racionales de ambos conjuntos son numerables también los puedes asociar biunívocamente.
Dani | 23 de July de 2009 | 11:07
Muy buena, M. Por alguna razón había supuesto que se requería que los DISCOS fuesen disjuntos, no las circumferencias, en cuyo caso está tanto el problema que dices tú como el que plantee yo. Ahora quedaría por demostrar que de hecho no es posible hacerlo con ochos.
Dani | 23 de July de 2009 | 11:10
(es decir, demostrar que no podemos “encajar” ochos dentro de ochos dentro de ochos de forma no numerbale)
Dani | 23 de July de 2009 | 11:23
Supongamos que tenemos ochos encajados dentro de cada “circumferencia superior” del ocho inmediatamente anterior (supondremos que sólo se encajan en la circumferencia superior pues si también hubiese en la inferior doblaríamos el cardinal, lo que no afecta a la numerabilidad). si el conjunto de ochos es
, reciclo la función de elección (y la idea, claro
) de M para definir una función
como
donde
es precisamente el círculo inferior de cada ocho. Como hemos supuesto que los ochos siguientes están encajados dentro de los círculos superiores de los ochos anteriores, tenemos que
. Por lo tanto esta función es inyectiva y en consecuencia
. Si de hecho hubiese ochos también encajados en los círuclos inferiores de cada ocho repetimos el argumento sólo para esos y concluiríamos que también son numerables, y por tanto que su unión también lo es.
Tanhäuser | 23 de July de 2009 | 15:19
Casi, casi.
La idea es pensar que Q^4 es numerable.
Como muy bien habéis observado, la gracia está en la “estructura topológica” de un 8.
M | 23 de July de 2009 | 16:59
Dani tu último razonamiento no me parece del todo correcto, ya que por propia construcción parece que estás tomando una cantidad numerable de ochos (de hecho hablas de “ocho inmediatamente anterior”). Pero la idea de elegir un punto de cada “círculo inferior” se ajusta muy bien a lo que ha propuesto Tanhäuser. De hecho nos lo ha dejado servido (
) y basta coger un punto con coordenadas racionales de cada una de las dos componentes conexas de la región interior del ocho:
Para cada figura
con forma de ocho llamaremos
a las dos componentes conexas de su región interior.
Tomemos una familia arbitraria de “ochos rellenos” (lemniscatas incluyendo su región interior)
de tal modo que las fronteras de dos ochos dados no se intersequen. Entonces, o bien los ochos son disjuntos (
), o bien uno de ellos está contenido en una de las componentes conexas del interior del otro ocho (
, para algún
; o bien cambiando el índice
por el
).
Volvemos a tomar una función de elección
, y ahora definimos la función
definida como
. Esta función es inyectiva.
Tanhäuser | 23 de July de 2009 | 17:29
M: voilà.
Felicidades
Nicolás Milano | 25 de July de 2009 | 18:21
Perdonen mi ignorancia, pero siempre varias veces me he topado con los símbolos matemáticos
y
y quisiera saber qué significan. Creo que alguna vez oí (quizá incorrectamente) que se refieren al plano y al espacio euclídeo, respectivamente. Sé que R es el conjunto de los números reales, pero desconozco los símbolos anteriormente empleados. Tampoco sé qué es
. Os agradecería si pudiérais aclararme tal cuestión.
También tengo otra pregunta, quizá un tanto extraña. ¿Existe algún criterio o algoritmo para determinar si un enunciado matemático es demostrable o no? Es decir, ¿existe algún método que permita saber si (por ej.) la Conjetura de Goldbach pueda ser demostrada o no (que no sea por supuesto demostrarla)? Desde ya muchas gracias.
Dani | 27 de July de 2009 | 20:28
M: ok, comprendido, y buena!
.
y otro
se define su producto cartesiano como el conjunto
de pares ordenados formados por un elemento de
y otro de
. Así pues el conjunto
es el conjunto de pares ordenados de números reales, como el
o el
. Como podemos identificar cada punto del plano con un par ordenado de números mediante un sistema de coordenadas identificamos todo el plano con
. Para el espacio es lo mismo pero con ternas ordenadas de números reales. El producto cartesiano se puede extender todo lo que quieras (para el infinito se necesita el Axioma de Elección, pero ese es otro asunto). Así pues
es el conjunto de 4-uplas de números racionales, es decir el conjunto de elementos de la forma
donde
son todos racionales.
Nicolás: Dado un conjunto
Por otra parte estás hablando del problema de la parada, asunto muy turbio en el que indagó mucho Turing. No se puede
Nicolás Milano | 27 de July de 2009 | 23:14
Muchas gracias, Dani. ¡Ahora por fin lo entiendo!
M | 28 de July de 2009 | 11:09
No quiero incordiar, pero acabo de acordarme de que hay problemas con la demostración del teorema de Cantor, si el proceso diagonal se define tal como se ha hecho. ¿Si el proceso diagonal se aplicase a las series siguientes (que en realidad son la misma) obtenemos un número de (0,1)?
0’9
0’99
0’999
0’9999
0’99999
…
0’899999…
0’989999…
0’998999…
0’999899…
0’999989…
…
La sucesión siguiente tampoco define un número de (0,1):
0’8
0’88
0’888
0’8888
…
Lo que es peor aún, la ley que asigna a cada serie un nuevo número “en
” no está bien definida: las siguientes sucesiones son iguales y no tienen asignados el mismo número.
0’1
0’01
0’001
0’0001
0’00001
…
0’09999999…
0’00999999…
0’00099999…
0’00009999…
0’00000999…
…
¿Cómo arreglamos esto? Aunque en el post se ha dicho que se descarta la repetición infinita de 9′s, vemos que las sucesiones 1) y 3) definen por el método diagonal al 0 y al 1, respectivamente. El problema de fondo es que la representación decimal de los números decimales finitos no es única, y para evitar estos problemas es mejor considerar únicamente expresiones decimales infinitas (con 9′s repetidos). Luego para evitar los problemas es mejor definir
como un número distinto de
y
(en lugar de tomar
, o
, si
) para evitar obtener un decimal diagonal finito.
Dani | 28 de July de 2009 | 17:35
Sí. Efectivamente, yo también me di cuenta de eso pero decidí obviarlo porque es fácil de arreglar. Mi demostración original consideraba una aplicación
, es decir, una numeración de las sucesiónes de ceros y unos, que se pueden identificar con los reales del
mediante el sistema binario. Demostrando que no puede ser sobreyectiva obtenemos el resultado deseado. Con ceros y unos es más fácil de arreglar esa cuestión, y aun se podría refinar más dándose cuenta de que el conjuno de números reales que tiene más de una representación en binario es numerable (si
es el conjuno de números que tiene un uno en la posición n-1 y todo “ceros” a partir de la n-ésima posición -igual al que tiene un 0 en la n-1 y todo unos a partir de la n-ésima) vemos que el conjunto de números que tienen más de una representación es
, unión numerable de finitos, con lo que podemos ignorar estos casos
)
Lou Sara Salomè | 2 de September de 2009 | 17:32
Muchísimas gracias por el artículo, el autor se expresó con suma claridad y hasta una profana como yo en el universo matemático lo pilló
Tengo una duda y me gustaría que alguien me echara un cable. Es sobre le teorema de la diagonal de Cantor, ¿alguien podría explicarme la demostracion de la diagonal y la contradiagonal construyendo una matriz con ceros y unos?
Muchísimas gracias, es una pregunta de la asignatura de Lógica, Teoría de conjuntos que tengo en la carrera.
Muchas gracias, espero impaciente que algún gentil matemático pueda darme una explicación “clara y distinta”, como diría el colega Descartes.
¡Un saludo!
y enhorabuena por la página, es muy interesante ;D
Trackback | 16 Apr, 2010
Alicia y el país de las matemáticas: una maravillosa relación | Gaussianos
Silvia | 4 de June de 2010 | 00:34
necesito demostrar que dada una sucesión de 0 y1 es numerable o no . justificando
Gracias Silvia
Trackback | 8 Jun, 2010
Increíble pero cierto | Gaussianos
Ignacio Larrosa | 14 de June de 2010 | 01:16
Silvia, ¿Te refieres a si el conjunto de sucesiones cuyos elementos son todos iguales a 0 o a 1 es o no numerable?
Si es así, la respuesta es no, e inmediata de justificar:
Una sucesión de ceros y unos es la representación en base 2 de un número en el intervalo [0, 1]. No es una biyección por lo que ya se ha comentado, que una sucesión cuyos términos sean todos unos de uno en adelante, se corresponde con el mismo número que otra sucesión finita. Pero esta claro que el cardinal de las sucesiones de ceros y unos es mayor o igual que el de los números reales en [0, 1], y por tanto, ese conjunto no es numerable.
Trackback | 19 Sep, 2010
Que no, que el conjunto de los números reales no es numerable | Gaussianos
Trackback | 25 Aug, 2011
Cuándo dos conjuntos tienen el mismo número de elementos - Gaussianos | Gaussianos
Trackback | 27 Dec, 2011
(Lo que yo considero) Lo mejor de 2009 en Gaussianos - Gaussianos | Gaussianos