denombrement

[invite371ae0af]

Bonjour,

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

[invite179e6258]

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.

[invite1aa81b81]

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.

[invite03f2c9c5]

La décomposition binaire d’un entier n’est pas de longueur infinie…

[A voir en vidéo sur Futura]

[invite1aa81b81]

La décomposition binaire d’un entier n’est pas de longueur infinie…

En effet, au temps pour moi.

[Médiat]

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)

[invite03f2c9c5]

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…

[Amanuensis]

Utile de préciser que c'est la démo donnée dans le message juste avant (#6).