Bonjour, pourriez-vous m'éclaircir au sujet du raisonnement qui suit:

On doit montrer que l'ensemble des fonctions de IN dans IN n'est pas dénombrable.
On admet que P(IN) n'est pas dénombrable.
Pour cela on pose l'application suivante :
φ : P(IN) -> f(IN , {0,1})
A |----> 1I_A (fonction indicatrice)

On prend A et A' dans P(IN) et on montre que A = A', donc c'est injectif. Ça ok.

Pour la surjectivité, on prend f dans f(IN , {0,1}).
On pose I = {i ∈ I , f(i) = 1} inclus dans IN (pourquoi cette inclusion ?)
Alors φ(I) = f.

On conclut que comme P(IN) n'est pas dénombrable, alors f(IN , {0,1}) non plus.

On a trouvé une injection d'un ensemble non dénombrable vers f(IN , {0,1}), donc pourquoi cherche-t-on a prouver la surjectivité ?
Merci

Effectivement, une fois que t'as l'injectivité ça suffit, je ne sais pas pourquoi ils s'embêtent à montrer la surjectivité.
Peut-être que dans le cours/bouquin d'où vient la preuve, ils n'ont énoncé la propriété sur les cardinaux que pour les bijections et du coup ils se sentent obligé de justifier ça comme ça.

Ça permet de préciser que les deux ensembles ont le même cardinal, mais oui en effet pour montrer la non denombrabilité, l'injectivité suffit.

Merci à vous pour votre aide

J'aurais d'autres questions à poser qui sont sur ce site: http://www.bibmath.net/ressources/index.php?action=affiche&quoi=bde/analyse/integration/denombrables&type=fexo

Exo 2 : Je ne comprends pas la phrase : "Si l'ensemble des applications [...] sous la forme F(IN) = {f_n ; n € IN}" En fait j'ai pas vraiment compris la démarche et je perds entre f et les f_n .

Exo 3 : Pourriez-vous me ré-expliquer l'argument de l'injectivité de A_p ?
De plus, je suppose que la surjectivité est également à mettre entre parenthèses ici.

Merci

Le 11 septembre 2018 à 22:50:37 valir00 a écrit :
Exo 2 : Je ne comprends pas la phrase : "Si l'ensemble des applications [...] sous la forme F(IN) = {f_n ; n € IN}" En fait j'ai pas vraiment compris la démarche et je perds entre f et les f_n .

Ben l'idée, c'est que si l'ensemble des fonctions de N dans N (ce qu'ils notent F(N)) est dénombrable, alors il existe une suite (f_n) tel que tous les éléments de F(N) soient représentant par un certain f_n. Et du coup, tu peux utiliser la construction donnée dans l'énoncé pour construire une fonction f qui est différente de toutes le f_n, ce qui est absurde.

Exo 3 : Pourriez-vous me ré-expliquer l'argument de l'injectivité de A_p ?
De plus, je suppose que la surjectivité est également à mettre entre parenthèses ici.

Les suites dans A_p sont nulles à partir du rang p, donc si les a_0, a_1, ..., a_(p-1) sont égaux, les deux suites sont égales, puisque par hypothèse elles coïncident sur [0;p-1] et qu'elles sont nulles à partir de p.

Le 11 septembre 2018 à 23:50:50 Dagnyr a écrit :

Le 11 septembre 2018 à 22:50:37 valir00 a écrit :
Exo 2 : Je ne comprends pas la phrase : "Si l'ensemble des applications [...] sous la forme F(IN) = {f_n ; n € IN}" En fait j'ai pas vraiment compris la démarche et je perds entre f et les f_n .

Ben l'idée, c'est que si l'ensemble des fonctions de N dans N (ce qu'ils notent F(N)) est dénombrable, alors il existe une suite (f_n) tel que tous les éléments de F(N) soient représentant par un certain f_n. Et du coup, tu peux utiliser la construction donnée dans l'énoncé pour construire une fonction f qui est différente de toutes le f_n, ce qui est absurde.

Exo 3 : Pourriez-vous me ré-expliquer l'argument de l'injectivité de A_p ?
De plus, je suppose que la surjectivité est également à mettre entre parenthèses ici.

Les suites dans A_p sont nulles à partir du rang p, donc si les a_0, a_1, ..., a_(p-1) sont égaux, les deux suites sont égales, puisque par hypothèse elles coïncident sur [0;p-1] et qu'elles sont nulles à partir de p.

Merci pour ta réponse.
Je ne comprends juste pas d'où on sort l'hypothèse que les suites coïncident sur [0,p-1].

Tu veux montrer que phi est injective. Donc tu prends deux suites de A_p qui ont la même image par phi, et tu veux montrer qu'elles sont égales. Or par définition de phi, deux suites qui ont la même image par phi coïncident sur les p premiers termes.

Le 12 septembre 2018 à 10:04:18 Prauron a écrit :
Tu veux montrer que phi est injective. Donc tu prends deux suites de A_p qui ont la même image par phi, et tu veux montrer qu'elles sont égales. Or par définition de phi, deux suites qui ont la même image par phi coïncident sur les p premiers termes.

Ok c'est bon j'ai compris, merci à vous