Deux ensembles E et F ont même cardinal, ce que l'on note Card(E) = Card(F), s'il existe une bijection ff de E sur F. Il s'agit d'une relation d'équivalence sur la classe des ensembles. On parle ici de « classe » car on ne peut parler d'ensemble de tous les ensembles. Cette relation est bien réflexive, symétrique et transitive puisque l'identité est une bijection, que l'inverse d'une bijection en est une et que la composée de deux bijections également.
-
L'ensemble de tous les ensembles --------------------------------
Pourquoi l'ensemble de tous les ensembles n'existe pas ? L'ensemble de tous les ensembles serait l'ensemble dont les éléments seraient tous les ensembles. Bertrand Russell montre qu'un tel objet ne peut exister. En effet, imaginons qu'il existe. Cet ensemble hypothétique appartient alors à lui-même, par définition. Cette affirmation semble étrange, mais pourquoi pas ? A priori, aucune logique ne nous interdit de le penser. Par esprit de contradiction, considérons alors les ensembles n'appartenant pas à eux-mêmes, puis l'ensemble de ces ensembles. Où est-il ? S'il s'appartient, il ne s'appartient pas, et s'il ne s'appartient pas, il s'appartient. Une histoire de fou, n'est-ce pas ? Sans précaution, il est possible de fabriquer de telles chimères. Pour l'ensemble de tous les ensembles, n'insistons pas : il faut l'exclure.
Revenons aux cardinaux. On note de même Card(E) ≤ Card(F) si E a le même cardinal qu'une partie de F. Dans ce cas, il existe une partie E' de F et une bijection ff de E sur E', ff est alors une injection de E dans F. En complétant l'inverse f−1f^{-1} de ff en associant n'importe quel élément de E aux éléments du complémentaire E' dans F, on obtient une surjection de F dans E. On démontre facilement que Card(E) ≤ Card(F) équivaut à l'existence d'une injection de E dans F comme à celle d'une surjection de F dans E. Ces équivalences permettent de montrer aisément que la relation d'inégalité des cardinaux sur la classe des ensembles est réflexive et transitive. Le paragraphe suivant prouve également qu'elle est antisymétrique, ce qui constitue le théorème de Cantor–Bernstein : si E et F sont deux ensembles tels qu'il existe une injection de E dans F et une injection de F dans E, alors il existe une bijection de E sur F. Il s'agit donc d'une relation d'ordre sur la classe des ensembles.