Ensembles dénombrables

Bonjour, je n'arrive pas à démontrer que l'intervalle des nombres réels [0,1] n'est pas dénombrable et à montrer que {0,1}^N :={(x_i)i appartenant à N: x_i appartenant à {0,1}} n'est pas dénombrable. Indication donnée:(Montrer que si D inclu dans {0,1}^N est dénombrable alors on peut construire une nouvelle suite (x^i)_(i appartenant à N) appartient à {0,1}^N en dehors de D!)
Pouvez-vous m'aidez svp
Merci

Et bien pour montrer que [0,1] n'est pas dénombrable c'est assez simple: il suffit de le montrer par l'absurde.
L'idée de la démo est la suivante: on suppose que l'ensemble des réels dans [0,1] est dénombrable; ce qui signifie que l'on peut en dresser une liste infinie. Il est donc possible d'appeler tous ces réels r1,r2,r3,r4,r5,... On va montrer qu'à partir de cette liste on peut créer un nouveau nombre réel qui n'est pas dans la liste. Cela prouvera alors qu'on ne peut tous les énumérer en une liste et que ce n'est donc pas dénombrable.

Regardons nos nombres r1,r2,r3,... sous forme décimale:
r1 = 0, d11 d12 d13 d14 d15 d16 d17 ...
r2 = 0, d21 d22 d23 d23 d25 d26 d27 ...
r3 = 0, d31 d32 d33 d34 d35 d36 d37 ...
r4 = 0, d41 d42 d43 d44 d45 d46 d47 ...
r5 = 0, d51 d52 d53 d54 d55 d56 d57 ...
.
.
.
où dij est le j-ème chiffre décimale de ri.
Je décide alors de poser les chiffres
k1 non égal à d11
k2 non égal à d22
k3 non égal à d33
k4 non égal à d44
k5 non égal à d55
.
.
.
Et j'affirme alors que le nombre
q = 0, k1 k2 k3 k4 k5 ...
n'est pas l'un des ri de la liste, car pour tout i, sa i-ème décimale diffère de celle de ri

On a ainsi créé un nombre qui n'est pas dans la liste, l'ensemble [0,1] n'est donc pas dénombrable.

ok merci le_duche je crois que j'ai compris
par contre pour l'autre démonstration je ne vois pas du tout comment faire.

Je vais regarder ça... Ca m'a lair un peu plus compliqué. Du moins je sens que je vais devoir rédiger quelques trucs avant de te répondre...

Ok je vois ce que tu veux dire, fais très attention, car l'ensemble tel que tu le décris ici (c'est d'ailleurs ce que j'avais compris au début) n'est pas celui auquel tu penses !
En effet, tu dis
{ (x_i) i dans IN et x_i dans {0,1} }
Moi je l'ai compris comme l'ensemble des n-uples binaires, c'est à dire
(0) (1) (0,0) (0,1) (1,0) (1,1) (0,0,1) ...
ce qui est dénombrable...

Donc on est bien d'accord,
{0,1}^IN est l'ensemble des suites binaires
??

Si c'est le cas, tu peux utiliser exactement la même démo que la mienne ci dessus.

A ok je n'avais pas compris cela mais je pense que c'est ça en effet
par contre je n'ai pas compris le (0,0,1) ça fait un triplé non? c'est pas biniare si?

quand je dis binaire c'est pcq c'est des 1 ou des 0 comme valeurs !

00110100110100110111101000101110100010101110101

est bien une suite binaire !

Ah oui ok
et donc je peux utiliser le procèdé d'avant

oui c'est la même chose, mais cette fois ci, quand tu prends un ki différent de dii ben c'est simplement 1 si dii = 0 et 0 si dii = 1
Mais ça fournit la même propriété...

A oui ok je pense que j'ai compris

chaque décimal est soit 0 soit 1 c'est bien ça?

N'oublions pas que cette démo remarquable vient d'un informaticien (et oui, le duche est étudiant en info)! Balèze hein!

C'est clair je comprend mieux d'où viens la suite binaire lol

En reprenant ce que tu avais fait pour [0,1] j'ai donc

par l'absurde.
on suppose que l'ensemble des réels dans {0,1}^N est dénombrable; ce qui signifie que l'on peut en dresser une liste infinie. Il est donc possible d'appeler tous les éléments de {0,1]^N par r1,r2,r3,r4,r5,... On va montrer qu'à partir de cette liste on peut créer un nouveau nombre réel qui n'est pas dans la liste. Cela prouvera alors qu'on ne peut tous les énumérer en une liste et que ce n'est donc pas dénombrable.

Regardons nos nombres r1,r2,r3,... sous forme décimale:
r1 = 0, d11 d12 d13 d14 d15 d16 d17 ...
r2 = 0, d21 d22 d23 d23 d25 d26 d27 ...
r3 = 0, d31 d32 d33 d34 d35 d36 d37 ...
r4 = 0, d41 d42 d43 d44 d45 d46 d47 ...
r5 = 0, d51 d52 d53 d54 d55 d56 d57 ...
.
.
.
où dij est le j-ème chiffre décimale de ri.
Je décide alors de poser les chiffres
k1 non égal à d11
k2 non égal à d22
k3 non égal à d33
k4 non égal à d44
k5 non égal à d55
.
.
.
Et j'affirme alors que le nombre
q = 0, k1 k2 k3 k4 k5 ...
En prenant kii=1 si dii = 0 et kii=0 si dii =1
n'est pas l'un des ri de la liste, car pour tout i, sa i-ème décimale diffère de celle de ri

On a ainsi créé un nombre qui n'est pas dans la liste, l'ensemble {0,1}^N n'est donc pas dénombrable.

non non ! {0,1}^IN ce ne sont plus des réels !


on suppose que l'ensemble des suites binaires dans {0,1}^N est dénombrable; ce qui signifie que l'on peut en dresser une liste infinie. Il est donc possible d'appeler tous les éléments de {0,1]^N par s1,s2,s3,s4,s5,... On va montrer qu'à partir de cette liste on peut créer une nouvelle suite qui n'est pas dans la liste. Cela prouvera alors qu'on ne peut tous les énumérer en une liste et que ce n'est donc pas dénombrable.

et ainsi de suite tu adaptes...
il n'y a plus de virgules par exemple...

a ok par contre pourquoi il n'y a plus de virgules?
on a bien si j'ai bien compris s1=(0) s2=(1) s3=(0,0) s4=(0,1) s5=(1,0) s6=(1,1) s7=(0,0,1) ...

Est-ce bien ça?

Personne ne peut m'aider?

minidiane a écrit:Personne ne peut m'aider?

Ca fait un moment que le_duche n'est pas venu !

oui je comprend pas,il en a eu marre de moi je pense

minidiane a écrit:oui je comprend pas,il en a eu marre de moi je pense

Je sais qu'en ce moment il a pas mal de boulot...

Non non, c'est juste qu'il a pas encore l'accès internet après son déménagement.

Sangoku a écrit:Non non, c'est juste qu'il a pas encore l'accès internet après son déménagement.

Ah d'accord ! Et c'est prévu pour quand, tu le sais ?

Ah ok j'ai eu peur lol
J'espère qu'il pourra bientôt revenir pour m'aider

Tadaaaam je suis lààààà !

Faut que je me remette dans le bain, le mieux est que tu me dises ou t'en es si c'est encore d'actualité...

oui je veux bien que tu m'aides, je ne sais plus trop non plus lol

ah oui! il reste à montrer que {0,1}^N :={(x_i)i appartenant à N: x_i appartenant à {0,1}} n'est pas dénombrable.

Et bien je t'ai dit pourtant...
C'est la même démo que pour les réels, mais la virgule disparait et les chiffres utilisés sont que des 0 et des 1.

oui mais j'ai du mal a le faire et a bien comprendre

le_duche a écrit:Et bien pour montrer que [0,1] n'est pas dénombrable c'est assez simple: il suffit de le montrer par l'absurde.
L'idée de la démo est la suivante: on suppose que l'ensemble des réels dans [0,1] est dénombrable; ce qui signifie que l'on peut en dresser une liste infinie. Il est donc possible d'appeler tous ces réels r1,r2,r3,r4,r5,... On va montrer qu'à partir de cette liste on peut créer un nouveau nombre réel qui n'est pas dans la liste. Cela prouvera alors qu'on ne peut tous les énumérer en une liste et que ce n'est donc pas dénombrable.

Regardons nos nombres r1,r2,r3,... sous forme décimale:
r1 = 0, d11 d12 d13 d14 d15 d16 d17 ...
r2 = 0, d21 d22 d23 d23 d25 d26 d27 ...
r3 = 0, d31 d32 d33 d34 d35 d36 d37 ...
r4 = 0, d41 d42 d43 d44 d45 d46 d47 ...
r5 = 0, d51 d52 d53 d54 d55 d56 d57 ...
.
.
.
où dij est le j-ème chiffre décimale de ri.
Je décide alors de poser les chiffres
k1 non égal à d11
k2 non égal à d22
k3 non égal à d33
k4 non égal à d44
k5 non égal à d55
.
.
.
Et j'affirme alors que le nombre
q = 0, k1 k2 k3 k4 k5 ...
n'est pas l'un des ri de la liste, car pour tout i, sa i-ème décimale diffère de celle de ri

On a ainsi créé un nombre qui n'est pas dans la liste, l'ensemble [0,1] n'est donc pas dénombrable.

Attention, il y a un petit rafinement à rajouter à cette démonstration pour la rendre tout à fait correcte. Il se pourrait, à priori que le nombre q = 0, k1 k2 k3 k4 k5 ... soit en fait dans la liste même si son écriture décimale est différente de celle de chaque nombre de la liste. En effet, certains nombres ont deux représentations décimales.

Par exemple : 0,099999...= 0,100000...

On peut résoudre ce problème facilement, mais cela alourdit un rien la preuve, sans en changer la philosophie.

ok merci pour ce complément