Théorème de Cantor-Bernstein

Théorème

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

Commentaire

La démonstration de ce théorème se trouve facilement dans les cours de théorie des ensembles.
Elle est un peu longue (environ une page) et un peu difficile. Mais voici d'une part une version "intuitive" de cette démonstration.

D'autre part une autre démonstration rigoureuse, hypercourte et méconnue, basée sur un résultat fondamental (méconnu aussi, à mon avis à tort). Au début que j'y ai pensé, je la croyais inconnue jusque-là. Finalement, une petite recherche sur le web a permis de la retrouver ici et de découvrir le nom du théorème sur lequel elle se base: théorème de Tarski-Knaster. Seulement dommage que la page du théorème de Tarski-Knaster qui y figure contient une énorme bourde: même si l'ensemble des points fixes est un treillis complet, et que la stabilité par bornes sup et bornes inf implique la complétude, néanmoins la stabilité par bornes sup et bornes inf est fausse dans le cas général (il y a un contre-exemple très facile), même s'il peut certes être vrai dans des cas particuliers comme en l'occurence celui de l'application utilisée pour Cantor-Bernstein.
Bon, un autre texte en anglais qui utilise la même méthode.

Le truc est donc d'utiliser le théorème de Tarski-Knaster, ou plutôt une première étape de ce théorème (existence d'un point fixe, et du coup on peut mentionner l'existence d'un plus grand et d'un plus petit point fixe, sans aller jusqu'à montrer que c'est un treillis complet), résultat méconnu, pourtant assez facile à démontrer et très utile par ailleurs si on veut fonder les mathématiques rigoureusement sans trop de complications, en particulier justifier simplement et rigoureusement le principe de définition des suites par récurrence (ou par induction sur les ordinaux ou les ensembles bien-fondés: c'est pour ça que j'ai pensé nécessaire de l'introduire, non pour Cantor-Bernstein !).

Cette démonstration rigoureuse, donc, est d'apparence moins explicite que la démonstration traditionnelle (ben oui, pour voir une chose comme explicite il faut prendre le temps de l'expliciter), mais c'est au fond une autre présentation de la même construction (en effet c'est la même bijection qui est obtenue). En particulier cela n'utilise pas l'axiome du choix.

Démonstration intuitive

Imaginons l'ensemble E des personnes venues assister à un match de foot dans un stade muni d'un ensemble F de sièges. Chaque personne x avait un billet de réservation pour le siège i(x). Hélas, ces gens indisciplinés se sont assis n'importe où, au point que les derniers arrivés ne trouvèrent plus de place: chaque siège (y) était occupé par j(y). Alors, les gens debout allèrent a leurs sièges réservés et chassèrent les personnes mal élevées qui les avaient pris. Ces dernières firent de même, et ainsi de suite. Une éternité plus tard, tout le monde était assis (x sur f(x)), et le match put enfin commencer.

Démonstration formelle


Théorème utilisé : toute application croissante de l'ensemble des parties d'un ensemble dans lui-même a un point fixe.


Acceptant donc ce résultat, le théorème de Cantor-Bernstein en découle comme suit:

L'application qui à toute partie A de E associe E\j[F\i[A]] étant croissante, a un point fixe M. Alors l'application qui à tout x de E associe i(x) si x appartient à M et j-1(x) sinon, est une bijection de E sur F.
CQFD

Voir mes textes sur les fondements des mathématiques que j'ai finalement complétés jusqu'à ces résultats (décembre 2005), même s'il reste beaucoup d'idées en projet pour la suite. Si je vous invite à aller voir, ce n'est pas principalement pour la démonstration du théorème ci-dessus (qui peut aisément se faire indépendamment en une demie-page), mais plutôt parce que j'y expose des points de vue originaux sur bien d'autres notions "élémentaires" des mathématiques.

On en discute sur Les-mathématiques.net


Retour