Mathématiques - Ensembles dénombrables

Ensembles dénombrables
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: minidiane

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

Posted by: Joker62

On suppose qu'il est dénombrable,
On le découpe en trois
Alors il existe forcément un élement de la suite qui n'appartient pas à un des 3 intervalles créer.
On recommence avec l'intervalle dans lequel on a choisi l'élément
On le découpe en trois... etc... etc...

On va arriver à une contradiction

Posted by: minidiane

Il faut faire cela pour les deux démonstrations?

Posted by: Joker62

Non ça c'est pour montrer que [0;1] n'est pas dénombrable.

Posted by: Joker62

Pour la deux, ça sent la décomposition diadique de Cantor.
Va voir du côté de l'argument de la Diagonale de Cantor

Posted by: minidiane

oula je ne connais pas du tout je vais voir si je trouve quelque chose sur google ;)

Posted by: legeniedesalpages

Bonjour, oui l'indication indique clairement qu'il faut utiliser la diagonale de Cantor, sinon on peut montrer que $\{0,1\}^{\mathbb{N}}$ est en bijection avec $\mathcal{P}(\mathbb{N})$ , et conclure à l'aide du théorème de Cantor.

Posted by: minidiane

ok est-ce que quelqu'un peut me donner la définition de la diagonale de Cantor et son théorème? car je ne comprend pas trop ce que j'ai trouvé sur le net
merci

Posted by: fahr451

bonjour

voila le procédé diagonal de cantor

on suppose qu'on peut dénombre les suites dont les termes valent 0 ou 1

on en fait donc une numération soit

(x^(n) )ndans N une telle numérotation on a donc toutes les telles suites

x^(0) , x^(1) etc ... sont donc des suites

on écrit

x^(0) = (x^(0) 0 ,x^(0) 1,..)
x^(0) 0 est le premier terme de la suite x^(0)

on construit une suite x telle que x0 soit différent de x^(0) 0

si x^(0) 0 = 1 on prend 0 et inversement
la suite x est donc différent de la suite x^(0)
on impose aussi que

x1 différent de x^(1) 1

la suite x est différente de la suite x^(1)

d'une façon générale on impose

pour tout n
xn différent de x^(n) n

donc la suite x est différente de toutes les suites x^(n)

et pourtant est bien une suite de termes 0 ou1

on avait supposé qu'on les avait toutes avec les x^(n)
c'est absurde

Posted by: minidiane

ok merci fahr je crois que j'ai compris le procédé, par contre pour l'appliquer c'est encore autre chose.

Posted by: Joker62

Il suffit de dire : par le procédé de la diagonale de Cantor, on extrait un élément etc...

Posted by: juve1897

Bonjour,

desolée de m'incruster dans ce topic, mais je suis aussi sur un exercice sur les ensembles dénombrables.

En fait la definition nous est énoncée et on nous demande de verifer que qq ensembles sont denombrables.

MAis je ne vois vraiment pas comment proceder à la demonstration.

Est ce que qqun pourrait m'eclairer un peu ?

Merci bcp

Posted by: Joker62

Un ensemble E est dénombrable si on peut le mettre en bijection avec N

Le but est donc de construire une bijection.
Montre sur quoi tu bloques.

Posted by: juve1897

Citation:

Posté par Joker62

Un ensemble E est dénombrable si on peut le mettre en bijection avec N

Le but est donc de construire une bijection.
Montre sur quoi tu bloques.

Ben c'est sur la definition que je bloque, je comprends qu'il y'a une histoire de bijection mais le reste ???

en fait je dois montrer que des ensembles tel que Z, les entiers impairs .

En par la suite je dois verifier que
1) l'union de 2 ensemble dénombrables est dénombrable (en supp que les 2 sont disjoint)

2) un sous ensemble infini d'un ensemble infini denombrable est infini denombrable

Mais j'aimerai simplement que l'on m'explique comment faire dans un cas general.

Merci Joker ;)

Posted by: Joker62

Pour montrer que Z est dénombrable :

On cherche une application g de Z dans N tel que g soit bijective

On pose

g(z) = 2z si z € N
g(z) = -(2z+1) si z € Z\N

g(0) = 0
g(-1) = 1
g(1) = 2
g(-2) = 3
g(2) = 4
g(-3) = 5

...
Tu vérifies qu'elle est bijective et voilà Z est dénombrable
On peut compter les entiers relatifs.

Posted by: juve1897

Citation:

Posté par Joker62

Pour montrer que Z est dénombrable :

On cherche une application g de Z dans N tel que g soit bijective

On pose

g(z) = 2z si z € N
g(z) = -(2z+1) si z € Z\N

g(0) = 0
g(-1) = 1
g(1) = 2
g(-2) = 3
g(2) = 4
g(-3) = 5

...
Tu vérifies qu'elle est bijective et voilà Z est dénombrable
On peut compter les entiers relatifs.

Merci joker, j'ai vu cette demo sur Wikipedia, mais je ne comprends pas ...
je ne vois pas quand je dois faire intervenir Z et N.

PEux tu m'expliquer comment on procede en general ? Car tu mets arbitrairement
g(z) = 2z si z € N
g(z) = -(2z+1) si z € Z\N

mais comment tu trouves les "g(z)" ?

Merci.

Posted by: legeniedesalpages

Bonjour,

tu prends un entier relatif z, à l'aide de cette fonction, si il est positif tu l'envoies vers un entier naturel pair, si il est strictement négatif tu l'envoies vers un entier naturel impair.

Il n'y a pas de cas général, c'est juste intuitif.

tu peux aussi montrer que - $\mathbb{N}$ est dénombrable, puis $\mathbb{Z}=-\mathbb{N}\cup \mathbb{N}$ est une union dénombrable en tant qu'union de deux ensembles dénombrables.

Posted by: juve1897

Citation:

Posté par legeniedesalpages

Bonjour,

tu prends un entier relatif z, à l'aide de cette fonction, si il est positif tu l'envoies vers un entier naturel pair, si il est strictement négatif tu l'envoies vers un entier naturel impair.

Il n'y a pas de cas général, c'est juste intuitif.

tu peux aussi montrer que - $\mathbb{N}$ est dénombrable, puis $\mathbb{Z}=-\mathbb{N}\cup \mathbb{N}$ est une union dénombrable en tant qu'union de deux ensembles dénombrables.

MErci pour ta reponse.

Je vais d'abord essayé de comprendre la definition, car je crois que c'est à ce niveau la que ça coince le plus ;)

Posted by: legeniedesalpages

quelle définition?

Posted by: juve1897

Citation:

Posté par legeniedesalpages

quelle définition?

la definition d'un ensemble denombrable:

Citation:

Un ensemble infini E est denombrable s'il existe une bijection de E vers N
soit card(E) = card(N)

Je n'arrive pas vraiment à la comprendre/

Posted by: Joker62

En fait, construire une bijection d'un ensemble E vers N ça veut dire qu'à chaque élément de E on peut associer un et un seul entier naturel, et qu'à tout entier naturel, on peut associer un et un seul élément de E.

Donc en gros, ça revient à compter les éléments de E.
Et tu remarques que compter et dénombrer c'est fort semblable

Posted by: juve1897

Citation:

Posté par Joker62

En fait, construire une bijection d'un ensemble E vers N ça veut dire qu'à chaque élément de E on peut associer un et un seul entier naturel, et qu'à tout entier naturel, on peut associer un et un seul élément de E.

Donc en gros, ça revient à compter les éléments de E.
Et tu remarques que compter et dénombrer c'est fort semblable

Oui joker,

je sais ce qu'est une bijection, mais le truc que je ne comprends pas c'est comment ect ce que tu veux compter un truc infini ...

enfin bon je vois que je suis bien loin de comprendre cette histoire de denombrement d'ensemble infini.

JE vais revoir à tete reposé cette definition et chercher qq exemple pour bien comprendre le raisonnement.

Merci

Posted by: Joker62

Bé c'est pas forcément compter, c'est juste comptable...

Posted by: juve1897

Citation:

Posté par Joker62

Bé c'est pas forcément compter, c'est juste comptable...

Ok merci.

comme je l'ai dit plus haut, je crois que je vais d'abord revoir les bases (injection, bijection ect...) je comprendrais peut etre meiux la definition ;)

Posted by: legeniedesalpages

oui voilà,

pour deux ensembles finis E et F, tu peux compter leurs éléments pour pouvoir les comparer.

par exemple E est un panier avec trois salades, et F est une cage avec trois lapins, tu vois qu'il y a autant de salades que de lapins, donc tu vas pouvoir donner une salade à chaque lapin et il ne te restera plus de salade :)

Pour des ensembles infinis G et H, c'est un peu différent, tu peux plus compter comme pour les ensemble finis.
Cependant tu as des instruments tres pratiques, tu vois que si à chaque élément de G tu peux associer un unique élément de H (c'est à dire si tu as une bijection de G dans H), tu peux dire qu'ils ont autant d'éléments.
Et donc comme ça tu peux comparer aussi des ensembles infinis entre eux.

Ici tu prends l'ensemble des entiers naturels et tu regardes donc quels sont les ensembles qui ont autant d'éléments, tu vois que ça ne marche pas pareil que les ensembles finis, tu as des ensembles comme $\mathbb{Z}$ et $\mathbb {Q}$ qui contiennent autant d'éléments que $\mathbb{N}$ , alors que ces ensembles contiennent non seulement $\mathbb{N}$ mais aussi d'autres éléments que ceux de $\mathbb{N}$ .
Tu vois aussi qu'il y a plusieurs types d'ensembles infinis car il y a des ensembles qui ne sont pas en bijection avec $\mathbb{N}$ , (l'exemple direct est $\mathcal{P}(\mathbb{N})$ avec le théorème de Cantor).

Posted by: Joker62

Que c'est mignon les laitues et les lapins :)

Mais sinon, c'est vrai que c'est étonnant de se dire qu'il y a autant d'élément dans Z que dans N alors que ces ensembles sont infinis, mais bon c'est comme ça :)

Posted by: juve1897

Citation:

Posté par legeniedesalpages

oui voilà,

pour deux ensembles finis E et F, tu peux compter leurs éléments pour pouvoir les comparer.

par exemple E est un panier avec trois salades, et F est une cage avec trois lapins, tu vois qu'il y a autant de salades que de lapins, donc tu vas pouvoir donner une salade à chaque lapin et il ne te restera plus de salade :)

Pour des ensembles infinis G et H, c'est un peu différent, tu peux plus compter comme pour les ensemble finis.
Cependant tu as des instruments tres pratiques, tu vois que si à chaque élément de G tu peux associer un unique élément de H (c'est à dire si tu as une bijection de G dans H), tu peux dire qu'ils ont autant d'éléments.
Et donc comme ça tu peux comparer aussi des ensembles infinis entre eux.

Ici tu prends l'ensemble des entiers naturels et tu regardes donc quels sont les ensembles qui ont autant d'éléments, tu vois que ça ne marche pas pareil que les ensembles finis, tu as des ensembles comme $\mathbb{Z}$ et $\mathbb {Q}$ qui contiennent autant d'éléments que $\mathbb{N}$ , alors que ces ensembles contiennent non seulement $\mathbb{N}$ mais aussi d'autres éléments que ceux de $\mathbb{N}$ .
Tu vois aussi qu'il y a plusieurs types d'ensembles infinis car il y a des ensembles qui ne sont pas en bijection avec $\mathbb{N}$ , (l'exemple direct est $\mathcal{P}(\mathbb{N})$ avec le théorème de Cantor).

Milles mercis Legeniedesalpages.

je crois que j'ai compris ...

MAis je ne vois pas comment tu veux trouver autant d'element dans Z que dans N alors que l'on sait que N est compris dans Z???

Posted by: juve1897

Citation:

Posté par Joker62

Que c'est mignon les laitues et les lapins :)

Mais sinon, c'est vrai que c'est étonnant de se dire qu'il y a autant d'élément dans Z que dans N alors que ces ensembles sont infinis, mais bon c'est comme ça :)

c'est ce que je me demandais

Posted by: legeniedesalpages

disons que les ensembles infinis ne suivent pas notre intuition de "nombre d'éléments",
mais vu la définition d'une bijection, et vu qu'on en a trouvé de Z dans N, c'est clair que N et Z ont autant d'éléments.

Posted by: juve1897

Citation:

Posté par legeniedesalpages

disons que les ensembles infinis ne suivent pas notre intuition de "nombre d'éléments",
mais vu la définition d'une bijection, et vu qu'on en a trouvé de Z dans N, c'est clair que N et Z ont autant d'éléments.

donc si je comprends bien je dois à chaque fois trouver une fonction qui a autant d'elements dans son ensemble de depart que dans N (ensemble d'arrivée) ???

Posted by: legeniedesalpages

Citation:

Posté par juve1897

donc si je comprends bien je dois à chaque fois trouver une fonction qui a autant d'elements dans son ensemble de depart que dans N (ensemble d'arrivée) ???

ça ne veut pas dire grand chose, une fonction n'a pas d'éléments, si tu veux montrer que E est en bijection avec N,

ou bien tu trouves une bijection $f:E\rightarrow \mathbb{N}$ , ou tu trouves une bijection $g:\mathbb{N} \rightarrow E$ , ou bien tu connais déjà un ensemble $F$ qui est en bijection avec $\mathbb{N}$ , et tu trouves une bijection de $E$ dans $F$ , ou de $F$ dans $E$ .

Cela découle du fait que " $E$ et $F$ sont en bijection" est une relation d'équivalence.

Posted by: juve1897

Citation:

Posté par legeniedesalpages

Merci legenie,

je vais essayé de me debrouiller avec ce que tu m'as expliquer, mm si j'avoue que je ne vois pas trop comment faire.

Edit: elles sont tres jolies tes forumules de maths, connais tu un site ou je pourrais apprendre le Latex ???

Posted by: legeniedesalpages

un formulaire de base: http://www.tuteurs.ens.fr/logiciels/latex/maths.html

Posted by: juve1897

Citation:

Posté par legeniedesalpages

un formulaire de base: http://www.tuteurs.ens.fr/logiciels/latex/maths.html

MErci bcp pour ton aide .

Posted by: minidiane

Je suis toujours perdu pour la deuxième démonstration
quelqu'un peut-il m'aider?