Khôlle : Cantor et ses ensembles

[Nightmare]

Salut à vous :happy3:

Pour la reprise, une petite khôlle de théorie des ensembles. En fait, il faut préciser que j'en ai déjà fait une en début d'année (bien avant que je commence à les poster sur le forum) axée sur les notions d'injection - surjection - bijection. Ces notions sont donc supposées "connues" (mais sont rappelées quand même) ainsi que les propriétés de base.

Rappels : On (re)définit les notions suivantes :

Une fonction est dite injective (resp. surjective) si tout élément de B a au plus (resp. au moins )1 antécédent par f dans A. Une fonction est bijective si elle est à la fois injective et surjective.

Etant donné un ensemble fini A, on note son cardinal, ie son nombre d'élément. Si A et B sont des ensembles quelconques, on notera s'il existe une injection de A dans B, s'il existe une surjection de A dans B et si A et B sont en bijection (on dira qu'ils sont équipotents). (A priori, les symboles d'ordre n'ont aucun rapport avec l'ordre entre les réels. Le I]1) permet de justifier a posteriori la notation pour des ensembles finis).


-------------------------------------------------------------------

I] Lien avec la notion de cardinal

. 1) Soit A et B deux ensembles finis. On suppose qu'il existe une fonction injective. Que dire des cardinaux de A et B ?

. 2) Soient A et B deux ensembles quelconques. Montrer que s'il existe une surjection de A dans B, alors il existe une injection de B dans A.

. 3) A et B sont deux ensembles finis de même cardinal, f une application de A vers B. Montrer l'équivalence entre les propositions suivantes :

a) f est injective
b) f est surjective
c) f est bijective

II] Cantor I :

Soient A et B deux ensembles quelconque. On se propose de montrer que s'il existe une injection f de A dans B et une injection g de B dans A, alors A et B sont équipotents.

. 1) Montrer ce théorème lorsque A et B sont finis

. 2) Montrer le théorème dans le cas quelconque.

Aide : étant donné x fixé dans A, on examine la chaine d'antécédents . On partitionne alors A en deux sous-ensembles : Le premier contenant les x pour lesquels la chaine précédente s'arrête sur un élément de A sans antécédent par g dans B, le deuxième étant son complémentaire, contenant les x pour lesquels la chaine est infinie ou s'arrête sur un élément de B sans antécédent par f dans A. Faire un dessin est conseillé

III] Cantor II

Soit A un ensemble quelconque. On note l'ensemble de ses parties.

. 1) Si A est fini, quel est le cardinal de P(A) ?

. 2) Si A est quelconque, montrer qu'il n'existe pas d'injection de P(A) dans A.

Aide : Soit surjective. Considérer

Amusez-vous bien !

[Ben314]

Salut,
Fait un peu gaffe quand même, dans le I)2), il est nécessaire :
- Que A soit non vide
- Que l'on ait l'axiome du choix...

[Nightmare]

Salut Ben :happy3:

Ok pour non vide, mais par contre l'axiome du choix n'intervient pas a priori ! Il ne faut pas montrer (qui nécessite bien l'axiome du choix) mais

:happy3:

[AL-kashi23]

Bonjour,

bonne petite colle sympatique =)

Tu pourrais aussi aller un tout petit peu à la découverte de l'infini, avec des trucs comme:

1) E infini <=> injection de N dans E
2) E infini <=> il existe f:E->E injective non surjective.

Enfin, dans l'état, elle me parait bien moi..

[Nightmare]

Salut !

Le problème est que la khôlle dure 1h, 1h30 grand max, et je pense que déjà ce sera un peu juste de tout traiter. J'ai juste mis en I] ce qui est nécessaire pour donner un "sens" aux deux théorèmes qui suivent.

:happy3:

[benekire2]

ah c'est la reprise ... donc les khôlles reviennent !!

Je m'y colle dès que j'aurais avancé celle de Zweig !!

[benekire2]

Je viens de regarder assez rapidement ... et je bloque sur la II-2 (évidemment) ; je vais méditer sur ton indice !

[benekire2]

pour la III-1 je conjecture que c'est 2^n ; pour la démo .. je sais pas si tu l'attend ( enfin je pense que si quand même ) mais je sais pas trop, je pense par récurrence ,

[Nightmare]

Et si tu essayais les exercices dans l'ordre ? :lol3:

[Nightmare]

pour la III-1 je conjecture que c'est 2^n ; pour la démo .. je sais pas si tu l'attend ( enfin je pense que si quand même ) mais je sais pas trop, je pense par récurrence ,

D'ou vient ta conjecture? Normalement, si tu as réussi à conjecturer le résultat, tu devrais pouvoir le prouver facilement, en tout cas si tu as essayé pour n=3,4,5 , à moins d'être très courageux, tu as normalement dû vite te fabriquer une façon de compter les parties d'un ensemble...

[Nightmare]

Et pour la II] 2), comme c'est conseillé, un dessin (pourvu qu'on fasse le bon) aide beaucoup à comprendre.

[benekire2]

D'ou vient ta conjecture? Normalement, si tu as réussi à conjecturer le résultat, tu devrais pouvoir le prouver facilement, en tout cas si tu as essayé pour n=3,4,5 , à moins d'être très courageux, tu as normalement dû vite te fabriquer une façon de compter les parties d'un ensemble...

Effectivement. J'ai sommer des conbinaisons, et en fait, c'est relativement facile à démontrer , j'écrirais bien entendu la démo quand j'aurais fini le pdf de Zweig ( pas gagné)

[Dinozzo13]

Salut !
Je me lance, mais je pense pas que ce soit bon ^^ :
I. lien avec la notion de cardinal
1°) il existe une injection de A dans B donc par conséquent
2°) S'il existe une injection de A dans B alors Or si alors il existe une surjection de B dans A.
3°) A et B sont finis et ont même cardinal donc et par conséquent f est bijective. or f est bijective si et seulement si f est injective et surjective donc f est également une injection et une surjection.

[Doraki]

Euh dans le 2) on suppose pas que les ensembles sont finis.
On te demande justement de montrer que |A|<=|B| est équivalent à |B|>=|A|.
T'as l'air de supposer que c'est la même chose, bah nan, c'est le principe de la question.

Dans le 3), ce que tu dis laisse sous-entendre que tu aurais-tu montré que toute application d'un ensemble fini dans lui-même est une bijection..

[Nightmare]

Salut !
Je me lance, mais je pense pas que ce soit bon ^^ :

Salut !

C'est la meilleur première chose à faire face à un exercice : Se lancer :lol3:

I. lien avec la notion de cardinal
1°) il existe une injection de A dans B donc par conséquent

Ok ! "Par conséquent" n'est pas top, disons que c'est une définition.

2°) S'il existe une injection de A dans B alors Or si alors il existe une surjection de B dans A.

Effectivement, , mais pourquoi ? C'est ce qu'on demande de montrer ..

.
3°) A et B sont finis et ont même cardinal donc et par conséquent f est bijective. or f est bijective si et seulement si f est injective et surjective donc f est également une injection et une surjection.

Qui est f ?

[Ben314]

Bon, j'en remet une couche, mais le fait que "toute surjection soit inversible à droite" est trés précisément une des formulations possible de l'axiome du choix

[benekire2]

Salut, comme nightmare leveut ... je prend les questions dans l'ordre. Je ne sais pas si mes "démos" sont valables :

Pour la I-1:

Considérons f:A -->B injective et que |A|>|B| c'est absurde car comme tout élément de A à une unique image et que chaque élément de B à au plus un antécédant par f on en déduit qu'il existe f(x)=f(x') tel que x est différent de x' ce qui contredit l'hypothèse d'injectivité.

Pour la II-2 :

Très bancale .
f:A-->B injective
"Découpons" B en B1 contenant ceux qui ont un antécédant par f et B2 ceux qui n'en ont pas.
Ainsi f:A-->B1 est bijective et on défini sa bijection réciproque f^-1 : B1 -->A bijective. De plus à tout élément de B2 on peut associer n'importe quel élément de A et on assure la surjectivité puisque tout élément de A à au moins un antécédant ( dans B1)

Pour la I-3:
L'énoncé se résume à f injective => f bijective et l'autre f surjective ==> f bijective

Pour la première par l'absurde supposons qu'un élément de B n'ai pas d'antécédant, par égalité des cardinaux on en déduit que f n'est pas injective.

Je traite l'autre cas tout à l'heure, je repart en cours .

[Doraki]

Bon, j'en remet une couche, mais le fait que "toute surjection soit inversible à droite" est trés précisément une des formulations possible de l'axiome du choix

Ceci dit, là il demande un truc un tout petit peu plus faible, à savoir si y'a une surjection de A dans B alors il y a une injection de B dans A (et non plus un inverse).
J'dois dire que j'ai pas trouvé de preuve de ça sans axiome du choix (normal), mais j'ai pas (encore) trouvé de preuve de l'axiome du choix en partant de ça.

[Nightmare]

Bon, j'en remet une couche, mais le fait que "toute surjection soit inversible à droite" est trés précisément une des formulations possible de l'axiome du choix

Gloups, tu as raison, cela dit le sens surjection => injection ne nécessite pas l'ADC donc je vais le garder.

[benekire2]

Il y a du débat théorique dans l'air !!

sinon ce que j'ai écrit est-il juste ?

PS: La "fin" de la preuve pour surjection ==> bijection :

S'il y a surjection, supposons qu'il n'y ait pas injection, c'est à dire que un élément de B ait plusieurs antécédants dans A. Ainsi nécésairement il y a plus d'éléments dans A que dans B ce qui n'est pas possible ie contradiction.