Ensembles dénombrables
5 participants
Page 1 sur 1
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
Pouvez-vous m'aidez svp
Merci
minidiane- Membre
- Nombre de messages : 128
Age : 37
Localisation : Mulhouse
Profession / Etudes : Etudiante
Points : 6225
Date d'inscription : 13/06/2007
Re: Ensembles dénombrables
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.
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.
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8286
Date d'inscription : 16/01/2006
Re: Ensembles dénombrables
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 contre pour l'autre démonstration je ne vois pas du tout comment faire.
minidiane- Membre
- Nombre de messages : 128
Age : 37
Localisation : Mulhouse
Profession / Etudes : Etudiante
Points : 6225
Date d'inscription : 13/06/2007
Re: Ensembles dénombrables
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...
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8286
Date d'inscription : 16/01/2006
Re: Ensembles dénombrables
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.
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.
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8286
Date d'inscription : 16/01/2006
Re: Ensembles dénombrables
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 contre je n'ai pas compris le (0,0,1) ça fait un triplé non? c'est pas biniare si?
minidiane- Membre
- Nombre de messages : 128
Age : 37
Localisation : Mulhouse
Profession / Etudes : Etudiante
Points : 6225
Date d'inscription : 13/06/2007
Re: Ensembles dénombrables
quand je dis binaire c'est pcq c'est des 1 ou des 0 comme valeurs !
00110100110100110111101000101110100010101110101
est bien une suite binaire !
00110100110100110111101000101110100010101110101
est bien une suite binaire !
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8286
Date d'inscription : 16/01/2006
Re: Ensembles dénombrables
Ah oui ok
et donc je peux utiliser le procèdé d'avant
et donc je peux utiliser le procèdé d'avant
minidiane- Membre
- Nombre de messages : 128
Age : 37
Localisation : Mulhouse
Profession / Etudes : Etudiante
Points : 6225
Date d'inscription : 13/06/2007
Re: Ensembles dénombrables
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é...
Mais ça fournit la même propriété...
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8286
Date d'inscription : 16/01/2006
Re: Ensembles dénombrables
A oui ok je pense que j'ai compris
chaque décimal est soit 0 soit 1 c'est bien ça?
chaque décimal est soit 0 soit 1 c'est bien ça?
minidiane- Membre
- Nombre de messages : 128
Age : 37
Localisation : Mulhouse
Profession / Etudes : Etudiante
Points : 6225
Date d'inscription : 13/06/2007
Re: Ensembles dénombrables
N'oublions pas que cette démo remarquable vient d'un informaticien (et oui, le duche est étudiant en info)! Balèze hein!
Sangoku- Membre
- Nombre de messages : 158
Age : 40
Profession / Etudes : Etudiant en maths
Points : 6469
Date d'inscription : 05/09/2006
Re: Ensembles dénombrables
C'est clair je comprend mieux d'où viens la suite binaire lol
minidiane- Membre
- Nombre de messages : 128
Age : 37
Localisation : Mulhouse
Profession / Etudes : Etudiante
Points : 6225
Date d'inscription : 13/06/2007
Re: Ensembles dénombrables
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 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.
minidiane- Membre
- Nombre de messages : 128
Age : 37
Localisation : Mulhouse
Profession / Etudes : Etudiante
Points : 6225
Date d'inscription : 13/06/2007
Re: Ensembles dénombrables
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...
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...
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8286
Date d'inscription : 16/01/2006
Re: Ensembles dénombrables
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) ...
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) ...
minidiane- Membre
- Nombre de messages : 128
Age : 37
Localisation : Mulhouse
Profession / Etudes : Etudiante
Points : 6225
Date d'inscription : 13/06/2007
Re: Ensembles dénombrables
Est-ce bien ça?
minidiane- Membre
- Nombre de messages : 128
Age : 37
Localisation : Mulhouse
Profession / Etudes : Etudiante
Points : 6225
Date d'inscription : 13/06/2007
Re: Ensembles dénombrables
Personne ne peut m'aider?
minidiane- Membre
- Nombre de messages : 128
Age : 37
Localisation : Mulhouse
Profession / Etudes : Etudiante
Points : 6225
Date d'inscription : 13/06/2007
Re: Ensembles dénombrables
Ca fait un moment que le_duche n'est pas venu !minidiane a écrit:Personne ne peut m'aider?
Julien- Administrateur
- Nombre de messages : 12291
Age : 37
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 22520
Date d'inscription : 10/03/2005
Re: Ensembles dénombrables
oui je comprend pas,il en a eu marre de moi je pense
minidiane- Membre
- Nombre de messages : 128
Age : 37
Localisation : Mulhouse
Profession / Etudes : Etudiante
Points : 6225
Date d'inscription : 13/06/2007
Re: Ensembles dénombrables
Je sais qu'en ce moment il a pas mal de boulot...minidiane a écrit:oui je comprend pas,il en a eu marre de moi je pense
Julien- Administrateur
- Nombre de messages : 12291
Age : 37
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 22520
Date d'inscription : 10/03/2005
Re: Ensembles dénombrables
Non non, c'est juste qu'il a pas encore l'accès internet après son déménagement.
Sangoku- Membre
- Nombre de messages : 158
Age : 40
Profession / Etudes : Etudiant en maths
Points : 6469
Date d'inscription : 05/09/2006
Re: Ensembles dénombrables
Ah d'accord ! Et c'est prévu pour quand, tu le sais ?Sangoku a écrit:Non non, c'est juste qu'il a pas encore l'accès internet après son déménagement.
Julien- Administrateur
- Nombre de messages : 12291
Age : 37
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 22520
Date d'inscription : 10/03/2005
Re: Ensembles dénombrables
Ah ok j'ai eu peur lol
J'espère qu'il pourra bientôt revenir pour m'aider
J'espère qu'il pourra bientôt revenir pour m'aider
minidiane- Membre
- Nombre de messages : 128
Age : 37
Localisation : Mulhouse
Profession / Etudes : Etudiante
Points : 6225
Date d'inscription : 13/06/2007
Re: Ensembles dénombrables
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é...
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é...
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8286
Date d'inscription : 16/01/2006
Re: Ensembles dénombrables
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.
ah oui! il reste à montrer que {0,1}^N :={(x_i)i appartenant à N: x_i appartenant à {0,1}} n'est pas dénombrable.
minidiane- Membre
- Nombre de messages : 128
Age : 37
Localisation : Mulhouse
Profession / Etudes : Etudiante
Points : 6225
Date d'inscription : 13/06/2007
Re: Ensembles dénombrables
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.
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.
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8286
Date d'inscription : 16/01/2006
Re: Ensembles dénombrables
oui mais j'ai du mal a le faire et a bien comprendre
minidiane- Membre
- Nombre de messages : 128
Age : 37
Localisation : Mulhouse
Profession / Etudes : Etudiante
Points : 6225
Date d'inscription : 13/06/2007
Re: Ensembles dénombrables
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.
ephemere- Membre
- Nombre de messages : 633
Age : 45
Localisation : Belgique
Profession / Etudes : Étudiant de 3ème cycle
Points : 6954
Date d'inscription : 05/05/2005
Re: Ensembles dénombrables
ok merci pour ce complément
minidiane- Membre
- Nombre de messages : 128
Age : 37
Localisation : Mulhouse
Profession / Etudes : Etudiante
Points : 6225
Date d'inscription : 13/06/2007
Page 1 sur 1
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum
|
|
Jeu 2 Juil 2015 - 15:16 par louaraychi
» Devoir maison sur équilibre et réaction chimique
Dim 1 Fév 2015 - 17:19 par sararose
» Ma présentation
Sam 25 Oct 2014 - 23:29 par Rith
» projet scientique sur la LUMIERE
Ven 26 Sep 2014 - 20:33 par benjamin-010
» La trajectoire de la Terre
Mar 5 Aoû 2014 - 22:19 par Alban
» Equilibrer une réaction redox
Dim 8 Juin 2014 - 21:18 par Courtney ♥
» les effets sur les lignes de transport de l’électricité
Ven 30 Mai 2014 - 17:14 par leila14
» lignes de transport de l'électricité
Ven 30 Mai 2014 - 17:07 par leila14
» Gravitation
Ven 16 Mai 2014 - 20:16 par fatimaa
» Maquette suspension de moto 2D
Jeu 17 Avr 2014 - 17:20 par Sti2d