{0,1}^N n'est pas dénombrable

[capitaine nuggets]

Bonjour, j'aurais besoin d'éclaircissement sur la preuve de la proposition suivante :

Proposition : n'est pas dénombrable.
Preuve : Supposons que est dénombrable.
Dans ce cas, il existe au moins une bijection .
Considérons alors la suite définie par .
u n'est pas dans l'image de puisqu'elle est différente de toutes les suites (f(n))_n, pourtant elle est à valeurs dans , n'est donc pas surjective, contradiction.
n'est donc pas dénombrable.

Je ne comprends plus la preuve à partir du moment où l'on considère la suite ...

Merci d'avance de m'éclairer :+++:

[jlb]

Salut,
f associe à un entier n une suite f(n): tu crées u terme par terme en considérant pour le terme d'indice n, le complément dans {0,1} du terme d'indice n de la suite f(n).

u est donc une suite de termes à valeur dans {0,1}, s'il existe n0 tel que f(n0)=u alors les termes d'indice n0 des suites u et f(n0) sont égaux mais par construction u(n0) est différent du terme n0 de la suite f(n0).

u n'a donc pas d'antécédent par f: f n'est par surjective, cela contredit donc l'hypothèse de départ ( {0,1}^N est dénombrable comme étant en bijection avec N)

Je ne sais pas si cela va t'aider, j'ai l'impression d'avoir vaguement paraphrasé ce que tu ne comprenais pas!! bon courage

[Rha]

Le principe c'est de construire une suite telle que , c'est-à-dire telle que .

Ici, si on choisit pour tout entier naturel , ça marche, parce que quel que soit l'entier naturel .

[mr_pyer]

Je pense qu'il faut tout d'abord bien comprendre que n'est pas un nombre mais une suite...

[capitaine nuggets]

@Ben314 : Ta notation est "lourde" comme tu dis, mais ça m'a fait comprendre ce qu'on manipulais :++:

Sinon j'ai eu beau lire et relire vos arguments, j'ai toujours un peu de mal à comprendre cette preuve :triste:

[Ben314]

Imagine ton tableau infini dans les deux sens (n est k) contenant des valeurs (en l’occurrence des 0 et des 1, mais ça pourrait être autre chose, il faut juste qu'il y ait au moins 2 valeurs possibles).

On va fabriquer une "nouvelle ligne" (par exemple au dessus du tableau vu qu'en dessous, comme on a une infinité de ligne, c'est un peu la merde... :marteau: )
- Dans la première case de cette nouvelle ligne, je met un élément différent de celui de la première case de la première ligne du tableau. Je suis certain que la ligne que je vais faire (quelque soit la suite) sera différente de la première ligne.
- Dans la deuxième case de cette nouvelle ligne, je met un élément différent de celui de la deuxième case de la deuxième ligne du tableau. Je suis certain que la ligne que je vais faire (quelque soit la suite) sera différente de la deuxième ligne.
- Dans la troisième case de cette nouvelle ligne, je met un élément différent de celui de la troisième case de la troisième ligne du tableau. Je suis certain que la ligne que je vais faire (quelque soit la suite) sera différente de la troisième ligne.
etc etc.

On est sûr avec ce procédé de fabriquer une nouvelle ligne qui n'est égale à aucune de celle du tableau d'origine (ce qui est contraire au fait que le tableau était censé contenir absolument toutes les suites possible de 0 et de 1)

[Ben314]

Pour écrire les choses proprement, en reprenant la notation pour tout entier k, on fabrique une nouvelle suite (avec un seul indice) en prenant pour une valeur différente de (donc si tu n'a le droit qu'à 0 et 1 tu n'a pas le choix).
Le fait, pour un donné que te garanti que la suite est différente de vu que leur terme d'indice ne sont pas les même.
Comme est quelconque, la suite ne peut être égale à aucun des ce qui contredit la surjectivité de la fonction f.