Théorème de 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 des ses parties P(E), c'est-à-dire essentiellement qu'il n'existe pas de bijection entre E et P(E).

Le théorème a été démontré en 1891 par Georg Cantor, à l'aide d'un raisonnement astucieux mais simple, l'argument diagonal.

Sommaire 1 Les ensembles finis 2 Cas général 3 Conséquences du théorème 4 Historique 5 Voir aussi 6 Bibliographie

Les ensembles finis

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 que, pour tout entier n, n < 2ⁿ, et 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). L'argument de Cantor qui suit est cependant tout à fait valable également pour les ensembles finis.

Cas général

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 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 :

D={x ∈ E | x ∉ f(x)}

n'appartient pas à l'image de f. On le déduit par un raisonnement par l'absurde. 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, et 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.

Ce type de raisonnement, que l'on appelle argument diagonal, a été utilisé sous une forme très proche par Russell (et Zermelo) pour le paradoxe de l'ensemble des ensembles qui ne s'appartiennent pas.

Conséquences du théorème

On déduit directement du théorème de Cantor qu'il n'existe pas de plus grand cardinal, au sens de la subpotence. En présence de l'axiome du choix, tout ensemble est bien ordonné, et donc le théorème de Cantor montre qu'il n'y a pas de plus grand aleph (ni de plus grand ordinal). cependant il existe une autre méthode pour montrer ce résultat, l'ordinal de Hartogs d'un ensemble quelconque (bien ordonné ou non) 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.

Historique

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, le premier à présenter une axiomatisation de la théorie des ensembles.

Voir aussi

• Théorème de Cantor-Bernstein

Bibliographie

• Georg Cantor (1891) —Über eine elementare Frage der Mannigfaltigskeitslehre, Jahresericht der Deutsch. Math.Vereing., Vol. I, pp 75-78 (1890-1891). Repris dans le volume ci-dessous (voir sur le centre de numérisation de Göttingen [1])
• Georg Cantor (1932) – Gesammelte Abhandlungen mathematischen und philosophischen inhalts. éd. par Ernst Zermelo.
• Ernst Zermelo (1908) — Untersuchungen über die Grundlagen der Mengenlehre I, Mathematische Annalen, volume 65, pp 261-281, traduction anglaise dans Jean van Heijenoort (1967), From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931, Harvard Univ. Press, pp 199-215, ISBN= 978-0674324497.

• Portail des mathématiques