Ensembles dénombrables

OShine

Bonsoir. 
Je ne comprends pas le corrigé de cet exercice. 

Heuristique

Il va falloir être plus explicite sur ton incompréhension si tu veux un coup de main...

Au passage, cela me semble un peu prématuré de t'attaquer à la dénombrabilité.

Dom

On parle de l’exercice 2. 

Le dessin, moi, il me semble clair pour l’idée. 

On établit une bijection de $\mathbb N$ dans $\mathbb N^2$. 

L’idée est d’expliciter cette suite. 

La correction n’entend pas expliciter la suite « dans l’ordre » mais ligne par ligne. 

1) Elle décrit la première ligne, l’axe des abscisses (une demi-droite entière, infinie donc…).  

On remarque la suite bien connue…

2) Puis, la ligne du dessus ($y=1$), c’est la même ligne que l’axe des abscisses auquel on ajoute $1$ à chaque terme. Enfin… pas juste au dessus mais « juste au-dessus à gauche ».

3) Idem pour les lignes ($y=k$). 

Je ne vérifie absolument pas les expressions. 
Ça c’est ton boulot. 

Amédé

C'est le théorème de Fueter-Polya... Essaye de compter 1,2,3,4,... sur le dessin peut-être que la lumière apparaitra.

Je te propose une autre méthode. Tout entier $n$ s'écrit $n=2^{k}(2m+1)$. À toi de trouver la bijection.

OShine

Ok mais je ne comprends pas la formule $f(p,q)=f(k,0)+q$ d'où elle sort.
Amédé tu donnes un résultat non démontré. 

Amédé

Je ne donne aucun résultat.

OShine

Tout entier naturel s'écrit... Tu ne le démontres pas.
Mais je bloque sur le corrigé et toi tu me donnes une autre méthode ça fait trop d'informations pour moi.

Alexique

Tu as un plan muni d'un repère. Les abscisses sont notées $p$ et les ordonnées $q$. Le point $(p,q)$ a pour valeur $f(p,q)$ tel que construit sur le dessin qui est très clair. Les diagonales ont pour équation $p+q=k$. Donc partant du point $(k,0)=(p+q,0)$ de valeur $f(k,0)$, on remonte la diagonale de $q$ ordonnées pour atteindre $(p,q)$ de valeur $f(p,q)$ puisque sur une diagonale, les valeurs sont consécutives croissantes vers le haut.

Ça, c'est comment on trouve la formule de la bijection. Une fois qu'elle est trouvée, il est plus propre de démontrer qu'elle est bien bijective mais en soi, le dessin fait le travail.

Encore dommage que tu nous sortes le corrigé pour un si joli problème. C'était une belle occasion de te faire chercher comment remplir le plan avec tous les entiers naturels.

lourrran

Ici, l'exercice t'aide beaucoup. Il ne te demande pas de trouver une bijection qui fonctionne, il t'en donne une.
Qu'est-ce qu'il reste à faire ?
Trouver la formule qui donne f(p,q) ? ou plutôt, comme le corrigé la donne, vérifier que cette formule est correcte.

Ici, disons que le dessin prouve que cette fonction est une bijection. Mais on pourrait voir l'exercice différemment : on a la formule donnée par le corrigé, et il faut prouver que cette formule définit une bijection.

Ne lis pas tout, sinon tu vas dire qu'il ne fallait pas donner la solution. Lis juste le 1er paragraphe, puis le 2ème si nécessaire...
Pour chaque paragraphe que tu lis, arrête toi 5 minutes. Retourne voir le dessin du bouquin. Essaie de voir si tu sais finir les calculs, sans lire la suite.

Maintenant, comment un lycéen va arriver à trouver cette formule ?  Pour un nombre comme 14 sur le dessin, ce nombre a été écrit sur la colonne p=0 et la ligne q=4. Quelle formule f(p,q) va nous donner f(0,4)=14 ?

Déjà, on voit que ce qui compte, c'est de trouver sur quelle diagonale descendante on se trouve. Les 5 nombres 10, 11, 12, 13, 14 ont été écrits sur la diagonale d'équation p+q=4.
Et pour ces 5 points, la valeur qu'on écrit est 10+q.
D'ou vient ce 10 ?

On a 10, parce que tous les nombres plus petits que 10 sont déjà écrits dans le triangle en-dessous de cette diagonale. 
Pour une diagonale donnée, on a donc besoin de connaître le nombre de points dans le triangle en dessous de cette diagonale. 

Tout ça, normalement, ça devrait te faire penser aux nombres triangulaires. 
Ce devrait te rappeler des exercices que tu as faits, ou plutôt que tu feras quand tu accepteras d'essayer des exercices de niveau lycée.
Et même si l'expression 'nombre triangulaire' ne te parle pas, on va retrouver ce résultat facilement.
Le triangle défini par $p+q < n$ contient combien de points ? 1+2+...+n = ?
Il faut être très vigilant dans les calculs. La numérotation des lignes et des colonnes commence à 0. En écrivant ce message un peu vite, je me suis trompé à cause de ça, et comme je n'arrivais pas à la formule du corrigé, j'ai retrouvé l'erreur.

1+2+...n=n(n+1)/2 
C'est le nombre de points dans le triangle de côté n. Comme on numérote les points à partir de 0 et pas de 1, le 1er nombre disponible quand on commence la diagonale d'équation p+q=n, c'est n(n+1)/2, c'est à dire (p+q)(p+q+1)/2
Et pour chaque point de cette diagonale, la valeur qu'on va écrire est (p+q)(p+q+1)/2+q

On trouve bien la formule du corrigé.

Amédé

OShine a dit :

Tout entier naturel s'écrit... Tu ne les démontres pas.

Ah... Si tu écris la décomposition de $n$ en facteur premier tu as $n=2^{k}p_{1}^{a_{1}}\cdots p_{s}^{a_{s}}$. Les $p_{i}$ sont impairs donc $p_{1}^{a_{1}}\cdots p_{s}^{a_{s}}$ est impair ainsi il s'écrit $2m+1$... C'est un truc que tu as fait il y a une semaine ou deux dans un e^{10000}-ième fil à rallonge. Mes élèves de spé maths savent le faire.

OShine

@Heuristique je suis arrivé à ce chapitre dans le livre, et on ne peut pas faire grand chose qui suit sans la dénombrabilité. On est obligé de se lancer dedans même si c'est dur. J'ai vu la compacité et les espaces vectoriels normés, c'est aussi très compliqué.

Sinon je n'ai rien compris aux explications. Déjà $f$ n'est même pas définie, et à partir de $p+q=k$ je ne comprends plus rien.

gerard0

Quelle mauvaise foi ! " Je ne veux pas réfléchir, je ne cherche pas à comprendre, expliquez-moi avec tous les détails". Dans n'importe quelle discipline on appelle ça de la fainéantise ...

Mais il y aura sans doute encore un ahuri pour "l'aider" ...

Remarque : encore une fois, ce n'est pas la difficulté qui l'arrête, mais le refus systématique de penser seul, comme on refuse de faire seul à 4 ans.

troisqua

gerard0: il y en a aura même plusieurs. Le problème "OShine" n'est en fait pas spécifiquement le problème "Oshine".

raoul.S

OShine, je te ferais remarquer que les coordonnées des points des diagonales vérifient $p+q=\text{constante}$. Par exemple les coordonnées des points de la troisième diagonale (celle où il y a 3,4,5) vérifient $p+q=2$... (mon nouvel hobby c'est casser les pieds de troisqua )

Blagues à part, sur le fond je suis d'accord avec troisqua. Demande à ton répétiteur de t'expliquer. Le problème est que si tu ne comprends pas la correction de ce type d'exo très simple c'est quand même mal barré pour la suite... 

lourrran

Si OShine était prof en lycée, il pourrait demander à ses élèves de l'aider sur cet exercice.
Mais malheureusement, il n'est pas prof en lycée.
Peut-être a-t-il dans son entourage un cousin ou un proche qui aime les maths ? Un collègue dans son collège ?

@gerard0
Je pense qu'il est sincèrement incapable de prendre une initiative devant un exercice de maths. Il ne peut pas être fainéant, alors qu'il passe autant d'heures à lire des corrigés. Ses lacunes sont ailleurs, ce n'est pas de la fainéantise, c'est une incapacité à comprendre et à retenir.

JLapin

@OShine

Est-ce que tu saurais faire le lien entre cette correction que tu ne comprends pas et les équations cartésiennes de certaines droites parallèles entre elles ?

Sinon, tu pourras poser la question à ton prof particulier.

OShine

En même temps la dénombrabilité c'est du dénombrement, et le dénombrement c'est l'un des domaines les plus difficiles des mathématiques.

@JLapin pas vraiment.

@raoul.S ok pour $p+q=k$ mais je n'ai pas compris comment calculer $f(p,q)$ ni d'où sort le $f(p,q)=f(k,0)+q$ ni comment en déduire $f(p,q)$ dans le cas général.

@lourrran je suis le seul à faire des maths de supérieur parmi mes collègues.

raoul.S

OShine a dit : 

@raoul.S ok pour $p+q=k$ mais je n'ai pas compris comment calculer $f(p,q)$ ni d'où sort le $f(p,q)=f(k,0)+q$ ni comment en déduire $f(p,q)$ dans le cas général.

Peut-être qu'il vaut mieux que tu dises ce que tu as compris, ce sera plus rapide...

OShine

@gerard0 j'ai réfléchi durant 45 min et je n'y arrive pas et même en relisant le message d'Alexique plusieurs fois car il m'a l'air le plus clair pour moi. Je fais un blocage sur cet exercice.

Thierry Poma

@OShine : tu as une très bonne réponse ici-même.

julian

Je doute qu'il ne soit pas sérieux, ceci dit, il s'y prend très mal ! C'est comme installer un toit sur une maison avant d'avoir commencé par les fondations... 😔

OShine

Pour le message de @lourrran je comprends la moitié mais la fin je ne comprends plus. 

troisqua

Je crois qu'Oshine nous a dit qu'il verrait avec son prof particulier. Je pense que c'est une très très bonne idée de sa part. C'est suffisamment rare pour être souligné.

gerard0

Lourran,

je connais des gros travailleurs qui sont prêts à apprendre par cœur un livre de cours de L1, mais reculent devant la tâche intellectuelle de penser par eux même. C'est de la fainéantise, intellectuelle. En effet, réfléchir vraiment, chercher de quoi parle la question, est fatigant pour celui qui n'a jamais fait ça, sans compter qu'on n'est pas sûr d'y arriver, donc qu'on va peut-être perdre du temps pour rien. OS confirme en deux phrases :

"@gerard0 j'ai réfléchi durant 45 min et je n'y arrive pas" + "En même temps la dénombrabilité c'est du dénombrement, et le dénombrement c'est l'un des domaines les plus difficiles des mathématiques."

Autrement dit, en 45 mn, il ne s'est pas aperçu qu'il ne s'agit pas d'une question de dénombrement, mais de repérage dans le plan (niveau quatrième ou troisième) ni du lien avec les équations de droite (p+q=k, où p est une abscisse et q une ordonnée - ou l'inverse).

Il est vrai qu'il est très faible sur les maths du lycée, mais là c'est la flemme totale, il ne veut pas le faire. Ou d'imbécillité, mais je je crois bien trop fin pour que ce ne soit pas autre chose que de la flemme intellectuelle.

Cordialement.

NB : Je compte déjà trois "ahuris".

Thierry Poma

@OShine : veux-tu préciser le repère à partir duquel tu ne comprends pas, s'il te plait ?

julian

Gerard, je n'en fais pas partie j'espère 😊

Médiat_Suprème

Quitte à me faire insulter, je peux assumer d'être un ahuri si c'est pour aider quelqu'un de dédié et à la vue des messages de OShine, je ne doute pas qu'il le soit.
@OShine : Ce qui suit n'est pas des mathématiques, et avant de parler du produit cartésien de deux ensembles dénombrables, je vais parler de leur union.

1) Union de 2 ensembles dénombrables. Imaginez que vous ayez 2 sacs contenant chacun une infinité dénombrable de cailloux, comment faire, en retirant un caillou d'un sac au choix à chaque étape (qui dure 1s à chaque fois), pour vider les 2 sacs. Il est facile de voir que si, pour commencer, on ne retire que les cailloux du premier sac, comme celui-ci ne sera jamais vide, on ne retirera aucun caillou du deuxième sac, quel que soit le temps passé.

Par contre si on prend un caillou du premier, puis un du deuxième, et on recommence en alternant à chaque fois, on finira par vider ces 2 sacs (en un temps infini), on peut comprendre ce dernier point (qui n'est pas trivial) de la façon suivante : est-ce qu'il peut rester un objet dans le premier sac ? Est-ce que le 17ième objet peut rester dans ce sac ? Clairement non, puisque je l'ai retiré la 17ème fois que j'ai retiré un objet du premier sac, est-ce qu'il peut rester un objet dans le deuxième sac ? Est-ce que le 17-ième objet peut rester dans ce sac ? Clairement non, puisque je l'ai retiré la 17ème fois que j'ai retiré un objet du deuxième sac.

Est-ce qu'il peut rester un objet dans le premier sac ? Est-ce que le n-ième objet peut rester dans ce sac ? Clairement non, puisque je l'ai retiré la nème fois que j'ai retiré un objet du premier sac, est-ce qu'il peut rester un objet dans le deuxième sac ? Est-ce que le n-ième objet peut rester dans ce sac ? Clairement non, puisque je l'ai retiré la n-ème fois que j'ai retiré un objet du deuxième sac.

Évidemment, cela se mathématise "facilement.

2) Produit cartésien de 2 ensembles dénombrables. On verra plus tard si vous considérez ces explications d'ahuris, utiles.

Soc

J'ai du mal avec le concept de "vider" dans le sens ou à n'importe quelle étape on n'est pas plus avancé qu'au début puisqu'il reste autant de cailloux qu'au début. On peut peut-être plutôt dire que n'importe quel tas fini de cailloux dans ces sacs finira par être vidé à un moment ou à un autre.

Médiat_Suprème

À chaque étape, vous avez raison, puisque chaque étape apparaît à un temps fini, mais qu'en est-il au bout d'un temps infini ?

C'est pourquoi j'ai posé la question autrement : quel objet reste dans un sac au bout d'un temps infini ?

C'est la même chose que si je compte les entiers 0, 1, 2, ... , n, ..., évidemment à chaque étape je n'ai compté qu'une partie finie, mais "à la fin" je les aurai tous comptés, puisqu'il n'en restera plus (comme quoi l'idée que Chuck Norris ait compté jusqu'à l'infini, deux fois, n'est pas si idiote) ; vous aurez remarqué que mon "à la fin" est idiot (puisqu'il n'y a pas de fin) mais si je me pose la question sous un autre angle (que reste-t-il), la question (non triviale, je répète) devient facile à répondre.

En fait, on donne ici un sens  à la question : "si je "compte" une infinité d'entiers, est-ce que je peux les compter tous (*)", ou encore "où en est-on, après un temps infini".

Et on peut jouer avec cette idée pour obtenir de jolis paradoxes (dans le sens contraire à l'intuition)

gerard0

Julian, relis ce que j'avais écrit ...

Médiat, tu passes à côté du problème d'OS : Relis son premier message, son problème est le corrigé de l'exercice 2. La notion intuitive de dénombrable l'intéresse-t-elle ? Peu probable.

Cordialement.

julian

Sauf que là, on est dans le cas infini dénombrable... 

Soc

Quand je demande à mes 6e quel est le plus petit nombre strictement positif, je finis toujours par avoir une réponse du genre "on met une infinité de 0 après la virgule et ensuite on met un 1"

Martial

@Soc : c'est normal que tes élèves de 6ème fassent cette erreur. Il existe plusieurs démonstrations du fait que $0,000....1 = 0$, mais aucune n'est compréhensible à ce niveau.

Martial

@gerard0 : je ne pense pas que @Médiat passe à côté du problème quand il parle de vider des sacs. Pour moi c'est un peu comme quand on parle de chaussures et de chaussettes pour expliquer AC.

Ceci dit je comprends ton point de vue : ce qui intéresse OS c'est de résoudre son exercice. Mais peut-être qu'un peu de vulgarisation peut l'aider...

Compte tenu du contexte je dois être un semi-ahuri. Mais j'ai fait la moitié du travail accompli par @Médiat, puisque j'ai vidé MON sac.

OShine

@Thierry Poma
A partir du triangle.

@Médiat_Suprème
D'accord merci même si ma question portait sur le corrigé de l'exercice et surtout la formule avec $f(p,q)$.
La notion d'ensemble dénombrable m'a l'air intuitive, on associe chaque élément de l'ensemble à un entier naturel, en gros on numérote les éléments de l'ensemble par les entiers naturels en partant de $0$ et dans l'ordre croissant.

Ma difficulté est de comment trouver l'expression de $f(p,q)$. J'ai cherché une vidéo de Maths Adultes et le prof n'explique pas comment l'obtenir, il dit juste de vérifier que ça marche.

La formule donnée par le corrigé ne fonctionne pas. Si je prends $(2,1)$ il appartient à la droite $p+q=3$  or $f(2,1)=7$ alors $f(3,0)+1=3+1=4$ 
https://www.youtube.com/watch?v=6JS6huQZ3gk

lourrran

@OShine
Tu dis que tu es le seul à faire des maths du supérieur parmi tes collègues.
Soit.
Mais je pense (j'espère) que tes collègues n'ont aucune difficulté à faire cet exercice. Sans avoir à consulter le corrigé.

OShine

@lourrran il y a une façon encore plus simple de résoudre l'exercice en utilisant l'injection $\N^2 \ \longrightarrow \N \\ (p,q) \mapsto 2^p 3^q$ et on utilise l'unicité de la décomposition en facteurs premiers.

Je pense avoir enfin compris la logique. On se balade sur les droites d'équations $p+q=k$. On part de l'axe des abscisses, on prend la droite qui va correspondre au couple recherché, et à chaque fois on ajoute $1$ quand on monte de $1$. L'idée principale étant de se balader que sur les droites.

Si je prends le couple $(3,1)$ on a $p+q=4$. Sur le dessin, on a $f(3,1)=11$.

Or $f(4,0)= 10$. Et $q=1$ puis $10+1=11$.

C'est surtout l'explication d' @Alexique qui m'a permis de comprendre, il a vraiment très bien expliqué.

lourrran

Oui, ta solution est plus simple.
L'énoncé demandait un dessin pour visualiser cette bijection entre N et N^2, tu as fait le dessin pour ta solution ?
L'énoncé demandait une bijection entre N et N^2, tu as vérifié si ta fonction est une bijection ?

OShine

@lourrran je pense que cette méthode est beaucoup plus simple à comprendre avec le dessin d'où le conseil de faire un dessin.
D'après le cours un ensemble infini est dénombrable si et seulement si il existe une injection entre $\N^2$ et $\N$.
Montrons que $f$ est injective. Soient $(p,q)$ et $(p',q')$ tels que $f(p,q)=f(p',q')$.
Alors $(p+q)(p+q+1)+ 2q = (p'+q')(p'+q'+1)+ 2q'$.
Donc $(p+q)(p+q+1)- (p'+q')(p'+q'+1) = 2 (q' -q)$.
Je ne vois pas comment continuer. J'ai essayé de raisonner modulo 2, de développer, j'ai testé différentes méthodes, je ne trouve pas l'idée.

Soc

Dire que c'est dénombrable revient à dire qu'il existe une bijection avec N. Démontrer qu'elle existe et en donner une explicite, ce n'est pas la même question.

Foys

La fable suivante sur le dénombrable est amusante: vous vivez dans un pays magique où il y a un nombre infini '"dénombrable" de banques, numérotées: banque n°1, banque n°2, banque n°3, ... Après avoir accompli une tâche dangereuse et très pénible vous vous voyez décerner un chèque de 100 000 zeuros avec la mention "il y a une banque dans laquelle ce chèque est encaissable".

Donc vous allez à voir la banque n°1 mais on vous dit "Ah non Monsieur/Madame, nous ne faisons pas ça". Puis la banque n°2: "non, mais allez voir une autre banque". Banque n°3 "On ne fait pas ce genre d'offre mais d'autres banques pourront vous aider". Au bout d'un moment, après vous être fait rejeter de la banque n° 133172 , vous finissez par vous dire que peut-être il y avait un enfumage.

Comment vous prouvez l'arnaque ?

JLapin

On va deux fois plus vite à chaque fois pour aller d'une banque à l'autre car on n'a pas que ça à faire et si on a mis 5 minutes pour aller de la première à la deuxième, on est fixé sur l'arnaque en 10 minutes.

OShine

Je n'ai pas trop compris l'arnaque.

lourrran

L'idée, elle est donnée dans le dessin initial.
Tu cherches à résoudre une équation avec 2 inconnues (p' et q'). Une équation, 2 inconnues, ça commence mal. Tu as quelques informations complémentaires , c'est que p' et q' doivent être des entiers, pas facile à exploiter. Et que p' et q' doivent être positifs ou nuls, pas facile à exploiter non plus. Il n'y a aucun outil classique qui permet de résoudre une équation quand on a ces contraintes.

Par exemple, pour f(p,q)=9, en se limitant aux solutions entières, on a 2 solutions évidentes pour (p',q') : (0,3) et (5,-1). Et c'est le 2ème critère (entiers positifs) qui permet d'éliminer la 2ème solution.
En vrai, on a une infinité de solutions si on n'a pas cette contrainte p et q positifs, on a une solution sur chaque diagonale descendante. Aucun espoir de solutionner ça avec tes équations.

Soit n=f(p,q)=f(p',q')
Quel est le plus grand nombre triangulaire inférieur à n ?  Soit t ce nombre. t est de la forme k(k+1)/2
On a donc p+q=p'+q'=k
et q=q'=n-t.

Alexique

OS : C'est surtout l'explication d' @Alexique qui m'a permis de comprendre, il a vraiment très bien expliqué.

Quel compliment, je suis flatté !    Je suis donc l'ahuri le plus pédagogue sur ce coup on dirait, rentrez chez vous les autres, y a rien à voir  
Moi qui ne suis plus prof depuis 4 ans maintenant, avec l'augmentation du point d'indice et des salaires des stagiaires, tu me donnes presque envie de rempiler (spoiler : FAUX).

OShine

Je ne comprends plus à partir du moment où tu parles de nombres triangulaires.

Quand on écrit $f(p,q)=f(p',q')$ je ne comprends pas le lien avec les nombres triangulaires inférieurs à $f(p,q)$ et comment on montre l'injectivité. 

lourrran

L'injectivité, elle est prouvée par le dessin.
Soit n=f(p,q) 
On cherche un 'éventuel' autre couple (p',q'), tel que f(p',q')=n
Connaissant n, on sait sur quelle diagonale descendante est le point (p',q'), et on sait quel point de cette diagonale est le point (p',q'). Et donc, il y a un seul point (p',q') qui convient.

Foys

@OShine: es-tu d'accord avec la phrase suivante? "trouver une bijection de $\N$ vers $\N^2$ revient à trouver une bijection de $\N^2$ vers $\N$"

(NB: bon j'avoue mon message d'avant est une authentique digression HS pour malmener un peu cette idée de "dénombrable intuitif"; je ferai un post dédié ailleurs -encore une promesse- pour ne pas embarasser un peu plus le pauvre OShine).

OShine

@Foys oui car si $f$ est bijective alors $f^{-1}$ aussi.

Oui c'est vrai l'injectivité et même la bijectivité est évidente sur le dessin, chaque couple $(p,q)$ est associé à un unique nombre. Mais voici une preuve en fait j'utilisais la mauvaise expression.

On a $f(p,q)=f(k,0)+q$ et $k=p+q$. 

Si $f(p,q)=f(p',q')$ alors forcément on est sur la même diagonale ainsi $k=p'+q'$.

Donc $f(k,0) + q = f(k,0)+q'$ donc $q=q'$ et finalement $p=p'$. 

Martial

@lourran : "Tu dis que tu es le seul à faire des maths du supérieur parmi tes collègues.
Soit.

Mais je pense (j'espère) que tes collègues n'ont aucune difficulté à faire cet exercice. Sans avoir à consulter le corrigé."

Rien n'est moins sûr. J'ai passé une année en collège (86/87 ça date) et la plupart de mes collègues refusaient ne serait-ce que de regarder un exercice de seconde.

OShine

@Martial c'est triste  Surtout qu'un prof de collège peut être amené à enseigner au lycée un jour.