Ensembles dénombrables

par minidiane le Dim 30 Sep - 9:09

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

par **le_duche** le Dim 30 Sep - 13:57

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.

par minidiane le Dim 30 Sep - 14:37

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.

par **le_duche** le Dim 30 Sep - 15:54

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

par **le_duche** le Dim 30 Sep - 16:02

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.

par minidiane le Dim 30 Sep - 20:00

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?

par **le_duche** le Dim 30 Sep - 20:20

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

00110100110100110111101000101110100010101110101

est bien une suite binaire !

par minidiane le Dim 30 Sep - 21:11

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

par **le_duche** le Dim 30 Sep - 21:58

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

par minidiane le Lun 1 Oct - 20:34

A oui ok je pense que j'ai compris

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

par Sangoku le Lun 1 Oct - 22:00

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

par minidiane le Lun 1 Oct - 22:26

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

par minidiane le Mar 2 Oct - 18:50

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.

par **le_duche** le Mer 3 Oct - 13:15

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