Dénombrabilité
Répondre à la discussion
Affichage des résultats 1 à 3 sur 3

Dénombrabilité



  1. #1
    FireScienceYxeOuR1en

    Dénombrabilité


    ------

    Bonjour,
    Durant un cours sur la dénombrabilité notre professeur nous a demandé de comparer N^N et {0;1}^N.
    En y réfléchissant j'ai bien aboutit à une preuve d'une bijection entre les deux ensembles et j'aimerais savoir s'il existe d'autres preuve de ceci.

    Voici ma démonstration : on s'appuie sur le théorème de Cantor-Bernstein en montrant l'existence de deux injections.
    De {0,1}^N vers N^N rien à faire l'identité convient

    De N^N vers {0;1}^N il y a plus de travail : on considère une suite V à valeur dans N et on réalise une sorte de codage en utilisant que des 0 et des 1. Le 0 va jouer le rôle d'espace, d'indicateur que l'on passe au terme suivant de la suite V, ensuite on associe 0 à 1, 1 à 1 1, 2 à 1 1 1 et de manière général on associe k à k+1 un à la suite.
    Par exemple pour vo=2, v1=1 on associe la suite uo=1,u1=1,u2=1, ainsi on a codé vo puis on passe au terme suivant en prenant u3=0, u4=1 et u5=1.
    On a donc bien une injection( malheureusement pas bijective car de nombreuses suites dans {0;1} posent problèmes: suites commençantes par 0, stationnaires, ayant deux 0 d'affilés etc.)
    On a ainsi une bijection entre les deux ensembles...

    J'ai quelques peu cherché sur internet mais n'ai pas trouvé de preuve de cela, pourriez vous m'en proposer ?

    -----

  2. #2
    Médiat

    Re : Dénombrabilité

    Citation Envoyé par FireScienceYxeOuR1en Voir le message
    En y réfléchissant j'ai bien aboutit à une preuve d'une bijection entre les deux ensembles et j'aimerais savoir s'il existe d'autres preuve de ceci.
    C'est la seule (avec ou sans Cantor Bernstein)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  3. #3
    GBZM

    Re : Dénombrabilité

    Bonsoir,

    Il s'agit plutôt ici d'indénombrabilité.

    On peut imaginer d'autres façons d'injecter dans .

    On remarque déjà que ce dernier ensemble est en bijection avec l'ensemble des parties de
    Ensuite, à toute suite d'entiers naturels, on peut associer la suite strictement croissante d'entiers naturels définie par et pour tout . L'image de cette suite, , est une partie infinie de et on a ainsi défini une bijection de sur l'ensemble des parties infinies de .
    Dernière modification par GBZM ; 30/06/2022 à 21h36.

Discussions similaires

  1. Non dénombrabilité
    Par SaraVan dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 17/09/2015, 05h41
  2. dénombrabilité
    Par lémathdabor dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 20/09/2011, 18h35
  3. Dénombrabilité de Q
    Par RoBeRTo-BeNDeR dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 28/11/2010, 10h20
  4. Dénombrabilité de A^n
    Par Seirios dans le forum Mathématiques du supérieur
    Réponses: 17
    Dernier message: 28/08/2007, 17h26
  5. Dénombrabilité
    Par invitead065b7f dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 24/09/2005, 09h31