Argumento de la diagonal de Cantor

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.

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:

La secuencia podría tener un aspecto similar a:

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.

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.

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

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

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

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

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 {ar {d}}(L)}$ un conjunto de números enteros positivos definido como sigue:

donde ${displaystyle mathbb {Z} ^{+}}$ es el conjunto de números enteros positivos. Esto indica que ${displaystyle {ar {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 {ar {d}}(L)}$ depende de la composición de la lista L. Es fácil ver que ${displaystyle {ar {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 {ar {d}}(L)}$.

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

Esto implica una contradicción, pues cuando ${displaystyle n=m}$, ocurre que ${displaystyle min {ar {d}}(L)iff m otin S_{m}={ar {d}}(L)}$, esto es, ${displaystyle m}$ debería formar y no formar parte de ${displaystyle {ar {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.