Théorème de Cantor-Bernstein

Je me souviens avoir essayé quand j’étais étudiant. Je n’avais pas totalement réussi, mais j’avais très bien compris ce qui se passait. Quand j’ai lu la preuve ensuite (qui n’est pas très longue, ni très difficile, mais il faut réussir à écrire correctement l’application), je l’ai trouvé complètement naturelle.

Tout le monde n'est pas Blaise Pascal, redécouvrant seul à douze ans la géométrie. Pour les gens moyens ou « normaux » (comme moi), et pour les résultats un peu délicats, genre « théorème de...», je préconise de regarder la démonstration, et même plusieurs démonstrations différentes s'il y en a, pour en synthétiser et assimiler une. Il reste suffisamment de problèmes qu'on peut ensuite chercher. Ou alors, couper la poire en deux, et chercher un problème avec des questions intermédiaires qui conduisent au théorème (de mémoire, il me semble que pour Cantor-Bernstein il y en a un dans le Ramis-Deschamps-Odoux). Je pense qu'il faut optimiser ses efforts. Mais ce n'est qu'un avis personnel.
Bon courage.
Fr. Ch.

Je te donne une indication si tu veux:

Soient $E,F,f,g$ avec $f$ injecte $E$ dans $F$ et $g$ injecte $F$ dans $E$.

On pose $h:=g^{-1}:=\{(x,y)\mid (y,x)\in g\}$

Alors il existe une bijection $h:E\to F$ telle que $h\subset (f\cup h)$.

Ca réduit les errements :-D

En gros, CB parait "difficile" car énoncé de manière qui donne la possibilité d'errer au hasard dans beaucoup d'endroits, mais c'est un phénomène en fait bien plus rigide qui se produit.

Edit enblue, merci Max.

CB est un corollaire du théorème suivant:(Birkhoff-Tarski) soit $(X,\leq)$ un ensemble ordonné dans lequel toute partie possède une borne supérieure (exemple: si $E$ est un ensemble, prendre pour $X$ l'ensemble des parties de $E$ et pour $\leq$, l'inclusion ensembliste). Soit $f:X\to X$ une fonction croissante (pour tous $a,b\in X$ tels que $a\leq b$, on a $f(a) \leq f(b)$). Alors $f$ possède un point fixe.

Merci Max, oui, tu as raison évidemment

Si vous voulez vous mettre à la place de l'auteur du fil je vous donne un énoncé de même difficulté mais dont les preuves par coeur sont moins connues.

Si E+E est en bijection avec F+F alors E et F sont en bijection

@Foys : je ne suis plus très sûr mais il me semble que la preuve avec le théorème du point fixe ne suppose pas connue l'existence de $\mathbb{N}$ (ou de $\omega$), contrairement aux deux autres.

Est-ce exact ?

Martial : oui ! (enfin je n'en connais qu'une autre, donc pas sûr de ce que tu appelles "les deux autres", mais en tout cas on n'utilise pas $\omega$ dans celle du point fixe)

christophe : j'en connais 2 (j'imagine incluses dans celles que Martial connait), la deuxième (pas par le point fixe de Knaster-Tarski) est essentiellement une reformulation de celle avec le point fixe.

C'est une reformulation qui 1- explicite le point fixe obtenu (puisqu'une version de Knaster-Tarski est constructive) et 2- est plus facilement explicable à des gens qui n'ont pas d'expérience en TDE (et plus intuitive, plus imagée, on peut faire plus de dessins etc.); mais c'est essentiellement la même.

La troisième, par contre, je ne sais pas :-D

@Max : merci ! Je donne une esquisse des 3 preuves ci-dessous.

@Christophe : 1) Il y a celle (la plus classique à mon sens) donnée page 8 dans le livre de Patrick. (J'ai la flemme de recopier, et puis je ne veux pas casser la baraque à 20100N).
2) Il y a celle avec les "ancêtres" à laquelle Foys fait allusion plus haut. Soient $f : A \to B$ et $g : B \to A$ des injections. Pour $x \in A$ on appelle ancêtre de $x$ l'antécédent de $x$ par $g$ (s'il existe), l'antécédent par $f$ de l'antécédent par $g$ de $x$ (toujours s'il existe), etc. Tu partitionnes $A$ en ceux qui ont un nombre pair d'ancêtres, ceux qui ont un nombre impair d'ancêtres, et ceux qui en ont une infinité. Tu fais la même chose dans $B$, et après tu recolles les morceaux de façon adéquate.
3) Il y a celle avec le théorème du point fixe, qui est conceptuellement plus complexe, mais qui a l'avantage de ne pas présupposer $\omega$, comme vient de le confirmer Max.

Enfin, je crois qu'il y a un petit malin qui s'est amusé à donner une preuve de CB qui utilise Zorn, mais la seule fois où je l'ai vue je l'ai oubliée dans les 5 mn, car c'est vraiment de la méchanceté !

Purée, je vais mettre une croix dans le calendrier : c'est bien la première fois que je t'apprends quelque chose, lol.

Christophe: oui et non :-D
ça dépend de ce que tu fais dans la preuve avec point fixe: celle-ci marche pour tout point fixe choisi et a priori il y en a plusieurs (ça ne doit pas être compliqué de trouver des exemples où c'est le cas), et donc cette preuve "construit" plusieurs bijections; alors que celle avec pair/impair n'en construit qu'une. Si on prend le plus petit point fixe (je crois - ou en tout cas un truc du genre), ça va donner la même bijection, mais si on s'autorise un point fixe arbitraire, non .

@Martial: tu m'as appris des tas de choses, y compris en théorie des ensembles, lors de nos conversations, tu as collecté une vraie masse d'informations, tu ne t'en rends pas compte toi-même j'ai l'impression, tu pourrais revendiquer l'ouverture d'une bibliothèque et t'en faire le gardien. ;-)

Je ne sais pas ce que savent les set theorist professionnels, mais comme ils visent la résolution de problèmes ouverts, ils mettent de côté des tas de survenues culturelles dans leur milieu qui fait que si ça se trouve, même eux ne savent pas tout ce que tu as collecté.

christophe c écrivait http://www.les-mathematiques.net/phorum/read.php?16,2234382,2235756#msg-2235756: Un truc qu'il ne faut pas citer ;-)

"Si E+E est en bijection avec F+F alors E et F sont en bijection" ?

Tentative de réponse et je suppose que E+E désigne l'ensemble des élements de type a,b où a et b appartiennent à E (et je noterais A et B les élements de F)

Si E et F ont un nombre fini d'éléments ça paraît simple:

- On note Ce le nombre d'élements de E et Cf celui de F, alors le nombre d'éléments de E+E est Ce^2 et celui le F+F est Cf^2.

Si E+E et F+F sont en bijection alors ils ont le même nombre d'élements, Ce^2 = Cf^2 donc Ce = Cf.

Si Ce = Cf il suffit de numéroter leurs élements pour avoir une bijection: numéro 1 de E avec numéro 1 de F etc.

On peut extrapoler ce raisonnement à tous les ensembles dénombrables E et F: le nombre d'élements est aussi grand qu'on veut mais on peut toujours numéroter leurs éléments et établir cette correspondance.

Restent les ensembles dont on ne peut pas numéroter les élements.

Et là on va se coucher.

Note à moi-même:
1 - E et F sont interchangeables dans la démonstration.
2 - Si X implique Y, non-Y implique non-X.
3 - Si A et a non liés par bijection (idem pour B et b) alors a minima injection (ou surjection, cf 1) [NON?]

Khee Nok a écrit:

je suppose que E+E désigne l'ensemble des élements de type a,b où a et b appartiennent à E

Tu confonds $E+E$ avec $E \times E$.

Alesha, Martial : oui, mea culpa. Merci.

Y a quelque chose qui cloche là-dedans
J'y retourne immédiatement