Dos conjuntos E y F tienen la misma cardinalidad, lo que se escribe Card(E) = Card(F), si existe una biyección ff de E sobre F. Es una relación de equivalencia sobre la clase de los conjuntos. Hablamos aquí de «clase» porque no podemos hablar del conjunto de todos los conjuntos. Esta relación es reflexiva, simétrica y transitiva, pues la identidad es una biyección, la inversa de una biyección también lo es y la composición de dos biyecciones también es una biyección.
-
El conjunto de todos los conjuntos --------------------------------
¿Por qué no existe el conjunto de todos los conjuntos? El conjunto de todos los conjuntos sería aquel cuyos elementos fueran todos los conjuntos. Bertrand Russell demuestra que tal objeto no puede existir. En efecto, imaginemos que existe. Por definición, este conjunto hipotético pertenece a sí mismo. Esta afirmación parece extraña, pero ¿por qué no? A priori, ninguna lógica nos impide pensarlo. Para llegar a una contradicción, consideremos entonces los conjuntos que no pertenecen a sí mismos y, después, el conjunto de esos conjuntos. ¿Dónde está? Si pertenece a sí mismo, no pertenece a sí mismo; y si no pertenece a sí mismo, pertenece a sí mismo. Una historia de locos, ¿verdad? Sin las debidas precauciones, es posible fabricar tales quimeras. No insistamos con el conjunto de todos los conjuntos: hay que excluirlo.
Volvamos a las cardinalidades. Del mismo modo, escribimos Card(E) ≤ Card(F) si E tiene la misma cardinalidad que un subconjunto de F. En este caso, existe un subconjunto E' de F y una biyección ff de E sobre E', ff es entonces una inyección de E en F. Si completamos la inversa f−1f^{-1} de ff asociando un elemento cualquiera de E a los elementos del complemento de E' en F, obtenemos una aplicación sobreyectiva de F sobre E. Se demuestra fácilmente que Card(E) ≤ Card(F) equivale tanto a la existencia de una inyección de E en F como a la de una aplicación sobreyectiva de F sobre E. Estas equivalencias permiten mostrar sin dificultad que la relación de desigualdad entre cardinalidades sobre la clase de los conjuntos es reflexiva y transitiva. El párrafo siguiente demuestra asimismo que es antisimétrica, lo que constituye el teorema de Cantor–Bernstein: si E y F son dos conjuntos tales que existe una inyección de E en F y una inyección de F en E, entonces existe una biyección de E sobre F. Por tanto, es una relación de orden sobre la clase de los conjuntos.