NxN dénombrable

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Archytas
Habitué(e)
Messages: 1223
Enregistré le: 19 Fév 2012, 15:29

NxN dénombrable

par Archytas » 03 Aoû 2013, 16:40

Salut,
Je comprends pas la solution de l'exercice 6 !
Merci !



Nightmare
Membre Légendaire
Messages: 13817
Enregistré le: 19 Juil 2005, 19:30

par Nightmare » 03 Aoû 2013, 16:56

Trace le chemin décrit par la fonction g tu verras qu'en continuant on passe par tous les couples d'entiers une unique fois.

Dlzlogic
Membre Transcendant
Messages: 5273
Enregistré le: 14 Avr 2009, 14:39

par Dlzlogic » 03 Aoû 2013, 16:59

Bonjour,
Moi non plus.
Le point de départ est que N est dénombrable. Partant de là, pourquoi pas ?

Archytas
Habitué(e)
Messages: 1223
Enregistré le: 19 Fév 2012, 15:29

par Archytas » 03 Aoû 2013, 18:11

Nightmare a écrit:Trace le chemin décrit par la fonction g tu verras qu'en continuant on passe par tous les couples d'entiers une unique fois.

Qu'appelles tu le chemin de la fonction ? g(0) puis g(1), g(2) etc... Ce que je comprends pas c'est que si on pose (déjà je comprends pas pourquoi ça c'est bijectif) ensuite si c'est bijectif on a que la moitié des couples (n>=k) et du coup je comprends pas pourquoi par exemple g(2)=(0,1)... (Et désolé de te demander ça mais si tu pouvais me donner d'autres arguments que le graphe ça serait cool, j'aime bien quand c'est bien rigoureux (J'aime bien aussi quand c'est visuel bien sûr mais on va dire que c'est bonus :ptdr: )).

Nightmare
Membre Légendaire
Messages: 13817
Enregistré le: 19 Juil 2005, 19:30

par Nightmare » 03 Aoû 2013, 18:59

Vouloir être rigoureux c'est bien mais ça ne sert à rien si on ne comprend pas d'où vient la démo.

Si tu comprends le dessin alors tu comprendras toute la démo et pourra y mettre toute la rigueur que tu veux, bien plus que ce que te proposes ton pdf peu précis.

L'idée c'est qu'un ensemble dénombrable est un ensemble dont on peut numéroter les éléments à l'aide des entiers. Le dessin fournit exactement une numérotation, d'où l'intérêt de le comprendre avant de vouloir le formaliser.

Archytas
Habitué(e)
Messages: 1223
Enregistré le: 19 Fév 2012, 15:29

par Archytas » 03 Aoû 2013, 19:50

Nightmare a écrit:Vouloir être rigoureux c'est bien mais ça ne sert à rien si on ne comprend pas d'où vient la démo.

Si tu comprends le dessin alors tu comprendras toute la démo et pourra y mettre toute la rigueur que tu veux, bien plus que ce que te proposes ton pdf peu précis.

L'idée c'est qu'un ensemble dénombrable est un ensemble dont on peut numéroter les éléments à l'aide des entiers. Le dessin fournit exactement une numérotation, d'où l'intérêt de le comprendre avant de vouloir le formaliser.

Ok pour le dessin, mais pourquoi n(n+1)/2 et k ? ça a un rapport avec le fait que ce soit diagonal ? Si on voulais le faire en petits carré on prendrait g(n(n+1)(2n+1)/6+k) ?

Nightmare
Membre Légendaire
Messages: 13817
Enregistré le: 19 Juil 2005, 19:30

par Nightmare » 03 Aoû 2013, 20:17

Le n(n+1)/2+k se comprend aussi à travers le dessin.

Par exemple essaye de trouver à l'aide du graphe à quel numéro va correspondre le couple (5,9). Quid du couple (17,48)?

Sourire_banane
Membre Irrationnel
Messages: 1355
Enregistré le: 23 Juil 2013, 13:48

par Sourire_banane » 03 Aoû 2013, 20:22

Salut,

En ayant pas regardé vos commentaires ni rien, je suppose que pour montrer la dénombrabilité de NxN, il suffit d'exhiber une bijection phi de NxN vers N qui convient. En dessinant un réseau N², on peut imaginer une spirale, c'est suffisant ?

PS : Sorry, je fais du ZxZ. Donc on peut faire des zig-zag ?

Nightmare
Membre Légendaire
Messages: 13817
Enregistré le: 19 Juil 2005, 19:30

par Nightmare » 03 Aoû 2013, 20:29

Oui c'est bien l'idée et la spirale pour Z^2 marche parfaitement.

Cela étant tout ceci est très géométrique. Une preuve arithmétique serait d'utiliser la décomposition en facteurs premiers des entiers pour les numéroter : (a,b) est le couple numéro 2^a * (2b+1)

Sourire_banane
Membre Irrationnel
Messages: 1355
Enregistré le: 23 Juil 2013, 13:48

par Sourire_banane » 03 Aoû 2013, 20:35

Hmmmm, je vois pas comment tu fais pour en arriver à là...

Archytas
Habitué(e)
Messages: 1223
Enregistré le: 19 Fév 2012, 15:29

par Archytas » 03 Aoû 2013, 20:47

Nightmare a écrit:Le n(n+1)/2+k se comprend aussi à travers le dessin.

Par exemple essaye de trouver à l'aide du graphe à quel numéro va correspondre le couple (5,9). Quid du couple (17,48)?

J'en sais rien 9>5 on peut donc pas utiliser la formule, si ? C'est vrai qu'on voit avec le graphe que ça marche mais la méthode du "etc" utilisée dans le pdf est loin d'être suffisante à mon sens... Bref, je suis un peu perdu avec l'empirisme du pdf. Pourquoi cette formule et pourquoi ça marche ?

Archytas
Habitué(e)
Messages: 1223
Enregistré le: 19 Fév 2012, 15:29

par Archytas » 03 Aoû 2013, 20:48

Sourire_banane a écrit:Hmmmm, je vois pas comment tu fais pour en arriver à là...

Ces deux entiers désignent un seul et unique entier n.

Sourire_banane
Membre Irrationnel
Messages: 1355
Enregistré le: 23 Juil 2013, 13:48

par Sourire_banane » 03 Aoû 2013, 20:50

Archytas a écrit:Ces deux entiers désignent un seul et unique entier n.

Effectivement, en le voyant d'un tel point de vue !

Nightmare
Membre Légendaire
Messages: 13817
Enregistré le: 19 Juil 2005, 19:30

par Nightmare » 03 Aoû 2013, 20:52

Je n'arrive nulle part, je pars d'un résultat qui est que tout entier naturel s'écrit de manière unique sous la forme 2^a * (2b+1) qui revient à la donnée d'un unique couple d'entier (a,b).

Donc :
le couple numéro 1 sera (0,0) car 1=2^0 * (2*0 +1)
le couple numéro 2 sera (1,0) car 2=2^1 * (2*0+1)
...
le couple numéro 44 sera (2,5) car 44=2^2 * (2*5+1)
etc.

Avec cette énumération on peut numéroter tous les couples de N^2, qui est donc dénombrable.

Nightmare
Membre Légendaire
Messages: 13817
Enregistré le: 19 Juil 2005, 19:30

par Nightmare » 03 Aoû 2013, 20:55

Archytas je ne te demande pas de trouver le numéro des couples que je t'ai donné à l'aide de la formule mais à l'aide du graphe!

Nightmare
Membre Légendaire
Messages: 13817
Enregistré le: 19 Juil 2005, 19:30

par Nightmare » 03 Aoû 2013, 21:03

Voir le graphe numéroté ici :https://encrypted-tbn1.gstatic.com/images?q=tbn:ANd9GcSVCdMFW9FQOyisPpNAMpls4wTtar10pUNu-jTvPj89aVTKmjNe1zsdyF0Bfw

Par exemple le couple (4,2) a le numéro 23. Je réitère alors ma question : selon ce processus de numérotation, quel va être le numéro du couple (17,48) ?

Nightmare
Membre Légendaire
Messages: 13817
Enregistré le: 19 Juil 2005, 19:30

par Nightmare » 03 Aoû 2013, 21:06


Archytas
Habitué(e)
Messages: 1223
Enregistré le: 19 Fév 2012, 15:29

par Archytas » 03 Aoû 2013, 22:30


Oui le graphe je l'ai déjà fait mais je vais pas tout faire jusqu'à (17,48), j'imagine que tu veux que je trouve une règle spéciale mais je vois vraiment pas... Et je vois toujours pas le rapport entre la formule et le graphe.

jlb
Habitué(e)
Messages: 1886
Enregistré le: 27 Jan 2013, 19:35

par jlb » 04 Aoû 2013, 02:29

Archytas a écrit:Qu'appelles tu le chemin de la fonction ? g(0) puis g(1), g(2) etc... Ce que je comprends pas c'est que si on pose (déjà je comprends pas pourquoi ça c'est bijectif) ensuite si c'est bijectif on a que la moitié des couples (n>=k) et du coup je comprends pas pourquoi par exemple g(2)=(0,1)... (Et désolé de te demander ça mais si tu pouvais me donner d'autres arguments que le graphe ça serait cool, j'aime bien quand c'est bien rigoureux (J'aime bien aussi quand c'est visuel bien sûr mais on va dire que c'est bonus :ptdr: )).


le principe: tu parcours NxN en suivant les diagonales (0,0) (1,0)(0,1) (2,0)(1,1)(0,2) (3,0)(2,1)(1,2)(0,3) (4,0)..... et donc la fonction g associe à la place-1 d'un couple de cette liste, le couple

en 1ère position -1=0 c'est le premier couple (0,0)
en 2-1=1 c'est le couple (1,0) et ainsi de suite

donc pour un entier m donné, est associé le couple en m+1 position dans la liste.

l'objectif c'est de trouver sur quelle diagonale est le couple en m+1 position soit le n tel que
n(n+1)/2 =<m+1<(n+1)(n+2)/2 ( car sur la diagonale i, il y a i+1 couples!!)et ensuite tu trouves le k par différence k=m+1-n(n+1)/2

je ne sais pas si j'ai été clair, mais le principe c'est de bien comprendre comment tu parcours NxN.
Et là si tu as compris tu peux répondre à Nightmare pour (48,17)!!!

jlb
Habitué(e)
Messages: 1886
Enregistré le: 27 Jan 2013, 19:35

par jlb » 04 Aoû 2013, 02:55

Archytas a écrit:Qu'appelles tu le chemin de la fonction ? g(0) puis g(1), g(2) etc... Ce que je comprends pas c'est que si on pose (déjà je comprends pas pourquoi ça c'est bijectif) ensuite si c'est bijectif on a que la moitié des couples (n>=k) et du coup je comprends pas pourquoi par exemple g(2)=(0,1)... (Et désolé de te demander ça mais si tu pouvais me donner d'autres arguments que le graphe ça serait cool, j'aime bien quand c'est bien rigoureux (J'aime bien aussi quand c'est visuel bien sûr mais on va dire que c'est bonus :ptdr: )).


Bonsoir, parcours en diagonale (0,0) (1,0) (0,1) (2,0)(1,1)(0,2) (3,0)(1,2)(2,1)(0,3) (4,0)... considère alors la position des couples dans cette liste, cela va te donner le lien fonctionnel établi par g.

Après, pour répondre à Nightmare, regarde combien de couples sur une diagonale "i" et la propriété de ces couples sur cette diagonale. Bonne recherche.

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 17 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