Répondre à la discussion
Affichage des résultats 1 à 21 sur 21

Ensemble dénombrable



  1. #1
    Bleyblue

    Ensemble dénombrable


    ------

    Bonjour,

    Je dois démontrer que l'ensemble A des fonctions injectives de vers n'est pas dénombrable.

    En calquant sur une autre démonstration (je ne suis pas encore capable de démontrer des propositions pareilles tout seul) :

    Si A était dénombrable il existerait une bijection
    Si je prends une fonction définie comme suit :

    Si

    g(z) = z

    Si

    g(z) est le plus petit naturel non nul différent de et de g(l) avec 0 < l < z

    Alors g est injective mais n'est pas dans l'image de F. Donc F n'est pas surjective, donc F n'est pas une bijection donc l'ensemble n'est pas dénombrable

    ca va ça ?

    merci

    -----
    Dernière modification par Bleyblue ; 13/07/2006 à 21h20.

  2. Publicité
  3. #2
    martini_bird

    Re : Ensemble dénombrable

    Salut,

    c'est quoi ?

    Cordialement.
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  4. #3
    Gwyddon

    Re : Ensemble dénombrable

    Fn m'a l'air d'être l'ensemble des fonctions injectives A.

    Donc la définition de g est erronée, puisque Fn(n) est une fonction, pas un entier...
    A quitté FuturaSciences. Merci de ne PAS me contacter par MP.

  5. #4
    Bleyblue

    Re : Ensemble dénombrable

    Excusez-moi j'ai fait une erreur dans mes notations.

    A est l'ensemble des fonctions injectives et la fonction est :



    cela marche comme ça ?

    merci

  6. A voir en vidéo sur Futura
  7. #5
    martini_bird

    Re : Ensemble dénombrable

    Salut,

    Alors g est injective mais n'est pas dans l'image de F.
    Il faudrait délayer un peu ça.

    En fait c'est une sorte d'argument "diagonal" (d'aileurs on pourrait s'y ramener très facilement).

    Cordialement.
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  8. #6
    rvz

    Re : Ensemble dénombrable

    Salut,

    Je dois être un peu fatigué (il est encore tôt ) mais il me semble que l'argument de Bleyblue est tout à fait juste et bien écrit, une fois qu'il a précisé ce qu'était F_n comme il l'a fait au post 4.
    Je comprends pas trop quels commentaires vous attendez en plus ?
    __
    rvz, qui l'année prochaine, devra faire des TDs, alors j'en profite pour essayer d'apprendre à rédiger clairement...

  9. Publicité
  10. #7
    martini_bird

    Re : Ensemble dénombrable

    Salut,

    tu te souviens quand tu étais en sup et qu'on te demandait pour démontrer qu'une fonction est injective de supposer qu'on a f(x)=f(y) et d'en déduire que x=y ?

    Il y a différents niveaux de rédaction : je ne suis pas certain (mais je me trompe peut-être) qu'un prof de sup accepte l'ommission de « détails »... Et puis c'est pas un mauvais exercice pour Bleyblue s'il veut vraiment se convaincre de sa preuve.

    Cordialement.
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  11. #8
    rvz

    Re : Ensemble dénombrable

    Oui, tu dois avoir raison. Encore que pour les fonctions injectives, ou c'est trivial, ou il faut vraiment le poser calmement. Je n'ai jamais vu de cas intermédiaire ...

    __
    rvz, qui se prépare à des longs exercices de rédaction...

  12. #9
    GrisBleu

    Re : Ensemble dénombrable

    Salut

    j essaie un truc, pas sur de la veracite

    1) R est indenombrable, l ensemble des nombres a developement decimale fini est inclus dans Q qui est denombrable, l ensemble des nombres a developpement non finis est donc indenombrables.
    c est la meme chose donc pour


    2) soit l ensemble F des fonction de N dans N injectives. A chaque f de F, on associe le nombre 0.f(0)f(1)f(2)....f(n).... Par exemple f(0)=3, f(1)=33, f(2)=333,... donne 0.33333333..... a chaque f de F, on peut associer ainsi un nombre de D, le 0 ne se repetant pas car f injectif
    montrons que c est injectif
    soit un nombre de D.
    -si il n y a pas de 0 dans les decimales, on prend


    etc...
    f est bien injective
    - si il y a au moins un zero, disons , on prend

    par definition, il existe q>p tq different de 0. si il n y a plus de 0 dans les decimales,
    different de f(0) puis chque f(n+1) est construit avec une decimale de plus que f(n)
    si il y a encore un 0 on recommence

    ainsi par recurence on construit un bon f

    donc F et D sont en bijection, F est donc indenombrable

    qu en pensez vous ?

  13. #10
    rvz

    Re : Ensemble dénombrable

    Salut

    L'idée est pas mauvaise, mais je ne comprends pas comment tu fais pour prouver que f est une bijection.
    x = 0,12345667....
    et y = 0,102345667... la même chose que x vont avoir la même image, non ? Y a sans doute moyen de corriger ça, mais j'ai pas trop le temps d'y réfléchir.

    __
    rvz

  14. #11
    GrisBleu

    Re : Ensemble dénombrable

    argh rvz m a tue

  15. #12
    Bleyblue

    Re : Ensemble dénombrable

    Citation Envoyé par martini_bird
    Il y a différents niveaux de rédaction : je ne suis pas certain (mais je me trompe peut-être)
    Non c'est bien vrai, j'ai oublié cette partie de la démonstration.
    J'essaie de démontrer proprement l'injectivité

    merci

  16. Publicité
  17. #13
    Bleyblue

    Re : Ensemble dénombrable

    Comme ça :

    Je dois montrer g injective.

    Supposons g(x) = g(y). Il faut x > 0 et y > 0 ou x <=0 et y <=0 car si x et y étaient de signes contraires il faudrait g(x) et g(y) aussi de signes contraires donc g(x) serait différent de g(y).

    a) Si
    alors g(x) = x et g(y) = y donc x = y

    b) Si

    g(x) est le plus petit naturel non nul, différent de , et différent de g(l1) avec 0 < l1 < x

    g(y) est le plus petit naturel non nul, différent de , et différent de g(l2) avec 0 < l2 < y

    Supposons x > y

    Alors g(x) est différent de g(l1) pour tout 0 < l1 < x et comme 0 < y < x eh bien g(x) est différent de g(y) ce qui est faux par hypothèse

    Supposons x < y
    (par le même raisonnement je montre que ce n'est pas possible)

    Donc x = y

    Donc g est une fonction injective car g(x) = g(y) ==> x = y et elle est différent de Fn pour tout naturel n car Fn(n) est différent de g(n)

    Maintenant, ça va ?

    merci

  18. #14
    Gwyddon

    Re : Ensemble dénombrable

    Je n'y vois strictement aucune faute, c'est nickel
    A quitté FuturaSciences. Merci de ne PAS me contacter par MP.

  19. #15
    Bleyblue

    Re : Ensemble dénombrable

    Bien bien, je vais mettre ça au net puis essayer une autre démonstration du même genre

    merci

  20. #16
    Bleyblue

    Re : Ensemble dénombrable

    Je dois montrer que l'ensemble E de toutes les suites réelles dont les termes sont 0 ou 1 n'est pas dénombrable

    En fait on se ramène à un ensemble de fonction parcequ'une suite réelle est une application et ici ça revient à montrer que l'ensemble des applications de N -> {0,1} n'est pas dénombrable

    Supposons que est une bijection et soit u une suite de E définie par :

    u(n) = 0 si Un(n) = 1
    u(n) = 1 si Un(n) = 0

    Alors la fonction u n'est pas dans l'image de U car pour toute suite Un appartenant à l'image de U on a u(n) diffèrent de Un(n) donc ça contredit la surjectivité etc.

    Ca passe ?

    merci

  21. #17
    doudache

    Re : Ensemble dénombrable

    Salut !

    Ca a l'air juste.

    Je ne sais pas si tu as remarqué, mais ton ensemble de suites est en bijection avec les parties de N. Plus généralement, essaie de montrer qu'il n'y a pas de surjection entre X et l'ensemble des parties de X.

  22. #18
    evariste_galois

    Re : Ensemble dénombrable

    Salut,

    J'y vais de ma petite idée, en espérant qu'elle soit juste:

    Montrons que l'ensemble A des fonctions injectives de N dans N est non dénombrable (On raisonne de même pour les fonctions injectives de Z dans Z).
    Je me donne une suite d'entiers naturels tous non nuls et je définis une fonction f:N->N comme suit:
    , pour i>0
    f est clairement injective, car les sont tous non nuls.
    Je considère alors l'ensemble B des fonctions définies comme ci-dessus, avec variant dans .
    Il s'ensuit que B est inclus dans A, de cardinal la puissance du continu.
    "Au train où vont les choses, les choses où vont les trains ne seront plus des gares."

  23. Publicité
  24. #19
    Bleyblue

    Re : Ensemble dénombrable

    Citation Envoyé par doudache
    Plus généralement, essaie de montrer qu'il n'y a pas de surjection entre X et l'ensemble des parties de X.
    J'ai déja vu cette démonstration dans le cas ou X = N, ça n'étais pas particulièrement simple comme démonstration, je ne sais pas si cela change quelque chose dans le cas d'un ensemble X quelconque (si je me souviens bien je pense que oui)

  25. #20
    Gwyddon

    Re : Ensemble dénombrable

    Et pourtant...


    Théorème : soit un ensemble quelconque. Il n'existe pas de surjection de sur


    Démonstration

    Supposons qu'il existe une telle surjection .

    Soit . Par surjection, il existe un certain tel que .

    Si l'on suppose que , par définition cela impose . Cela est absurde.

    Par conséquent, ; mais alors cela signifie que

    C'est encore absurde. Donc en définitive l'hypothèse de départ, à savoir l'existence de f, est absurde.

    Ainsi, il n'existe pas de surjection de vers
    Dernière modification par Gwyddon ; 16/07/2006 à 16h06.
    A quitté FuturaSciences. Merci de ne PAS me contacter par MP.

  26. #21
    Bleyblue

    Re : Ensemble dénombrable

    Ah tiens oui, c'est la même démo que celle que j'ai eu sauf que N est remplacé par un ensemble quelconque X

    merci

Discussions similaires

  1. Ensemble dénombrable.
    Par mystic_snake [Théo] dans le forum Mathématiques du supérieur
    Réponses: 18
    Dernier message: 18/10/2008, 11h51
  2. Espace connexe dénombrable
    Par martini_bird dans le forum Mathématiques du supérieur
    Réponses: 21
    Dernier message: 30/08/2007, 09h14
  3. Compact métrique infini dénombrable
    Par invité576543 dans le forum Mathématiques du supérieur
    Réponses: 14
    Dernier message: 13/08/2007, 08h52
  4. Q est dénombrable
    Par max2357 dans le forum Mathématiques du supérieur
    Réponses: 11
    Dernier message: 12/03/2006, 10h37
  5. cardinal du groupe des bijections d'un ensemble dénombrable
    Par metacarambar dans le forum Mathématiques du supérieur
    Réponses: 9
    Dernier message: 09/03/2006, 17h32