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

Existence d'une bijection des parties finies de N dans N



  1. #1
    Flohito

    Existence d'une bijection des parties finies de N dans N


    ------

    Hello
    Je n'arrive pas à montrer qu'il n'existe pas de surjection de l'ensemble des fonctions de N dans N pour montrer la non dénombrabilité de cet ensemble...quelqu'un peut il m'aider?
    Merci

    -----

  2. Publicité
  3. #2
    rvz

    Re : Existence d'une bijection des parties finies de N dans N

    Je ne comprends pas : Ta question et ton titre sont différents !
    Cela dit, pour ton titre, il me semble que je sais le faire: Considère les nombres premiers p_n comme marqueurs.
    Pour une partie A={a_1,...,a_n}, d'abord classer les éléments par ordre décroissant, afin d'avoir une définition précise, puis poser f(A) = produit des p_i^a_i.
    On arrive dans une partie dénombrable de N, qu'il est facile de mettre en bijection avec N.
    Pour ta question, il suffit de démontrer que [0,1[ s'injecte dans l'ensemble des fonctions de N dans N. Pour cela, tu peux par exemple regarder l'application qui à un nombre réél r = 0,a_1...a_n... associe la fonction f(r):N->N telle que f(r)(n)=a_n. Mais là, j'ai sans doute modifié ta question. La bonne question, à laquelle pour le coup, je n'ai pas de réponse, c'est : Est ce que l'ensemble des fonctions _bijectives_ de N dans N est dénombrable ? Je ne pense pas, mais je ne vois pas de preuve. Des idées ?

    __rvz

  4. #3
    invite986312212
    Invité

    Re : Existence d'une bijection des parties finies de N dans N

    Citation Envoyé par rvz
    La bonne question, à laquelle pour le coup, je n'ai pas de réponse, c'est : Est ce que l'ensemble des fonctions _bijectives_ de N dans N est dénombrable ? Je ne pense pas, mais je ne vois pas de preuve. Des idées ?

    __rvz
    pourquoi ne pas utiliser le procédé diagonal de Cantor?
    si les bijections de N dans N étaient dénombrables, on pourrait les dénombrer : f1,f2,...
    construisons maintenant une bijection f, telle que pour tout entier i, f(i) != fi(i) <je note != : différent de>
    on prend f(1) = le plus petit entier différent de f1(1), puis par récurrence, f(i) = le plus petit entier différent de fi(i) et des f(1),...,f(i-1)
    f est injective par construction. Il reste à montrer qu'elle est surjective. On le montre par récurrence. Soit k le plus petit entier tel que fk(1)!=1. Alors f(k)=1. Supposons que les entiers 1,..,(n-1) ont un antécédent par f. Soit k le plus petit entier tel que fk(n)!=n, etc.

  5. #4
    kaya31

    Re : Existence d'une bijection des parties finies de N dans N

    Citation Envoyé par ambrosio
    pourquoi ne pas utiliser le procédé diagonal de Cantor?
    si les bijections de N dans N étaient dénombrables, on pourrait les dénombrer : f1,f2,...
    construisons maintenant une bijection f, telle que pour tout entier i, f(i) != fi(i) <je note != : différent de>
    on prend f(1) = le plus petit entier différent de f1(1), puis par récurrence, f(i) = le plus petit entier différent de fi(i) et des f(1),...,f(i-1)
    f est injective par construction. Il reste à montrer qu'elle est surjective. On le montre par récurrence. Soit k le plus petit entier tel que fk(1)!=1. Alors f(k)=1. Supposons que les entiers 1,..,(n-1) ont un antécédent par f. Soit k le plus petit entier tel que fk(n)!=n, etc.
    Salut,

    Il me semble qu'il y a un petit problème quant à ta démonstration de la surjectivité. Pour que f(k)=1 il faut non pas que fk(1)!=1 mais plutôt que fk(k)!=1...
    Ca rajoute une subtilité pour la construction de f.
    Pour reprendre là où ca coince : l'existence de k le plus petit entier tel que fk(k)!=1 n'est pas certaine.
    Mais s'il n'existe pas, tu peux construire une nouvelle bijection g en considérant par exemple g(2)=f1(3), g(3)=f1(2) et g=f1 partout ailleurs.
    Bref, soit la récurrence est vraie et tu peux construire une nouvelle bijection, soit elle est fausse et tu peux tout de même construire une nouvelle bijection

  6. A voir en vidéo sur Futura

Discussions similaires

  1. bijection de IR^n dans IR
    Par metacarambar dans le forum Mathématiques du supérieur
    Réponses: 25
    Dernier message: 07/03/2010, 05h06
  2. Parties polluantes d'une voiture
    Par gauthierM dans le forum TPE / TIPE et autres travaux
    Réponses: 0
    Dernier message: 26/10/2007, 15h38
  3. quand doit on effectuer la recherche des limite finies et des limites infinies
    Par indilunique dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 22/10/2007, 10h21
  4. Existence d'une onde réfléchie
    Par explicit01 dans le forum Physique
    Réponses: 1
    Dernier message: 23/09/2007, 11h22
  5. Réponses: 8
    Dernier message: 20/08/2007, 21h39