Argumento de la diagonal de Cantor

Un ejemplo de cómo funciona el argumento diagonal de Cantor para probar la existencia de un conjunto no numerable. Dada la lista inicial, formada por números con alguna cifra marcada en rojo, puede probarse que ningún elemento de la lista coincide con el número cuya expresión tiene las cifras marcadas en azul, ya que dicho número difiere de todos y cada uno de los anteriores.

El argumento de la diagonal de Cantor, también conocido como método de la diagonal, es una argumentación o demostración matemática vislumbrada por Georg Cantor hacia 1891 para demostrar que el conjunto de los números reales no es numerable.

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

Números reales

La prueba original de Cantor demuestra que el intervalo [0,1] no es numerable, es decir, no podemos enumerar la lista de todos los reales dentro del intervalo (siempre habrá más). Se extiende a todos los reales, ya que es posible equipotenciar estos al intervalo. Podemos demostrar que lo que es válido para el intervalo [0,1] lo es para cualquier otro, por grande que sea (exceptuando el intervalo [0,0] que tiene un solo valor, el cero).

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

1. Se supone que el intervalo [0,1] es infinito numerable.
2. En ese caso se podría elaborar una secuencia de números, ( r₁, r₂, r₃,... ).
3. Se sabe que los reales entre 0 y 1 pueden ser representados solamente escribiendo sus decimales.
4. Se colocan 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 podría tener un aspecto similar a:

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...

...

Dada la primera premisa dicha lista contiene todos los números reales entre 0 y 1. Con esto, se puede 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 k-ésimo dígito decimal de x le corresponde el k-ésimo dígito decimal de r_k más 1 (en caso de que fuera un nueve, se le asigna el dígito 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 enésimo lugar de mi lista, no sería cierto, ya que el ené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, que nace de la premisa de suponer que estos números son infinitos numerables.

Para extender este resultado al campo ${\displaystyle \mathbb {R} }$ tenemos que establecer una relación biyectiva entre este intervalo y los reales. Esto es posible gracias a una función como ésta:

${\displaystyle {\begin{array}{rccl}f:&(0,1)&\to &\mathbb {R} \\&x&\to &y=f(x)=\tan \left[\pi \left(x-{\frac {1}{2}}\right)\right]\end{array}}}$

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

Números enteros positivos

El argumento de la diagonal de Cantor está íntimamente ligado al Teorema de Cantor. La relación entre ambos puede entenderse en términos de la numerabilidad de un conjunto. Un conjunto se dice numerable o contable si existe una relación biyectiva entre los elementos del conjunto y los números enteros positivos; esto es, si es posible organizar a los elementos del conjunto de tal manera que todos los elementos del conjunto aparecen antes o después, incluso repetidas veces, en la lista. En tal caso, los elementos del conjunto pueden ser asignados con un 'marcador' o 'índice', que sería el correspondiente número entero positivo (esto es, al primer elemento de la lista le sería asignada la etiqueta 1; al segundo, 2; etc.). Como quiera que esto es posible en tanto en cuanto el conjunto sea numerable, operar con los elementos del conjunto, o con sus etiquetas es equivalente.

El argumento de la diagonal de Cantor establece que

El conjunto de todos los conjuntos de números enteros positivos no es numerable.

Demostración

Sea P el conjunto de todos los conjuntos de números enteros positivos. Sea L una lista infinita cualquiera de conjuntos de enteros positivos:

${\displaystyle L=\{S_{1},S_{2},S_{3},\ldots \}}$

donde ${\displaystyle S_{1},S_{2},S_{3},\ldots }$ son conjuntos cualesquiera de enteros positivos. Si el conjunto P fuera numerable, entonces sería posible definir una lista L tal que incluya a todos los conjuntos de números enteros positivos. Sin embargo, el argumento de diagonalización demuestra que esto no es posible.

Sea ${\displaystyle {\bar {d}}(L)}$ un conjunto de números enteros positivos definido como sigue:

${\displaystyle {\bar {d}}(L)=\{n\in \mathbb {Z} ^{+}:n\notin S_{n}\}}$

donde ${\displaystyle \mathbb {Z} ^{+}}$ es el conjunto de números enteros positivos. Esto indica que ${\displaystyle {\bar {d}}(L)}$ está formado por todos aquellos enteros positivos n tales que al mismo tiempo no formen parte del conjunto ${\displaystyle S_{n}}$ de la lista L. Por tanto, la composición de ${\displaystyle {\bar {d}}(L)}$ depende de la composición de la lista L. Es fácil ver que ${\displaystyle {\bar {d}}(L)}$ existe: supóngase por ejemplo que ${\displaystyle S_{8}}$ es el conjunto de todos los números positivos impares. Entonces, ${\displaystyle n=8}$ no pertenece a ${\displaystyle S_{8}}$, y por tanto pertenece a ${\displaystyle {\bar {d}}(L)}$.

Si P fuera enumerable, entonces debería existir una lista L tal que ${\displaystyle {\bar {d}}(L)}$ formara parte de ella como elemento ${\displaystyle m\in \mathbb {Z} ^{+}}$. En cuyo caso, se seguiría que

${\displaystyle S_{m}={\bar {d}}(L)}$.

Esto implica una contradicción, pues cuando ${\displaystyle n=m}$, ocurre que ${\displaystyle m\in {\bar {d}}(L)\iff m\notin S_{m}={\bar {d}}(L)}$, esto es, ${\displaystyle m}$ debería formar y no formar parte de ${\displaystyle {\bar {d}}(L)}$ al mismo tiempo.

Por tanto, no es posible construir una lista L tal que contenga al menos una vez a todos los elementos del conjunto de todos los conjuntos de números enteros positivos. O, dicho de otro modo, el conjunto P de todos los conjuntos de enteros positivos no es numerable.

Referencias

Bibliografía

• Binder, P. (2008). «Theories of almost everything». Nature (455): 884-885. 

• Boolos, G.S. (1994). Computability and Logic. Cambridge University Press. 

• Datos: Q729471