Deux ensembles E et F ont même cardinal, ce que l'on note Card(E) = Card(F), s'il existe une bijection  \( f\)  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  \( f\)  de E sur E',  \( f\)  est alors une injection de E dans F. En complétant l'inverse  \( f^{-1}\) de \( f\)  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.

Une démonstration ancestrale

Prenons une injection  \( f\)  de E dans F et une injection g de F dans E. On appelle ancêtre d'un élément de E son antécédent par g (s'il existe), puis l'antécédent de cet antécédent par  \( f\)  et ainsi de suite. Notons E_p, E_i et E_∞ respectivement l'ensemble des éléments de E ayant un nombre pair, impair et infini d'ancêtres. On fait de même pour F pour obtenir F_p, F_i et F_∞.

Vous vous convaincrez sans difficulté que  \( f\)  est une bijection de E_p sur Fi (de même,  \( f\)  est une bijection de E_∞ sur F_∞) et que g est une bijection de F_p sur E_i (donc sa réciproque est une bijection de E_i sur F_p). On construit ainsi une bijection de E sur F, ce qui établit le résultat cherché.

Un résultat simple est valable pour tous les ensembles finis : si un ensemble E possède n éléments, l'ensemble  \( \mathcal{P}\) (E) des parties de E possède 2ⁿ éléments et n < 2ⁿ. Ces deux résultats sont faciles à établir par récurrence. L'inégalité se généralise aux ensembles infinis ; c'est l'objet du théorème de Cantor.

Dans le cas où l'ensemble E est fini, une démonstration particulièrement élégante met en œuvre une récurrence sur le cardinal n de E. Si n = 0, E est vide et sa seule partie est le vide donc \( \mathcal{P}\) (E) possède 1 = 2⁰ élément. Admettons que si E possède n éléments, \( \mathcal{P}\) (E) en a 2ⁿ et considérons un ensemble F à n+1 éléments. Prenons-en un, soit x. En le retirant à F, on obtient un ensemble F' ayant n éléments et \( \mathcal{P}\) (F') a 2ⁿ éléments d'après l'hypothèse de récurrence. Les parties de F se partagent en deux classes, celles qui contiennent x et celles qui ne le contiennent pas. Les éléments de la seconde classe sont les parties de F' alors que ceux de la première sont de la forme X  \( \cup\)  {x} où X est une partie de F'. Chacune de ces classes a donc le même nombre d'éléments que \( \mathcal{P}\) (F'), soit 2ⁿ. En tout,  \( \mathcal{P}\) (E) possède donc 2.2ⁿ = 2ⁿ⁺¹ éléments. Le résultat est donc prouvé par récurrence.

Dans le cas où E est infini, on dispose du théorème de Cantor : si E est un ensemble, Card(E) < Card( \( \mathcal{P}\) (E)), au sens qu'il ne peut exister de bijection entre E et \( \mathcal{P}\) (E).

Un résultat particulièrement déroutant

Pour démontrer ce résultat profond, Cantor a utilisé son célèbre argument diagonal (voir en encadré), adapté à ce contexte ensembliste. Il s'agit d'un raisonnement par l'absurde particulièrement déroutant. On suppose d'abord qu'il existe une surjection  \( f\)  de E sur \( \mathcal{P}\) (E) et on considère l'ensemble A des éléments de E n'appartenant pas à leur image par  \( f\) . Comme A est une partie de E, il possède un antécédent x par  \( f\) , soit A = f ({x}). On s'aperçoit alors que cet élément x ne trouve sa place nulle part ! Si on le voit dans A, on se trompe puisque les éléments de A n'appartiennent pas à leur image par  \( f\)  qui, en l'occurrence, est A. Si on le voit hors de A, on se trompe encore puisque, par construction, il doit alors appartenir à son image, qui est A.

Le théorème de Cantor implique l'existence d'une infinité d'infinis différents même si, dans la pratique, on n'en utilise que deux : le dénombrable (l'infini des entiers) et le continu (l'infini des réels).