El teorema de Cantor, de Georg Cantor,^[1]​, es un resultado formalizable en la teoría de conjuntos de Zermelo-Fränkel, que afirma lo siguiente:

Para conjuntos finitos, se puede ver que el teorema de Cantor es verdadero mediante una simple enumeración del número de subconjuntos. Contando el conjunto vacío como un subconjunto, un conjunto con ${\displaystyle n}$ elementos tiene un total de ${\displaystyle 2^{n}}$ subconjuntos, y el teorema se cumple porque ${\displaystyle 2^{n}>n}$ para todos los enteros no negativos.

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. En consecuencia, la cardinalidad de los números reales, que es la misma que la del conjunto potencia de los enteros, es estrictamente mayor que la cardinalidad de los enteros.

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. El teorema de Cantor tuvo consecuencias inmediatas e importantes para la filosofía de las matemáticas. 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 teorema de Cantor es obvio para conjuntos finitos: si un conjunto finito tiene n elementos entonces el conjunto de partes de ese conjunto tiene 2ⁿ elementos. El hecho de que sea válido para todo conjunto infinito no es del todo intuitivo, pero permite establecer varios resultados interesantes:

• Existe una infinidad de cardinales transfinitos, lo cual significa que en realidad existen muchos tipos de infinito (de hecho una infinidad) cada uno mayor que el anterior. Este resultado a priori es muy poco intuitivo, pero tremendamente importante en la fundamentación de las matemáticas.
• No existe ninguna manera de enumerar todos los subconjuntos de ${\displaystyle \mathbb {N} }$.

Para ilustrar la validez de este teorema para conjuntos infinitos se reproduce a continuación una demostración.

Sea ${\displaystyle A}$ un conjunto arbitrario, y consideremos una función ${\displaystyle f:A\to {\mathcal {P}}(A)}$ arbitraria, donde ${\displaystyle {\mathcal {P}}(A)}$ es el conjunto potencia de ${\displaystyle A}$. Queremos ver que esta función no es sobreyectiva, y para ello necesitamos encontrar un subconjunto de ${\displaystyle A}$ que no sea la imagen de ningún elemento de ${\displaystyle A}$ a través de ${\displaystyle f}$. Cantor consideró un subconjunto particular ${\displaystyle B}$ definido de la siguiente manera:

${\displaystyle B=\left\{\,x\in A:x\not \in f(x)\,\right\}.}$

Veamos que ${\displaystyle B}$ no puede ser la imagen de ningún elemento de ${\displaystyle A}$. El argumento que construyó Cantor es por reducción al absurdo presuponiendo que existe ${\displaystyle a\in A:B=f(a)}$, puesto que ${\displaystyle B}$ es un subconjunto de ${\displaystyle A}$. Ahora podemos distinguir dos casos:

1. Si ${\displaystyle a\in B}$, entonces por la definición de ${\displaystyle B}$ se tiene que ${\displaystyle a\notin B}$, lo cual es contradictorio.
2. Si ${\displaystyle a\notin B}$, entonces por la definición de ${\displaystyle B}$ se tiene que ${\displaystyle a\in B}$, lo cual es contradictorio.

En ambos casos llegamos a una contradicción, por tanto no existe dicha ${\displaystyle a}$ y entonces ${\displaystyle f}$ (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 ${\displaystyle A}$ es un infinito numerable. Sin pérdida de generalidad, se puede tomar A = N = {1, 2, 3, …}, el conjunto de los números naturales.

Si se supone que N es equinumeroso con su conjunto potencia 𝒫(N). Se analiza una muestra del aspecto de 𝒫(N):

${\displaystyle {\mathcal {P}}(\mathbb {N} )=\{\varnothing ,\{1,2\},\{1,2,3\},\{4\},\{1,5\},\{3,4,6\},\{2,4,6,\dots \},\dots \}.}$

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

Ahora que tenemos una idea de cómo son los elementos de 𝒫(N), vamos a intentar emparejar cada elemento de N con cada elemento de 𝒫(N) para demostrar que estos conjuntos infinitos son equinuméricos. En otras palabras, intentaremos emparejar cada elemento de N con un elemento del conjunto infinito 𝒫(N), de manera que ningún elemento de ninguno de los dos conjuntos infinitos quede sin emparejar. Este intento de emparejar elementos se vería así:

${\displaystyle \mathbb {N} {\begin{Bmatrix}1&\longleftrightarrow &\{4,5\}\\2&\longleftrightarrow &\{1,2,3\}\\3&\longleftrightarrow &\{4,5,6\}\\4&\longleftrightarrow &\{1,3,5\}\\\vdots &\vdots &\vdots \end{Bmatrix}}{\mathcal {P}}(\mathbb {N} ).}$

Dado este emparejamiento, algunos números naturales se emparejan con subconjuntos que contienen el mismo número. Por ejemplo, en nuestro ejemplo el número 2 está emparejado con el subconjunto {1, 2, 3}, que contiene el 2 como miembro. Llamemos a estos números egoístas. Otros números naturales están emparejados con subconjuntos que no los contienen. Por ejemplo, en nuestro ejemplo el número 1 está emparejado con el subconjunto {4, 5}, que no contiene el número 1. 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. Por definición, el conjunto de potencias 𝒫(N) contiene todos los conjuntos de números naturales, y por tanto contiene este conjunto B como elemento. Si el mapeo es biyectivo, B debe ser emparejado con algún número natural, digamos b. Sin embargo, esto causa un problema. Si b está en B, entonces b es egoísta porque está en el conjunto correspondiente, lo que contradice la definición de B. Si b no está en B, entonces no es egoísta y en cambio debería ser miembro de B. Por lo tanto, no puede existir ningún elemento b que mapee a B.

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. Pero el conjunto vacío es un miembro de 𝒫(N), por lo que el mapeo todavía no cubre 𝒫(N).

Mediante esta demostración por contradicción hemos demostrado que la cardinalidades de N y 𝒫(N) no pueden ser iguales. También sabemos que la cardinalidad de 𝒫(N) no puede ser menor que la cardinalidad de N porque 𝒫(N) contiene todos los singletons, por definición, y estos singletons forman una "copia" de N dentro de 𝒫(N). Por tanto, sólo queda una posibilidad, y es que la cardinalidad de 𝒫(N) sea estrictamente mayor que la cardinalidad de N, demostrando el teorema de Cantor.

El teorema de Cantor y su demostración están estrechamente relacionados con dos paradojas de la teoría de conjuntos.

La paradoja de Cantor es el nombre que recibe una contradicción que se deriva del teorema de Cantor junto con la suposición de que existe un conjunto que contiene a todos los conjuntos, el conjunto universal. ${\displaystyle V}$. Para distinguir esta paradoja de la otra que se trata más abajo, es importante notar la naturaleza de esta contradicción. Según el teorema de Cantor ${\displaystyle |{\mathcal {P}}(X)|>|X|}$ para todo conjunto ${\displaystyle X}$. Por otra parte, todos los elementos de ${\displaystyle {\mathcal {P}}(V)}$ son conjuntos, y por lo tanto están contenidos en ${\displaystyle V}$, por lo tanto ${\displaystyle |{\mathcal {P}}(V)|\leq |V|}$.^[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]​

${\displaystyle R_{A}=\left\{\,x\in A:x\not \in x\,\right\}.}$

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:

${\displaystyle R_{U}\in R_{U}\iff R_{U}\notin R_{U}.}$

Esta argumentación se denomina la paradoja de Russell.^[2]​ Es de notar que la versión de la paradoja de Russell que hemos presentado aquí es en realidad un teorema de Zermelo;^[3]​ se puede concluir a partir de la contradicción obtenida que debemos rechazar la hipótesis que R_U∈U, refutando así la existencia de un conjunto que contiene todos los conjuntos.

Esto es posible porque hemos usado comprensión restringida (como se muestra en ZFC) en la definición de R_A anterior, lo que a su vez implica que

${\displaystyle R_{U}\in R_{U}\iff (R_{U}\in U\wedge R_{U}\notin R_{U}).}$

Si se hubiese utilizado la comprensión irrestricta (como por ejemplo en el sistema de Frege) para definir el conjunto de Russell simplemente como ${\displaystyle R=\left\{\,x:x\not \in x\,\right\}}$, entonces el sistema de axioma mismo hubiera implicado la contracicción, sin necesidad de recurrir a otras hipótesis.^[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. Cuando el conjunto de partida es el de los números naturales N, la coincidencia entre estos dos métodos es la hipótesis de continuidad debida al mismo Cantor. 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). La hipótesis del continuo es entonces que este cardinal es el de todas las partes de N.

Cantor demostró este resultado en 1891, para el conjunto de funciones características de N (el conjunto de los números enteros naturales), y luego para el conjunto de funciones características del intervalo de los números reales entre 0 y 1. Afirmó, sin embargo, que el resultado podía generalizarse a cualquier conjunto, lo que su método permitía sin ambigüedades.

Zermelo enunció (y demostró) este resultado, que denominó teorema de Cantor (en alemán Satz von Cantor) en su artículo de 1908^[4]​, el primero en presentar una axiomatización de la teoría de conjuntos.

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. Entonces "no-phi-x(x)", es decir, "phi-x no se sostiene de x" es una función proposicional no contenida en esta correlación; porque es verdadera o falsa de x según phi-x sea falsa o verdadera de x, y por lo tanto difiere de phi-x para cada valor de x". Russell atribuye la idea de esta prueba a Cantor.

• Teorema de Cantor-Bernstein-Schröder
• Axiomas de Zermelo-Fraenkel

• Paul Halmos, Naive set theory. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition).
• Jech, Thomas, 2003. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer. ISBN 3-540-44085-2.

• Weisstein, Eric W. «Cantor's Theorem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.  (en inglés)