Théorème de Cantor

vignette|Georg Cantor Le théorème de Cantor est un théorème mathématique, dans le domaine de la théorie des ensembles. Il énonce que le cardinal d'un ensemble E est toujours strictement inférieur au cardinal de l'ensemble de ses parties P(E), c'est-à-dire essentiellement qu'il n'existe pas de bijection entre E et P(E). Combiné avec l'axiome de l'ensemble des parties et l'axiome de l'infini de la théorie des ensembles usuelle, ce théorème implique qu'il existe une hiérarchie infinie d'ensembles infinis en termes de cardinalité. Le théorème a été démontré en 1891 par Georg Cantor à l'aide d'un raisonnement astucieux mais simple, l'argument diagonal. 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 2n éléments. Il est alors aisé de vérifier (par exemple par récurrence) que, pour tout entier n, n < 2n, 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 par f : n'a pas d'antécédent, c'est-à-dire n'est l'image par f d'aucun élément de E.