Une démonstration du théorème Cantor Bernstein.

Je sais, mais bon de temps en temps, il faut se servir un peu plus de notre cerveau et j'ai décidé que c'était pour aujourd’hui.

Soient f une injection d'un ensemble  vers un ensemble B et g une injection de B vers A. Montrons qu'il existe alors une bijection h de A sur B.

Considérons Co = A \ g(B). Co est l'ensemble des points n'admettant pas d'antécédent par l'application g. Cette partie Co est le petit grain de sable qui empêche g d'être bijective (à l'exception bien sûre, du cas où Co est vide, situation où il n'y a plus rien à démontrer). Le plan d'attaque est de faire rebondir Co et ses avatars afin de diluer sa nuisance à l'infini.

Pour cela, posons C1 = {g(f(x)) | x € Co}, et, plus généralement, pour tout naturel n, Cn+1 = {g(f(x)) | x € Cn}.

L'application h convoitée est définie de la manière suivante :

h(x) = f(x) si, pour un certain entier n, x appartient à l'avatar Cn,

h(x) = g-1(x) sinon.

Précisons deux points pour ce dernier cas. Tout d'abord l'injection g permet de définir une bijection B sur g(B), dont l'application réciproque est notée, par abus de langage, g-1.

Ensuite, si x appartient à A sans appartenir à aucun des Cn-1 (et donc pas à Co) alors x € g(B) et g-1(x) existe bien!

Le travail de vérification peut commencer.

On introduit la partie Dn, de B définie par :

Dn = {f(x) | x € Cn}, de sorte que Cn+1 = {g(y) | y € Dn}.

Pour montrer que h est injective, considérons deux éléments distincts x et x' de A.

Puisque f et g-1 sont injectives, le seul point qui puisse éventuellement poser problème est le cas ou x € Cm pour un certain entier m et où x' € Cn' pour tout entier n.

 Nous avons alors :

h(x) = f(x) € Dm et h(x') = g-1(x') not € Dm (sinon x' serait dans Cm+1).

De sorte que h(x) not = h(x').

Pour terminer, montrons que tout élément de B admet un antécédent par h.

Il est clair que les seuls éléments de B qui puissent échapper à l'emprise de h sont les y qui n'appartiennent à aucun des Dn. Mais où se trouve alors g(y)?

Certainement pas dans Co, et s'il n'est pas dans Cn, il n'est pas plus dans Cn+1 puisque Cn+1 = {g(u) | u € Dn} et y not € Dn (l'injectivité intervient ici).

Ainsi g(y) not € Cn pour tout entier n.

Par conséquent, h(g(y)) = g-1(g(y)) = y.

On a bien y € h(A).

h est injective et surjective, c'est une bijection de A sur B.

Et il se suicida