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 ?
-----