Théorème de Cantor

Le résultat est connu de longue date pour les ensembles finis. En effet supposons que E possède n éléments, on démontre facilement que l'ensemble des parties de E contient 2ⁿ éléments. Il est alors aisé de vérifier (par exemple par récurrence) que, pour tout entier n, n < 2ⁿ, et l'on sait alors — c'est le principe des tiroirs — qu'il n'existe pas d'injection de P(E) dans E, donc pas de bijection. Mais l'argument de Cantor qui suit et qu'il a développé pour les ensembles infinis est en fait tout à fait valable également pour les ensembles finis.

On se contente pour ce théorème d'une approche de la cardinalité, en particulier des ensembles infinis, par l'équipotence. Dire d'un ensemble A qu'il a un cardinal strictement inférieur à celui d'un ensemble B, c'est dire qu'il existe une injection de A dans B, mais pas de bijection entre ces deux ensembles. De façon équivalente (par le théorème de Cantor-Bernstein), c'est également dire qu'il existe une injection de A dans B mais pas d'injection de B dans A. L'existence d'une injection de E dans P(E) est immédiate (associer à un élément son singleton).

Pour montrer qu'il n'existe pas de bijection, l'argument de Cantor, dit argument diagonal, est le suivant. Soit f une application d'un ensemble E dans son ensemble des parties P(E). Alors le sous-ensemble des éléments de E qui n'appartiennent pas à leur image par f :

${\displaystyle D=\{x\in E\mid x\not \in f(x)\}}$

n'a pas d'antécédent, c'est-à-dire n'est l'image par f d'aucun élément de E. On le déduit du raisonnement par l'absurde suivant. S'il était l'image d'un élément y de E, soit D = f(y), alors :

• si y est dans D, par construction de D, y n'appartient pas à son image… c'est-à-dire que y n'appartient pas à D ;
• si y n'est pas dans D, toujours d'après la construction de D, y doit appartenir à son image… c'est-à-dire à D.

Les deux hypothèses mènent bien à une contradiction.

On a donc montré qu'aucune fonction de E dans P(E) n'est surjective (ni, a fortiori, bijective).

Comme on a montré qu'il n'existe pas de surjection de E dans P(E) (et pas simplement qu'il n'existe pas de bijection), on peut en déduire plus directement que par le théorème de Cantor-Bernstein qu'il n'existe pas d'injection de P(E) dans E. En effet s'il en existait une, soit g, on construirait une surjection de E dans P(E) en associant à chaque élément de E son unique antécédent par g s'il existe, et l'ensemble vide (qui appartient toujours à P(E)) sinon.

Du point de vue de la cardinalité, le théorème de Cantor a pour conséquence l'existence pour tout ensemble d'un ensemble de cardinal strictement supérieur, c'est-à-dire qu'il n'existe pas de plus grand cardinal (au sens introduit ci-dessus, il n'existe pas d'ensemble dans lequel tout ensemble pourrait s'injecter). En présence en particulier de l'axiome du choix, il est possible de définir les nombres cardinaux comme des nombres ordinaux particuliers, grâce au théorème de Zermelo. Dans la théorie des ensembles ZFC (avec axiome du choix), le théorème de Cantor montre qu'il n'y a pas de plus grand cardinal également en ce sens. Cependant, ce dernier résultat peut s'énoncer et se démontrer sans utiliser l'axiome du choix ; la démonstration utilise également un raisonnement diagonal, mais fait intervenir directement la notion de bon ordre (voir aleph (nombre) et ordinal de Hartogs).

On peut également se servir du théorème de Cantor pour montrer qu'il n'existe pas d'ensemble de tous les ensembles (on parle parfois du paradoxe de Cantor, du moins dans une théorie des ensembles qui permet de développer ces notions), puisque celui-ci inclurait l'ensemble de ses parties. On aurait donc une injection de l'ensemble de ses parties dans cet ensemble, ce qui est absurde. Cependant ce résultat s'obtient plus directement à partir du paradoxe de l'ensemble des ensembles qui ne s'appartiennent pas : l'existence d'un ensemble de tous les ensembles permet de formaliser celui-ci, et donc aboutit à une contradiction, en présence du seul schéma d'axiomes de compréhension (ou de séparation).

En fait ce paradoxe, dû à Russell et, indépendamment, à Zermelo, utilise un raisonnement très proche de celui utilisé pour le théorème de Cantor, et Russell a d'ailleurs déclaré qu'il l'avait découvert en analysant la démonstration de celui-ci[2]. L'argument du théorème de Cantor reste correct si f est une application de E dans un ensemble ayant pour éléments toutes les parties de E, et n'ayant que des ensembles pour éléments. C'est le cas si E est l'ensemble de tous les ensembles, et l'on peut choisir pour f l'identité sur E (on n'a plus besoin de parler de l'ensemble des parties). La construction de Russell apparait alors comme une reformulation de l'argument de Cantor.

Il existe une autre méthode pour montrer qu'il n'existe pas de plus grand cardinal : l'ordinal de Hartogs d'un ensemble quelconque est de cardinal strictement supérieur à celui de l'ensemble initial. Quand l'ensemble de départ est celui des entiers naturels N, la coïncidence entre ces deux méthodes est l'hypothèse du continu due au même Cantor. Plus précisément, on montre que l'ensemble des ordinaux au plus dénombrables a également un cardinal strictement supérieur à celui de N (résultat dû à Cantor). L'hypothèse du continu est alors que ce cardinal est celui de l'ensemble des parties de N.

Cantor démontre ce résultat en 1891, pour l'ensemble des fonctions caractéristiques de N (ensemble des entiers naturels), puis pour l'ensemble des fonctions caractéristiques de l'intervalle des réels entre 0 et 1. Il affirme cependant que le résultat se généralise à n'importe quel ensemble, ce que permet sans ambiguïté sa méthode.

Zermelo énonce (et démontre) ce résultat qu'il appelle théorème de Cantor ((de) Satz von Cantor) dans son article de 1908[3], le premier à présenter une axiomatisation de la théorie des ensembles.