Argumento de la diagonal de Cantor
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.
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.
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 extender este resultado al campo
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.
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.
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.
un conjunto de números enteros positivos definido como sigue: donde
es el conjunto de números enteros positivos.
está formado por todos aquellos enteros positivos n tales que al mismo tiempo no formen parte del conjunto
es el conjunto de todos los números positivos impares.
Si P fuera enumerable, entonces debería existir una lista L tal que
formara parte de ella como elemento
En cuyo caso, se seguiría que Esto implica una contradicción, pues cuando
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.
