Diagonalización de Cantor

Este artículo o sección necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 22 de octubre de 2011. También puedes ayudar wikificando otros artículos o cambiando este cartel por uno más específico.

La diagonalización de Cantor, también conocida como método diagonal, es una prueba matemática vislumbrada por Georg Cantor para demostrar que los números reales no son contables.

Esta demostración de la imposibilidad de contar los números reales no fue la primera, pero sí la más sencilla y elegante. Posteriormente, esta prueba inspiró otras demostraciones, conocidas como argumento diagonal por la analogía con esta demostración.

Números reales

La prueba original de Cantor muestra que el intervalo [0,1] no es numerable. Se extiende a todos los reales, ya que es posible equipotenciar estos al intervalo.

La demostración es por reducción al absurdo.

• Suponemos que el intervalo [0,1] es infinito numerable.
• Podríamos elaborar una secuencia de los números, ( r₁, r₂, r₃,... )
• Sabemos que los reales entre 0 y 1 pueden ser representados solamente escribiendo sus decimales.
• Colocamos los números en la lista (no necesariamente en orden). Considerando los decimales periódicos, como 0.499... = 0.500..., como los que tienen infinitos nueves.

La secuencia q

r₄ = 0. 2 3 3 0 1 2 6...

r₅ = 0. 4 1 0 7 2 4 6...

r₆ = 0. 9 9 3 7 8 3 8...

r₇ = 0. 0 1 0 5 1 3 5...

...

Ahí tenemos todos los números reales entre 0 y 1. Vamos a construir un número x que debería estar en la lista. Para eso usamos los números de la diagonal.

r₁ = 0. 5 1 0 5 1 1 0...

r₂ = 0. 4 1 3 2 0 4 3...

r₃ = 0. 8 2 4 5 0 2 6...

r₄ = 0. 2 3 3 0 1 2 6...

r₅ = 0. 4 1 0 7 2 4 6...

r₆ = 0. 9 9 3 7 8 3 8...

r₇ = 0. 0 1 0 5 1 3 5...

...

• El número x está definido así: al dígito x_k le corresponde el k-ésimo dígito de r_k + 1 (si fuera un nueve, le asignó el cero)

Entonces x= 0.6251346.... El número x es claramente un real. Pero.. ¿Dónde está x ?

Si yo quisiera decir que x está en el n-ésimo lugar de mi lista, no sería cierto, ya que el elemento n-ésimo dígito de r_n es distinto al de x.

• Entonces esta no es una lista completa de los reales en el intervalo [0,1].
• Existe una contradicción, por suponer que estos números son infinitos numerables.

Para extender este resultado a R tenemos que establecer una relación biyectiva entre este intervalo y los reales. Esto es posible gracias a una función como esta:

definida por

Con esto podemos decir que hay tantos números reales como reales entre 0 y 1.