Teorema de Cantor
Para conjuntos finitos, se puede ver que el teorema de Cantor es verdadero mediante una simple enumeración del número de subconjuntos.
Mucho más significativo es el descubrimiento de Cantor de un argumento que es aplicable a cualquier conjunto y muestra que el teorema también se cumple para conjuntos infinitos.
El teorema lleva el nombre del matemático alemán Georg Cantor, quien lo planteó y demostró por primera vez a fines del siglo XIX.
Por ejemplo, tomando iterativamente el conjunto potencia de un conjunto infinito y aplicando el teorema de Cantor, obtenemos una jerarquía infinita de cardinales infinitos, cada uno estrictamente mayor que el anterior.
En consecuencia, el teorema implica que no hay un número cardinal más grande (coloquialmente, "no hay un infinito más grande").
El hecho de que sea válido para todo conjunto infinito no es del todo intuitivo, pero permite establecer varios resultados interesantes: Para ilustrar la validez de este teorema para conjuntos infinitos se reproduce a continuación una demostración.
Queremos ver que esta función no es sobreyectiva, y para ello necesitamos encontrar un subconjunto de
(que es una función cualquiera) no es sobreyectiva, como queríamos demostrar.
Si se examina la demostración para el caso específico cuando
Se analiza una muestra del aspecto de 𝒫(N): 𝒫(N) contiene infinitos subconjuntos de N, o sea el conjunto de todos los números pares {2, 4, 6,...}, además del conjunto vacío.
Otros números naturales están emparejados con subconjuntos que no los contienen.
Llamamos a estos números no egoístas.
Del mismo modo, el 3 y el 4 son no egoístas.
Usando esta idea, construyamos un conjunto especial de números naturales.
Este conjunto proporcionará la contradicción que buscamos.
Sea B el conjunto de todos los números naturales no egoístas.
Como no hay ningún número natural que pueda ser emparejado con B, hemos contradicho nuestra suposición original, de que hay una biyección entre N y 𝒫(N).
Nótese que el conjunto B puede estar vacío.
Esto significaría que cada número natural x mapea a un subconjunto de números naturales que contiene a x.
Entonces, cada número corresponde a un conjunto no vacío y ningún número corresponde al conjunto vacío.
Mediante esta demostración por contradicción hemos demostrado que la cardinalidades de N y 𝒫(N) no pueden ser iguales.
Para distinguir esta paradoja de la otra que se trata más abajo, es importante notar la naturaleza de esta contradicción.
son conjuntos, y por lo tanto están contenidos en
[2] Otra paradoja puede derivarse de la demostración del teorema de Cantor instanciando la función f con la función identidad; esto convierte el conjunto diagonal de Cantor en lo que a veces se llama el conjunto de Russell de un conjunto dado A:[2] La demostración del teorema de Cantor se adapta directamente para mostrar que suponiendo que existe un conjunto de todos los conjuntos U, entonces considerando su conjunto Russell R U se llega a la contradicción: Esta argumentación se denomina la paradoja de Russell.
Esto es posible porque hemos usado comprensión restringida (como se muestra en ZFC) en la definición de RA anterior, lo que a su vez implica que Si se hubiese utilizado la comprensión irrestricta (como por ejemplo en el sistema de Frege) para definir el conjunto de Russell simplemente como
[3] Existe otro método para demostrar que no existe un cardinal mayor: el número de Hartogs de cualquier conjunto tiene una cardinalidad estrictamente mayor que la del conjunto inicial.
Más precisamente, mostramos que el conjunto de ordinales contables como máximo también tiene un cardinal estrictamente mayor que el de N (resultado debido a Cantor).
Bertrand Russell tiene una prueba muy similar en Principia Mathematica (1903, sección 348),[5] donde muestra que hay más funciones proposicionales que objetos.
"Supongamos que una correlación de todos los objetos y algunas funciones proposicionales han sido afectadas, y que phi-x es el correlato de x.
Russell atribuye la idea de esta prueba a Cantor.
