Théorème de Cantor-Bernstein - Définition

Énoncé

S'il existe une injection f d'un ensemble E vers un ensemble F, et une injection g de l'ensemble F vers l'ensemble E, alors il existe une bijection h de E sur F.

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 E_p (resp. E_i) l'ensemble des éléments de E ayant un nombre pair (resp. impair) d'ancêtres. E_p n'est autre que la partie C de la première démonstration. Notons l'ensemble des éléments de E ayant un nombre infini d'ancêtres. E_p, E_i et forment une partition de E. Définissons de même F_p, F_i et .

f est une bijection de E_p sur F_i et aussi de sur . g est une bijection de F_p sur E_i, et sa réciproque est donc une bijection de E_i sur F_p.

On peut ainsi construire une bijection de E sur F.

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 (où est l'ensemble des parties de E) une application croissante, i.e. . Alors G admet un point fixe, i.e. .

En effet, posons et . Alors :

• pour tout , d'une part , d'autre part car G est croissante. Donc et donc . M est donc la partie maximale de S

• donc car G est croissante. Donc donc 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 , c'est-à-dire que G(A) s'obtient en prenant l'ensemble f(A) des images par f des éléments de A, puis le complémentaire dans F de cet ensemble d'images par f, puis l'ensemble des images par g des éléments de ce complémentaire, et enfin le complémentaire dans E de cet ensemble d'images par g. 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(F − f(M)) est exactement le complémentaire de M dans E.

On pose :

si

si

h est bijective de E dans F.

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

Généralisation

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 f de A dans B telle que, pour tout sous-ensemble C de A, ;
• si et et alors .

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

Ceci peut également être démontré sans l'axiome du choix. Dans le cas particulier où et est la relation d'équipotence, on retrouve le résultat précédent.

Références

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'é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.