Comment montrer que {0,1}^N est non dénombrable avec N l'ensemble des entiers naturels
je raisonne par l'absurde en supposant qu'il existe une bijection f:{0,1}^N--->N mais comment avoir la contradiction?
merci de votre aide
-----
28/01/2013, 12h03
#2
invite179e6258
Date d'inscription
janvier 1970
Messages
2 128
Re : denombrement
tu peux remplacer N par n'importe quel ensemble E et montrer que le cardinal de {0,1}^E est supérieur à celui de E, ça ne coûte pas plus cher.
28/01/2013, 12h03
#3
invite1aa81b81
Date d'inscription
janvier 1970
Messages
114
Re : denombrement
Où as-tu eu cet énoncé ?
Je pense au contraire que l'ensemble est {0,1}^N est dénombrable. Si je ne m'abuse, la bijection qui à un entier naturel associe sa décomposition binaire me paraît être la preuve de la dénombrabilité de ton ensemble.
ASan.
28/01/2013, 12h05
#4
invite03f2c9c5
Date d'inscription
janvier 1970
Messages
653
Re : denombrement
La décomposition binaire d’un entier n’est pas de longueur infinie…
Aujourd'hui
A voir en vidéo sur Futura
28/01/2013, 12h23
#5
invite1aa81b81
Date d'inscription
janvier 1970
Messages
114
Re : denombrement
Envoyé par DSCH
La décomposition binaire d’un entier n’est pas de longueur infinie…
En effet, au temps pour moi.
28/01/2013, 12h46
#6
Médiat
Date d'inscription
août 2006
Âge
74
Messages
20 461
Re : denombrement
Bonjour,
En supposant qu'il existe une telle bijection f, vous pouvez considérer l'image réciproque k par f de l'application g de IN dans {0, 1} définie pour tout n, par
g(n) = 1 - [f(n)](n) (f(n) est une application de IN dans {0, 1}) et calculez [f(k)](k)
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
28/01/2013, 12h48
#7
invite03f2c9c5
Date d'inscription
janvier 1970
Messages
653
Re : denombrement
Pour répondre au posteur initial, ce problème possède une démonstration classique fondée sur l’« argument diagonal ». Pas évident à trouver si l’on ne l’a jamais rencontré, et en même temps, cet argument devrait faire partie de la culture générale mathématique de tout étudiant…
28/01/2013, 13h19
#8
Amanuensis
Date d'inscription
septembre 2010
Messages
22 578
Re : denombrement
Utile de préciser que c'est la démo donnée dans le message juste avant (#6).
Pour toute question, il y a une réponse simple, évidente, et fausse.