Théorème de Cantor-Bernstein

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Théorème de Bernstein.

Le théorème de Cantor-Bernstein, également appelé théorème de Cantor-Schröder-Bernstein, est un théorème de la théorie des ensembles qui affirme l’existence d'une bijection entre deux ensembles à partir du moment ou il existe deux injections, l'une du second vers le premier l'autre du premier vers le second. Il est nommé ainsi en référence aux mathématiciens Georg Cantor, Felix Bernstein et Ernst Schröder. Cantor en donna une première démonstration, mais qui utilisait implicitement l'axiome du choix. Bernstein en donna une démonstration qui ne dépendait pas de cet axiome.

Historique[modifier | modifier le code]

Georg Cantor énonce ce théorème sans démonstration en 1887, puis en donne une preuve dans son livre Sur les fondements de la théorie des ensembles transfinis (1895-1897), en utilisant la théorie des ordinaux[1]. Felix Bernstein, élève de celui-ci, en esquisse une autre démonstration dès 1896 à l'âge de 18 ans. Elle est publiée en 1898 sur proposition de Cantor dans Leçons sur la théorie des fonctions sous la plume d'Émile Borel[2],[3]. Ernst Schröder donne une esquisse de démonstration en 1896 qui se révèle erronée, et qu'il complète en 1898[4].

Richard Dedekind en fit lui-même une démonstration en 1897 mais qui ne fut publiée qu'en 1930. Ernst Zermelo en fait une autre en 1906 qui reprend en fait les idées de Dedekind.

Énoncé[modifier | modifier le code]

S'il existe une injection d'un ensemble vers un ensemble et une injection de vers , alors il existe une bijection de sur .

Trois démonstrations[modifier | modifier le code]

Première démonstration[modifier | modifier le code]

Lemme préliminaire[modifier | modifier le code]

Commençons par montrer que si est une application injective d'un ensemble vers une de ses parties, , alors il existe une bijection de sur .

Théorème de Cantor-Bernstein.

Soit la suite définie par :

Soit la réunion de tous les ensembles  : .

Soit alors l'application de dans définie par :

est bien définie à valeurs dans , car est à valeurs dans , et si alors et donc .

envoie injectivement dans  ; et le complémentaire de identiquement dans lui-même. C'est donc une injection.

Montrons que est surjective. Soit . Montrons qu'il existe un tel que .

  • Si  : alors il existe tel que ( est strictement positif car , donc ). Il existe donc tel que .
  • Si  : alors

Ainsi, est bijective, ce qui démontre la première proposition.

Interprétation[modifier | modifier le code]

On peut donner une interprétation concrète du résultat montré ci-dessus. A est l'ensemble (infini) des spectateurs d'un théâtre (infini). Chaque spectateur a réservé une place, et initialement, on suppose que chaque place est occupée par un spectateur, mais pas forcément par le spectateur qui a réservé cette place. B est alors l'ensemble des spectateurs assis. Par ailleurs, les ensembles étant infinis, il peut rester des spectateurs debout. L'application u est l'application qui associe, à un spectateur x, le spectateur y = u(x) assis à la place de x.

est l'ensemble des spectateurs initialement debout. Ces spectateurs se rendent à leur place et délogent leur occupant. Ceux-ci forment alors l'ensemble . Ces derniers procèdent de même. désigne les spectateurs debout à la n-ème étape. Ils vont aux places qu'ils ont réservées et en chassent leurs occupants. On itère une infinité de fois. C désigne l'ensemble des spectateurs qui se sont levés au moins une fois (y compris ceux qui étaient debout initialement).

L'application v désigne l'application qui associe, à un spectateur x qui doit se lever, le spectateur y qu'il va déloger, ou bien qui, à un spectateur x qui reste toujours assis, associe x lui-même. L'application réciproque de v est l'application qui, à un spectateur y qui est dérangé, associe le spectateur x qui vient prendre sa place, ou bien qui associe, à un spectateur y jamais dérangé, y lui-même.

Démonstration finale du théorème[modifier | modifier le code]

Montrons alors le théorème initial.

Soit B = g(F) l'image de F par l'injection g. L'application u = g o f est une injection de E dans B, avec . Donc il existe une bijection v de E sur B. Comme g est une injection et g(F) = B, elle définit par restriction une bijection h de F sur B. La composée h-1v est une bijection de E sur F, ce qui démontre le théorème de Cantor-Bernstein.

Deuxième démonstration[modifier | modifier le code]

Un lemme préliminaire[modifier | modifier le code]

Article détaillé : Théorème de Knaster-Tarski.

Cette démonstration repose sur le lemme suivant, cas particulier du théorème de Knaster-Tarski.

Soit un ensemble, l'ensemble de ses parties et une application croissante, c'est-à-dire telle que . Alors admet un point fixe, c'est-à-dire qu'il existe une partie de telle que .

Démonstration finale[modifier | modifier le code]

Soient maintenant injective de dans et injective de dans . Pour toute partie de , on pose , c'est-à-dire que s'obtient en prenant l'image directe , puis le complémentaire dans de cette image, puis l'image directe par de ce complémentaire, et enfin le complémentaire dans de cette image. Il n'est pas difficile de vérifier que est croissante.

On introduit alors la partie du lemme préliminaire. Cette partie est invariante par , ce qui signifie que est le complémentaire de dans .

Théorème de Cantor-Bernstein.

On définit une bijection en posant :

si  ;
si .

joue un rôle comparable à la partie dans la première démonstration ou à dans la démonstration qui suit.

Troisième démonstration[modifier | modifier le code]

Supposons, sans perte de généralité, que et sont disjoints. Appelons ancêtres d'un élément de l'antécédent de par (s'il existe) puis l'antécédent de cet antécédent par , etc. Procédons de même pour les éléments de .

Notons (resp. ) l'ensemble des éléments de ayant un nombre pair (resp. impair) d'ancêtres. n'est autre que la partie de la première démonstration. Notons l'ensemble des éléments de ayant un nombre infini d'ancêtres. , et forment une partition de . Définissons de même , et .

est une bijection de sur et aussi de sur . est une bijection de sur , et sa réciproque est donc une bijection de sur .

Théorème de Cantor-Bernstein.

On peut ainsi construire une bijection de sur .

Applications[modifier | modifier le code]

Si l'on considère la technique naïve qu'a un enfant pour compter le nombre d'éléments d'un ensemble, cela revient quasiment toujours à associer chacun des éléments à un autre d'un ensemble connu dont le nombre d'éléments est connu.

Il peut s'agir soit d'associer chacun des éléments à compter avec l'un des doigts, soit d'associer chacun des éléments avec un nombre que l'on réciterait à haute voix (un, deux, trois, etc.), par exemple.

En clair, compter se fait naïvement en effectuant une bijection d'un ensemble dont la « dimension » est connue vers un autre dont la dimension est inconnue.

Ce théorème s'interprète alors comme disant : « Si je peux compter une partie d'un ensemble avec la totalité des éléments d'un autre ensemble, et réciproquement, alors ils ont le même nombre d'éléments ». Ce qui est évident pour des ensembles finis. Ce théorème généralise alors cette notion pour des ensembles infinis.

« Si je peux compter un certain nombre de billes de mon sac de billes avec mes dix doigts, et qu'avec la totalité de mes billes, je peux les associer avec certains de mes doigts, alors j'ai exactement dix billes. »

À partir de là, ce théorème représente l'une des briques de base pour généraliser la notion de tailles d'ensembles à des ensembles infinis.

Généralisation[modifier | modifier le code]

Soient X un ensemble non vide et une relation d'équivalence sur l'ensemble des parties de X. On suppose qu'elle vérifie les deux propriétés :

  • si alors il existe une bijection telle que, pour toute partie de ,  ;
  • si et et alors .

Soient deux ensembles et , un sous-ensemble de et un sous-ensemble de . On suppose que et . Alors .

Cette généralisation peut, elle aussi, être démontrée sans l'axiome du choix[5].

Dans le cas particulier où et est la relation d'équipotence, on retrouve le résultat précédent.

Notes et références[modifier | modifier le code]

  1. Georg Cantor, Sur les fondements de la théorie des ensembles transfinis, trad. française de 1899, énoncé p. 347 et démonstration p. 395, sur Gallica.
  2. F. Casiro, « Le théorème de Cantor-Bernstein », Tangente, mai-juin 2008, p. 42-44.
  3. Émile Borel, Leçons sur la théorie des fonctions, p. 104.
  4. (en) William W. Tait (en), « Michael Potter, Set Theory and its Philosophy (Book Review) », History and Philosophy of Logic, vol. 26, no 2,‎ , p. 145-172 (lire en ligne), p. 164.
  5. (en) Stan Wagon (en), The Banach-Tarski Paradox, CUP (ISBN 978-0-521-45704-0, lire en ligne)[réf. incomplète].

Article connexe[modifier | modifier le code]

Propriété de Schröder-Bernstein (en)