Théorème de Cantor-Bernstein
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 axiomatique des ensembles. Il est nommé en l'honneur des mathématiciens Georg Cantor, Felix Bernstein et Ernst Schröder. Cantor en donna une première démonstration (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment...), mais qui utilisait implicitement l'axiome (Un axiome (du grec ancien αξιωμα/axioma, « considéré comme digne, convenable, évident en soi ») désigne une...) du choix. Bernstein et Schröder en donnèrent des démonstrations qui ne dépendaient pas de cet axiome.

Énoncé

S'il existe une injection (Le mot injection peut avoir plusieurs significations :) f d'un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut...) E vers un ensemble F, et une injection g de l'ensemble F vers l'ensemble E, alors il existe une bijection (Une fonction f: X → Y est dite bijective ou est une bijection si pour tout y dans l’ensemble d'arrivée Y il existe un et un seul x dans l’ensemble de définition X tel que f(x) = y. On dit encore...) h de E sur F.

\left\{\begin{matrix}\exist f \in F^E \;{\rm injective} \\ \exist g \in E^F \;{\rm injective} \end{matrix} \right. \Rightarrow \exist h \in F^E \;{\rm bijective}

Démonstration n°1

Lemme préliminaire

Commençons par montrer que si u est une application injective d'un ensemble A vers un ensemble B avec B \subset A, alors il existe une bijection v de A sur B.

Théorème de Cantor-Bernstein.

Soit (C_n)_{n \in \mathbb N} la suite définie par :

\left\{\begin{matrix} C_0 = A - B \\ \forall n \in \mathbb{N}^*, C_n = u( C_{n-1} ) \end{matrix} \right.

Soit C la réunion (La Réunion est une île française du sud-ouest de l'océan Indien située dans l'archipel des Mascareignes à environ 700 kilomètres à l'est de Madagascar et à 170 kilomètres au sud-ouest...) de tous les ensembles (C_n)_{n \in \mathbb N} : C=\bigcup_{n \in \mathbb N}C_n

Soit alors v l'application de A dans B défini par :

\begin{matrix}v: & x \in C & \mapsto & u(x)\\ & x \notin C& \mapsto & x \end{matrix}

v est bien défini à valeurs dans B, car u est à valeur dans B, et si x \notin C alors x \notin C_0 et donc x \in B.

Montrons que v est injective. Soient alors x et y deux éléments de A tel que v(x) = v(y)

  • Supposons que x \in C et y \notin C.
Alors v(x) \in C (car C est stable par v) et y=v(y) \notin C. Or v(x) = v(y) ce qui est absurde.
  • Supposons que x \in C et y \in C.
Alors v(x) = u(x) = v(y) = u(y). Comme u est injective x = y.
  • Supposons que x \notin C et y \notin C.
Alors x = y = v(x) = v(y)
Dans tous les cas x = y, donc v est injective.

Montrons que v est surjective. Soit y \in B. Montrons qu'il existe un x \in A tel que v(x) = y.

  • Si y \in C
alors il existe i \in \mathbb{N}^* tel que y \in C_i. (i est strictement positif car y \in B, donc y \notin C_0).
Il existe donc x \in C_{i-1} \subset C tel que u(x) = v(x) = y.
  • Si y \notin C
alors v(y) = y

Donc v est bijective. Ce qui démontre la première proposition.

Interprétation

On peut donner une interprétation concrète (La concrète est une pâte plus ou moins dure obtenue après extraction d’une matière première fraîche d’origine végétale (fleurs, feuille) par...) 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, à un spectateur x associe le spectateur y = u(x) assis à la place de x.

C0 est l'ensemble des spectateurs initialement debout. Ces spectateurs se rendent à leur place et délogent leur occupant. Ceux-ci forment alors l'ensemble C1. Ces derniers procèdent de même. Cn désigne les spectateurs debout à la n-ème étape. Ils vont aux places qu'ils ont réservé 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, à un spectateur x qui doit se lever, associe 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 (En mathématiques, une application réciproque est en des termes simples une fonction qui « fait exactement l'inverse de ce que fait une application...) 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, à un spectateur y jamais dérangé, associe y lui-même.

Démonstration finale du théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à partir d'axiomes. Un théorème est à distinguer...)

Montrons alors le théorème initial.

Soit B = g(F) l'image de F par l'application g injective. L'application u= g \circ f est une application injective de E dans B, avec B \subset E. Donc il existe une application bijective v de E sur B. Comme g est une injection, la restriction de g a son image pour l'espace d'arrivée est une bijection de F sur B. Donc la composée g^{-1} \circ v est une bijection de E sur F, ce qui démontre le théorème de Cantor-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 axiomatique des ensembles. Il est...).

Démonstration n°2

Un lemme préliminaire

Cette démonstration repose sur le lemme suivant, cas particulier du théorème de Knaster-Tarski. Soit E un ensemble et G : \mathfrak P(E) \to \mathfrak P(E) (où \mathfrak P(E) est l'ensemble des parties de E) une application croissante, i.e. A \subset B \Longrightarrow G(A) \subset G(B). Alors G admet un point fixe (En mathématiques, pour une application f d’un ensemble E dans lui-même, un élément x de E est un point fixe de f si f(x) = x.), i.e. \exists M, G(M) = M.

En effet, posons S = \{A \;|\; A \subset G(A)\} et M = \cup_{A \in S} A. Alors :

  • pour tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) A \in S, d'une part A \subset G(A), d'autre part A \subset M \Longrightarrow G(A) \subset G(M) car G est croissante. Donc M = \cup_{A \in S} A \subset \cup_{A \in S} G(A) \subset G(M) et donc M \in  S. M est donc la partie maximale de S
  • M \subset G(M) donc G(M) \subset G(G(M)) car G est croissante. Donc G(M) \in S donc G(M) \subset M compte tenu de la maximalité de M comme élément de S. On a donc bien G(M) = M

Démonstration finale

Soient maintenant f injective de E dans F et g injective de F dans E. Pour toute partie A de E. On pose G(A) = Eg(Ff(A)). On calcule f(A) ensemble des images des éléments de A par f, on en prend le complémentaire dans F, on prend l'ensemble g(Ff(A)) des images des éléments de cette partie par g et on prend le complémentaire dans E. Il n'est pas difficile de vérifier que G est croissante.

On introduit alors la partie M du lemme préliminaire. Cette partie est invariante par G ce qui signifie que g(Ff(M)) est exactement le complémentaire de M dans E.

On pose :

si x \in M, \phi(x) = f(x)
si x \notin M, \phi(x) = g^{-1}(x)

φ est bijective de E dans F.

M joue (La joue est la partie du visage qui recouvre la cavité buccale, fermée par les mâchoires. On appelle aussi joue le muscle qui sert principalement à ouvrir et fermer la...) un rôle comparable à la partie C dans la première démonstration ou à E_p \cup E_{\infty} dans la démonstration qui suit.

Démonstration n° 3

Appelons ancêtres d'un élément x de E l'antécédent de x par g (s'il existe) puis l'antécédent de cet antécédent par f, etc. Procédons de même pour les éléments de F.

Notons Ep (resp. Ei) l'ensemble des éléments de E ayant un nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) pair (resp. impair) d'ancêtres. Ep n'est autre que la partie C de la première démonstration. Notons E_\infty l'ensemble des éléments de E ayant un nombre infini (Le mot « infini » (-e, -s ; du latin finitus, « limité »), est un adjectif servant à qualifier quelque chose qui n'a pas de limite en nombre ou en taille.) d'ancêtres. Ep, Ei et E_\infty forment une partition de E. Définissons de même Fp, Fi et F_\infty.

f est une bijection de Ep sur Fi et aussi de E_\infty sur F_\infty. g est une bijection de Fp sur Ei, et sa réciproque (La réciproque est une relation d'implication.) est donc une bijection de Ei sur Fp.

On peut ainsi construire une bijection de E sur F.

Applications

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 élements à un autre d'un ensemble connu dont le nombre d'élements 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 (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une pièce sont sa longueur, sa largeur et sa profondeur/son épaisseur, ou bien son diamètre si c'est une...) 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'élements ". 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 (La généralisation est un procédé qui consiste à abstraire un ensemble de concepts ou d'objets en négligeant les détails de...)

Soit X un ensemble non vide (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.) et \sim une relation d'équivalence sur l'ensemble des parties de X. On suppose qu'elle vérifie les deux propriétés:

  • si A˜B alors il existe une bijection f de A dans B telle que, pour tout sous-ensemble (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou encore B est sur-ensemble de A, si tout élément du sous-ensemble A est aussi...) C de A, f(CC;
  • si A_{1} \cap A_{2}=B_{1} \cap B_{2}=\emptyset et A1˜B1 et A2˜B2 alors A_{1} \cup A_{2} \sim B_{1} \cup B_{2}.

Soient deux ensembles A et B, un sous-ensemble A1 de A et un sous-ensemble B1 de B. On suppose que A˜B1 et B˜A1. Alors A˜B.

Ceci peut également être démontré sans l'axiome du choix[1]. Dans le cas particulier ou X=E \cup F et \sim est la relation d'équipotence (En théorie des ensembles, deux ensembles E et F sont dits équipotents, ce qu'on note E ≈ F, s'il existe une bijection de E sur F. On dira alors que deux ensembles équipotents ont la même cardinalité, c'est-à-dire la même...), on retrouve le résultat précédent.

Page générée en 1.314 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique