Voir la source de Théorème de Cantor-Bernstein

{{Voir homonymes|Cantor|Bernstein}}
{{Voir paronymes|Théorème de Bernstein}}
[[Fichier:Theoreme cantor bernstein.png|vignette|L'existence d'une injection de E vers F et d'une injection de F vers E, implique l'existence d'une bijection de E vers F.]]

Le '''théorème de Cantor-Bernstein''', également appelé '''théorème de Cantor-Schröder-Bernstein''', est le [[théorème]] de la [[théorie des ensembles]] qui affirme l’existence d'une [[bijection]] entre deux ensembles dès lors qu'il existe deux [[injection (mathématiques)|injections]], l'une du second vers le premier l'autre du premier vers le second.

{{Théorème|énoncé=S'il existe une injection d'un ensemble E vers un ensemble F et une injection de F vers E, alors il existe une bijection de E sur F.}}

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]]{{Référence nécessaire|date=11 octobre 2018}}. Bernstein en donna une démonstration qui ne dépendait pas de cet axiome. Cependant, toutes les démonstrations données utilisent le [[principe du tiers exclu]] et de ce fait ne sont pas acceptées par les [[Intuitionnisme|intuitionnistes]]<ref>{{Ouvrage|langue=en|auteur1=Ettore Carruccio|titre=Mathematics and Logic in History and in Contemporary Thought|éditeur=Transaction Publishers|année=2006|passage=354|isbn=978-0-202-30850-0}}</ref>. En 2019, Cécilia Pradic et Chad E. Brown montrent que le théorème de Cantor Bernstein implique le  [[principe du tiers exclu]]<ref>{{Article|langue=anglais|auteur1=Cécilia Pradic|auteur2=Chad E. Brown|titre=Cantor-Bernstein implies Excluded Middle|périodique=arxiv|date=19/04/2019|lire en ligne=https://arxiv.org/abs/1904.09193|accès url=libre|format=pdf}}</ref> en [[théorie des ensembles]] [[Intuitionnisme|intuitionniste]].

== Historique ==
[[Fichier:CantorEquivalenceTheorem1887b.gif|vignette|upright=2|Énoncé original de Cantor (1887).]]
[[Georg Cantor]] énonce ce théorème sans démonstration en 1887<ref>Georg Cantor, ''Sur les fondements de la théorie des ensembles transfinis'', trad. française de 1899, [https://gallica.bnf.fr/ark:/12148/bpt6k29057h/f9.image.r= énoncé] p. 347</ref>. En 1895, Cantor remarque dans la première partie de ''{{lang|fr|Beiträge zur Begründung der transfiniten Mengenlehre}}'' (« Sur les fondements de la théorie des ensembles transfinis ») que le théorème se déduit de la propriété de [[Trichotomie (mathématiques)|trichotomie]] pour les cardinaux (Cantor considère en effet que [[théorème de Zermelo|tout ensemble peut être bien ordonné]], ce qui équivaut à l'[[axiome du choix]]), mais renvoie a une publication ultérieure la démonstration de cette propriété<ref> [https://gallica.bnf.fr/ark:/12148/bpt6k29057h/f57.image.r= démonstration] p. 395, sur Gallica.</ref>.

[[Felix Bernstein]], élève de celui-ci, produit une démonstration qui n'utilise pas les bons ordres (et ne nécessite pas l'axiome du choix) 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]]<ref>F. Casiro, « Le théorème de Cantor-Bernstein », ''[[Tangente (magazine)|Tangente]]'', mai-juin 2008, p. 42-44.</ref>{{,}}<ref>Émile Borel, [https://archive.org/stream/leconstheoriefon00borerich#page/n117/mode/2up ''Leçons sur la théorie des fonctions''], {{p.|104}}.</ref>.

[[Ernst Schröder]] publie lui aussi une démonstration en 1898<ref>{{article| langue=de| prénom=Ernst | nom=Schröder | lien auteur=Ernst Schröder|éditeur=Kaiserliche Leopoldino-Carolinische Deutsche Akademie der Naturforscher | titre=Ueber zwei Definitionen der Endlichkeit und G. Cantor’sche Sätze | journal=Nova Acta | volume=71 | numéro=6 | périodique=Johann Ambrosius Barth Verlag | lieu=Halle a.&nbsp;S. | année=1898 | pages=303–362 (336-344) | url=https://www.biodiversitylibrary.org/item/45265#page/331/mode/1up}}.</ref>, mais celle-ci s'avère erronée<ref>{{citation étrangère|lang=en|… the question why Schröder’s name is so often associated with a result towards which his sole contribution was to provide a fallacious proof.}}, {{article |langue=en|auteur={{lien|William W. Tait}}|titre=Michael Potter, ''Set Theory and its Philosophy'' (Book Review)|journal= History and Philosophy of Logic| volume=26| numéro= 2|année=2005 |pages = 162-166 | lire en ligne=http://www.tandfonline.com/doi/abs/10.1080/01445340412331313602}}, {{p.|164}}.</ref>. L'erreur est repérée en 1902 par [[Alwin Korselt]] qui en fait part à Schröder début {{date-|mai 1902}}<ref name="Korselt">{{article |langue=de| prénom=Alwin | nom= Korselt | titre=Über einen Beweis des Äquivalenzsatzes | journal=[[Mathematische Annalen]] | volume=70 | numéro=2 | périodique=B.&nbsp;G. Teubner | lieu=Leipzig | année=1911 | pages=294–296 | ISSN=0025-5831 | url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN235181684_0070&DMDID=DMDLOG_0029 | doi=10.1007/bf01461161}}</ref>. Celui-ci reconnaît que la paternité de la démonstration du théorème revient entièrement à Bernstein, dans une réponse envoyée quinze jours plus tard<ref name="Korselt"/> (un mois avant sa mort). Il ajoute s'être lui-même rendu compte du problème en 1901 et en avoir fait part alors à son ami [[Max Dehn]]<ref>{{citation étrangère|lang=de|… Daß ich Herrn F. Bernstein die Ehre, den G. Cantorschen Satz bewiesen zu haben, allein überlasse, hatte ich einstweilen einem Freunde desselben, Herrn Dr. Max Dehn (jetzt in Münster) schon vorigen Herbst resp. Sommer — natürlich zum Weitergeben — gesagt}}, extrait d'une lettre de Schröder à Körselt du 23 mai 1902, cité par {{harvsp|Korselt|1911}}.</ref>.

Korselt soumet fin {{date-|mai 1902}} un article aux [[Mathematische Annalen]], où il expose l'erreur de Schröder et propose une autre démonstration, mais celui-ci n'est publié qu'en 1911. Pendant tout ce temps la preuve de Schröder est considérée comme correcte, en particulier par Cantor, [[Giuseppe Peano|Peano]] et [[Arthur Moritz Schoenflies|Schönflies]]<ref>{{Ouvrage|langue=en|prénom1=Gregory H.|nom1=Moore|titre=Zermelo's Axiom of Choice Its Origins, Development, and Influence|éditeur=Springer|collection=Studies in the History of Mathematics and Physical Sciences|numéro dans collection=8|année=1982|passage=48|isbn=978-0-387-90670-6}}.</ref>.

[[Richard Dedekind]] avait rédigé une preuve du théorème de Cantor-Bernstein dès 1887, pour laquelle il utilise sa théorie des chaînes publiée dans son ouvrage ''{{lang|de|Was sind und was sollen die Zahlen ?}}'' (1888). Elle a été retrouvée après sa mort et publiée seulement en [[1930]]<ref>{{harvsp|Hinkis|2013|p=87}}.</ref>.

Ignorant alors cette démonstration<ref>{{harvsp|Hinkis|2013|p=89}}.</ref>, [[Ernst Zermelo]] publie deux démonstrations du théorème en 1901 puis en 1908, toutes deux fondées sur la théorie des chaînes de Dedekind, dont la seconde s'avère très similaire à celle de Dedekind<ref>{{harvsp|Hinkis|2013|p=129}}.</ref>. Zermelo avait déjà envoyé sa seconde preuve à [[Henri Poincaré|Poincaré]] début [[1906]], en réponse à une critique de Poincaré sur l'usage de l'induction complète ([[définition par récurrence]] et [[raisonnement par récurrence]]) dans les preuves alors connues du théorème de Cantor-Bernstein. Cette critique est accompagnée d'une version détaillée de la preuve de Bernstein-Borel qui met en évidence l'usage de l'induction complète. Elle avait été publiée dans la [[Revue de métaphysique et de morale]] en {{date-|janvier 1906}}. La preuve de Zermelo n'utilise pas les entiers, et donc manifestement pas de récurrence. En réponse, Poincaré publie dans la même revue en mai de la même année une adaptation en français de la démonstration de Zermelo, dont il critique l'usage de l'[[imprédicativité]], critiques auxquelles répond Zermelo en 1908<ref>{{harvsp|Hinkis|2013|p=196}}.</ref>.

== Trois démonstrations ==

=== Première démonstration ===

==== Lemme préliminaire ====
On commence par montrer que si <math>u</math> est une application injective d'un ensemble <math>A</math> vers une de ses parties, <math>B</math>, alors il existe une bijection <math>v</math> de <math>A</math> sur <math>B</math>.

[[Fichier:Cantor1.png|300px|right|Théorème de Cantor-Bernstein.]]
Soit <math>(C_n)_{n \in\N}</math> la suite définie par :
::<math>\left\{\begin{matrix} C_0 = A\setminus B \\ \forall n \in\N^*, C_n = u( C_{n-1} ) \end{matrix} \right.</math>

Soit <math>C</math> la réunion de tous les ensembles <math>(C_n)_{n\in\N}</math> : <math>C=\bigcup_{n\in\N}C_n</math>.

Soit alors <math>v</math> l'application de <math>A</math> dans <math>B</math> définie par :
::<math>\begin{matrix}v: & x \in C & \mapsto & u(x)\\ & x \notin C& \mapsto & x \end{matrix}</math>

<math>v</math> est bien définie à valeurs dans <math>B</math>, car <math>u</math> est à valeurs dans <math>B</math>, et si <math>x\notin C</math> alors <math>x\notin C_0</math> et donc <math>x\in B</math>.

<math>v</math> envoie injectivement <math>C</math> dans <math>u(C)=\cup_{n\in\N}u(C_n)=\cup_{m\in\N^*}C_m\subset C</math> ; et le complémentaire de <math>C</math> identiquement dans lui-même. C'est donc une injection.

Montrons que <math>v</math> est [[Surjection|surjective]]. Soit <math>y\in B</math>. Montrons qu'il existe un <math>x\in A</math> tel que <math>v(x)=y</math>.
:* Si <math>y \in C</math> : alors il existe <math>i\in\N^*</math> tel que <math>y\in C_i</math> (<math>i</math> est strictement positif car <math>y\in B</math>, donc <math>y\notin C_0</math>). Il existe donc <math>x\in C_{i-1} \subset C</math> tel que <math>v(x)=u(x)=y</math>.
:* Si <math>y\notin C</math> : alors <math>v(y)=y</math>

Ainsi, <math>v</math> est bijective, ce qui démontre la première proposition.

==== Interprétation ====
On peut donner une interprétation 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''.

<math>C_0</math> est l'ensemble des spectateurs initialement debout. Ces spectateurs se rendent à leur place et en délogent les occupants. Ceux-ci forment alors l'ensemble <math>C_1</math>. Ces derniers procèdent de même. <math>C_n</math> 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 ====
Montrons alors le théorème initial.

Soit ''B'' = ''g''(''F'') l'image de ''F'' par l'injection ''g''. L'application ''u'' = ''g'' <small>o</small> ''f'' est une injection de ''E'' dans ''B'', avec <math>B \subset E</math>. 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''<sup>-1</sup>∘''v'' est une bijection de ''E'' sur ''F'', ce qui démontre le théorème de Cantor-Bernstein<ref>{{lien web |url=https://www.cs.swan.ac.uk/~csulrich/ftp/MatthewGwynne1008.pdf |titre=CSM25 - The Cantor-Schröder-Bernstein Theorem |consulté le=4 decembre 2022 |website=www.cs.swan.ac.uk}} (En fait, la démonstration commence à la page 3.)</ref>.

=== Deuxième démonstration ===

==== Un lemme préliminaire ====
{{Voir|Théorème de Knaster-Tarski}}
Cette démonstration repose sur le lemme suivant, cas particulier du [[théorème de Knaster-Tarski]]{{Refsou|date=31 janvier 2019}}.
{{énoncé|Soit <math>E</math> un ensemble, <math>P(E)</math> l'ensemble de ses parties et <math>G:P(E)\to P(E)</math> une application croissante, c'est-à-dire telle que <math>A\subset B\Rightarrow G(A)\subset G(B)</math>. Alors <math>G</math> admet un [[point fixe]], c'est-à-dire qu'il existe une partie <math>M</math> de <math>E</math> telle que <math>G(M) = M</math>.}}

==== Démonstration finale ====
Soient maintenant <math>f</math> injective de <math>E</math> dans <math>F</math> et <math>g</math> injective de <math>F</math> dans <math>E</math>. Pour toute partie <math>A</math> de <math>E</math>, on pose <math>G(A)=E\setminus g\left[F\setminus f(A)\right]</math>, c'est-à-dire que <math>G(A)</math> s'obtient en prenant l'[[image directe]] <math>f(A)</math>, puis le [[Complémentaire (théorie des ensembles)|complémentaire]] dans <math>F</math> de cette image, puis l'image directe par <math>g</math> de ce complémentaire, et enfin le complémentaire dans <math>E</math> de cette image. Il n'est pas difficile de vérifier que <math>G:P(E)\to P(E)</math> est croissante.

On introduit alors la partie <math>M</math> du lemme préliminaire. Cette partie est invariante par <math>G</math>, ce qui signifie que <math>g\left[F\setminus f(M)\right]</math> est le complémentaire de <math>M</math> dans <math>E</math>.

[[Fichier:Cantor3.png|400px|center|Théorème de Cantor-Bernstein.]]

On définit une bijection <math>h:E\to F</math> en posant :
: si <math>x \in M, h(x) = f(x)</math> ;
: si <math>x \notin M, h(x) = g^{-1}(x)</math>.

<math>M</math> joue un rôle comparable à la partie <math>C</math> dans la première démonstration ou à <math>E_E\cup E_{\infty}</math> dans la démonstration qui suit.

=== Troisième démonstration ===
Cette démonstration est essentiellement celle publiée par [[Julius König]] en 1906<ref>{{Article|auteur=J. König|titre=Sur la théorie des ensembles|journal=[[Comptes rendus hebdomadaires des séances de l'Académie des sciences]]|volume=143| pages=110-112| année=1906| url=https://gallica.bnf.fr/ark:/12148/bpt6k30977.image.f110.langEN}}.</ref>, et souvent reprise depuis<ref>Par exemple 
{{Ouvrage | prénom1=Garrett | nom1=Birkhoff | lien auteur1=Garrett Birkhoff | prénom2=Saunders | nom2=Mac Lane | lien auteur2=Saunders Mac Lane | titre=A Survey of Modern Algebra | éditeur=[[Macmillan Publishers|Macmillan]] | année=1977 | année première édition=1941 | passage=387-388 | isbn=0-02-310070-2}},
{{Ouvrage|prénom1=Andreï|nom1=Kolmogorov|lien auteur1=Andreï Kolmogorov|prénom2=Sergueï|nom2=Fomine|lien auteur2=Sergei Fomine|titre=Éléments de la théorie des fonctions et de l'analyse fonctionnelle|éditeur=Mir|année=1977|passage=22|isbn=}} (première édition en français 1974), {{Ouvrage|langue=en|auteur1=[[John L. Kelley]]|titre=General Topology|éditeur=Van Nostrand|année=1955|passage=28|lire en ligne=https://archive.org/stream/GeneralTopology/Kelley-GeneralTopology#page/n45/mode/2up}} (réédité chez Springer-Verlag), {{Cori-Lascar II}}, 1993.</ref>.

Supposons, [[sans perte de généralité]], que [[Union disjointe#Union disjointe de deux ensembles|<math>E</math> et <math>F</math> sont disjoints]].
[[Fichier:Cantor2.png|thumb|upright=2|Théorème de Cantor-Bernstein (les ensembles <math>E_E</math>, <math>E_F</math>, <math>F_F</math> et <math>F_E</math> sont notés ici respectivement <math>E_p</math>, <math>E_i</math>, <math>F_p</math> et <math>F_i</math>).]]
À élément <math>x</math> de <math>E</math>, on associe une suite <math>(x_0, x_1, \dots)</math> finie ou infinie [[définition par récurrence|définie par récurrence]] de la façon suivante. La valeur initiale est <math>x_0 = x</math>. Supposons  <math>x_n</math> défini (sinon <math>x_{n+1}</math> n'est pas défini), alors :
* si <math>x_n\in E</math> possède un antécédent par ''g'', alors <math>x_{n+1}</math> est cet (unique) antécédent (remarque : dans ce cas ''n'' est pair) ;
* si <math>x_n\in F</math> possède un antécédent par ''f'', alors <math>x_{n+1}</math> est cet (unique) antécédent (remarque : dans ce cas ''n'' est impair) ;
* dans les autres cas <math>x_{n+1}</math>n'est pas défini.

Trois cas sont alors possibles pour la suite <math>(x_0, x_1, \dots)</math> qui permettent de partitionner <math>E</math> en trois ensembles :
* <math>E_E</math> est l'ensemble des <math>x\in E</math> tels que la suite <math>(x_0, x_1, \dots)</math> correspondante est finie et s'arrête sur un élément de <math>E</math> (de façon équivalente, l'indice du dernier élément est pair) ;
* <math>E_F</math> est l'ensemble des <math>x\in E</math> tels que la suite <math>(x_0, x_1, \dots)</math> correspondante est finie et s'arrête sur un élément de <math>F</math> (de façon équivalente, l'indice du dernier élément est impair) ;
* <math>E_\infty</math> est l'ensemble des <math>x\in E</math> tels que la suite <math>(x_0, x_1, \dots)</math> correspondante est infinie.

On partitionne <math>F</math> de façon analogue en <math>F_F</math>, <math>F_E</math> et <math>F_\infty</math>. Alors :
* <math>f</math> est une bijection de <math>E_E</math> sur <math>F_E</math>, ainsi que de <math>E_\infty</math> sur <math>F_\infty</math> ;
* <math>g</math> est une bijection de <math>F_F</math> sur <math>E_F</math>, et sa réciproque est donc une bijection de <math>E_F</math> sur <math>F_F</math>.
On obtient ainsi une bijection de <math>E</math> sur <math>F</math><ref>Cette démonstration suit de près {{harvsp|Kolmogorov|Fomine|1977|p=22}} et {{harvsp|Cori-Lascar II|texte=Cori et Lascar 1993|p=148-149}}, qui simplifient légèrement {{harvsp|König|1906}} et explicitent l'utilisation de la définition par récurrence, et donc des entiers. La preuve de {{harvsp|Kelley|1955}} qui n'explicite pas la définition des suites récurrente est incorrecte, car le partitionnement est défini selon le caractère fini et la parité du nombre d'éléments de l'ensemble image des suites <math>(x_n)</math> et <math>(y_n)</math>. Or cet ensemble peut être fini, si la suite correspondante est infinie mais présente un cycle. Ceci a été remarqué par [[Leslie Lamport]], [http://lamport.azurewebsites.net/pubs/lamport-how-to-write.pdf ''How to Write a Proof''], 1993, p. 8, qui prend cette preuve comme exemple d'une preuve informelle fausse, dont l'erreur apparaît quand il essaye de la présenter de façon structurée, mais qui est difficile sinon à déceler.</ref>.

== Généralisation ==
Soient ''X'' un ensemble non vide et <math>\sim</math> une [[relation d'équivalence]] sur l'[[ensemble des parties]] de ''X''.
On suppose qu'elle vérifie les deux propriétés :
* si <math>A\sim B</math> alors il existe une bijection <math>f:A\to B</math> telle que, pour toute partie <math>C</math> de <math>A</math>, <math>f(C)\sim C</math> ;
* si <math>A_1\cap A_2=B_1\cap B_2=\varnothing</math> et <math>A_1\sim B_1</math> et <math>A_2\sim B_2</math> alors <math>A_1\cup A_2\sim B_1\cup B_2</math>.
Soient deux ensembles <math>A</math> et <math>B</math>, un sous-ensemble <math>A_1</math> de <math>A</math> et un sous-ensemble <math>B_1</math> de <math>B</math>. On suppose que <math>A\sim B_1</math> et <math>B\sim A_1</math>. Alors <math>A\sim B</math>.

Cette généralisation peut, elle aussi, être démontrée sans l'[[axiome du choix]]<ref>{{Ouvrage|langue=en|auteur1=[[Stan Wagon]]|titre=The Banach-Tarski Paradox|éditeur=[[Cambridge University Press|CUP]]|année=1993|pages totales=253|isbn=978-0-521-45704-0|lire en ligne={{Google Livres|_HveugDvaQMC}}}}{{refinc|date=13/10/2016}}.</ref>.

Dans le cas particulier où <math>X=E\cup F</math> et <math>\sim</math> est la relation d'[[équipotence]], on retrouve le résultat précédent.

== Notes et références ==
{{Références}}

== Voir aussi ==
=== Articles connexes ===

* [[Théorème de comparabilité cardinale]]
* {{Lien|langue=en|trad=Schröder–Bernstein property|fr=Propriété de Cantor-Bernstein}}

=== Bibliographie ===
* {{Article|langue=en|url=https://link.springer.com/content/pdf/10.1007%2Fs00283-011-9242-3.pdf|titre=Cantor-Bernstein’s Theorem in a Semiring|auteur=Marcel Crabbé|revue=[[The Mathematical Intelligencer]]|année=2011|vol=33|numéro=3|page=80}}
* {{Ouvrage|langue=en|prénom1=Arie|nom1=Hinkis|titre=Proofs of the Cantor-Bernstein theorem, a mathematical excursion|éditeur=Birkhäuser|année=2013|pages totales=456|isbn=978-3-0348-0788-3|doi=10.1007/978-3-0348-0224-6}}

{{Portail|mathématiques}}

[[Catégorie:Théorème de la théorie des ensembles|Cantor-Bernstein]]
[[Catégorie:Georg Cantor]]
[[Catégorie:Article contenant une démonstration]]