Dénombrabilité

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Avatar de l’utilisateur
Ncdk
Membre Rationnel
Messages: 758
Enregistré le: 30 Mar 2014, 19:10

Dénombrabilité

par Ncdk » 12 Sep 2015, 18:58

Bonjour,

1) En "rangeant" les éléments de x de la façon suivante :

(0,0), (0,1), (1,0), (0,2), (1,1), (2,1), (0,3), (1,2), ...

Déterminer une bijection possible de sur x

2) Que peut-on dire de l'application définie de x dans par ?

3) En déduire que est dénombrable

4) En déduire qu'une union dénombrable d'ensembles dénombrables est un ensemble dénombrable.
Que pensez-vous d'une union quelconque d'ensembles finis ou dénombrables ?


Tout d'abord, je pensais savoir faire la une mais pas du tout.
J'ai déjà commencé par ranger d'une différente manière les couples de points.
J'ai rangé en pyramide, en partant du sommet qui est (0,0) et je me suis rendu compte que chaque ligne gagné 2 couples, mais de la à déduire une bijection. J'ai du mal, car même en listant les couples que l'on a de cette manière :
0 --> (0,0)
1 --> (1,0)
2 --> (0,1)
3 --> (1,1)
...

Pour moi cette liste est interminable. M
Mais je sais juste que est dénombrable, comment je peux m'en servir ?



Avatar de l’utilisateur
zygomatique
Habitué(e)
Messages: 6928
Enregistré le: 20 Mar 2014, 12:31

par zygomatique » 12 Sep 2015, 19:08

salut

soit n un entier naturel ...

que peux-tu dire des couples (p, q) tels que p + q = n ?

n'est-il pas normal que cette liste soit interminable, N l'étant lui-même ?

et je rangerai plutôt la liste ainsi ::

(0, 0)
(0, 1), (1, 0)
(0,,2), (1, 1), (2, 0)
....
Ce qui est affirmé sans preuve peut être nié sans preuve. EUCLIDE

Avatar de l’utilisateur
Ncdk
Membre Rationnel
Messages: 758
Enregistré le: 30 Mar 2014, 19:10

par Ncdk » 12 Sep 2015, 19:16

Est-ce qu'avec le relation que tu as marqué on peut créer une application et on voit qu'elle est déjà surjective si je dis pas de bêtises.

Une application qui va de x dans

n'est-il pas normal que cette liste soit interminable, N l'étant lui-même ?


Evidemment, je crois que j'ai pas prit le temps de réfléchir ni de me relire avant de poster... :triste:

Sinon la liste j'avais pas vu ça comme ça, c'est pas mal :)

Avatar de l’utilisateur
zygomatique
Habitué(e)
Messages: 6928
Enregistré le: 20 Mar 2014, 12:31

par zygomatique » 12 Sep 2015, 19:55

Ce qui est affirmé sans preuve peut être nié sans preuve. EUCLIDE

Avatar de l’utilisateur
Ncdk
Membre Rationnel
Messages: 758
Enregistré le: 30 Mar 2014, 19:10

par Ncdk » 12 Sep 2015, 20:27

zygomatique a écrit:pour trouver l'inspiration :: http://forums.futura-sciences.com/mathematiques-superieur/351048-bijection-n-n.html

....


Mais si je prends une application du style :

f:x -->
(p,q) ---> p+q

Si je montre qu'il y a une bijection c'est bon non ?

Avatar de l’utilisateur
zygomatique
Habitué(e)
Messages: 6928
Enregistré le: 20 Mar 2014, 12:31

par zygomatique » 12 Sep 2015, 20:45

2 + 3 = 1 + 4 .....
Ce qui est affirmé sans preuve peut être nié sans preuve. EUCLIDE

Avatar de l’utilisateur
Ncdk
Membre Rationnel
Messages: 758
Enregistré le: 30 Mar 2014, 19:10

par Ncdk » 12 Sep 2015, 21:26

Je vois pas alors, hum...

J'ai regardé ton lien, et notamment la question 2) de ce lien me parait en rapport avec la situation.

Robot

par Robot » 12 Sep 2015, 22:32


Avatar de l’utilisateur
Ncdk
Membre Rationnel
Messages: 758
Enregistré le: 30 Mar 2014, 19:10

par Ncdk » 12 Sep 2015, 23:01

Robot a écrit:


Heu... comment on trouve cette relation ?

Avatar de l’utilisateur
zygomatique
Habitué(e)
Messages: 6928
Enregistré le: 20 Mar 2014, 12:31

par zygomatique » 12 Sep 2015, 23:23

ouais mais ça c'est de N² dans N ... et nous on veut de N dans N² ....

mais bon ça aide tout de même .... puisqu'une bijection est inversible ....
Ce qui est affirmé sans preuve peut être nié sans preuve. EUCLIDE

Robot

par Robot » 13 Sep 2015, 07:02

Remarque :

est la somme des entiers de à .

Avatar de l’utilisateur
Ncdk
Membre Rationnel
Messages: 758
Enregistré le: 30 Mar 2014, 19:10

par Ncdk » 13 Sep 2015, 10:38

Bonjour,

Je ne comprends toujours pas comment cette relation arrive, tu peux m'expliquer comment tu l'as trouves ?

Sinon j'ai décidé d'avancer un peu dans l'exercice, la question 2 est faites, j'ai prouvé que c'était bijectif, mais concernant la question 3, je vois pas l'astuce pour en déduire que Q est dénombrable.

Est-ce qu'il y a un lien entre N et Q par exemple ?

EDIT : En créant par exemple une application ?

Avatar de l’utilisateur
zygomatique
Habitué(e)
Messages: 6928
Enregistré le: 20 Mar 2014, 12:31

par zygomatique » 13 Sep 2015, 11:27

n'est-il pas vrai que tout entier s'écrive ?
Ce qui est affirmé sans preuve peut être nié sans preuve. EUCLIDE

Robot

par Robot » 13 Sep 2015, 11:53

Ncdk a écrit:Je ne comprends toujours pas comment cette relation arrive, tu peux m'expliquer comment tu l'as trouves ?


On a d'abord : 1 couple (p,q) avec p+q=0, puis 2 couples (p,q) avec p+q=1, rangés dans l'ordre des p croissants, puis 3 couples (p,q) avec p+q=2, rangés dans l'ordre des p croissants etc.

La formule que j'ai écrite donne le rang (en partant de 0) du couple (p,q) dans la liste.

Dans l'autre sens, partant de ce rang , on peut retrouver le couple : prendre le plus grand entier naturel tel que . Alors et

Edit : correction de formule

Avatar de l’utilisateur
Ncdk
Membre Rationnel
Messages: 758
Enregistré le: 30 Mar 2014, 19:10

par Ncdk » 13 Sep 2015, 12:42

zygomatique a écrit:n'est-il pas vrai que tout entier s'écrive ?


Si, seulement si p et q le sont aussi.

Merci Robot pour l'explication, parfait, du coup pour déterminer une bijection possible, il suffit de faire une petite étude de l'injectivité et de la surjectivité et le tour est jouer :)

Avatar de l’utilisateur
Ncdk
Membre Rationnel
Messages: 758
Enregistré le: 30 Mar 2014, 19:10

par Ncdk » 15 Sep 2015, 18:25

Bonjour,

Je reviens sur la question 3 :zen:

Avec la première question, on a prouvé qu'il existait une bijection de

Mais si on prends une application f : , je cherche à en trouver une, si on trouve que cette application est bijective on pourra directement conclure que est dénombrable non ?

Avatar de l’utilisateur
zygomatique
Habitué(e)
Messages: 6928
Enregistré le: 20 Mar 2014, 12:31

par zygomatique » 15 Sep 2015, 19:21

oui ..............
Ce qui est affirmé sans preuve peut être nié sans preuve. EUCLIDE

Avatar de l’utilisateur
Ncdk
Membre Rationnel
Messages: 758
Enregistré le: 30 Mar 2014, 19:10

par Ncdk » 15 Sep 2015, 19:51

Mais je n'ai pas tellement l'idée pour créer l'application.

En prenant p + q = n, avec (p,q) un couple de N²

Je vois ce que ça donne le n, c'est le nombre de couple que l'on peut créer non ?

Robot

par Robot » 15 Sep 2015, 22:12

Pour montrer la dénombrabilité de , il suffit d'avoir une injection de dans , ou une surjection de sur .

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 183 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite