Bijection de N dans N²
Répondre à la discussion
Affichage des résultats 1 à 16 sur 16

Bijection de N dans N²



  1. #1
    ssjb007

    Bijection de N dans N²


    ------

    Yo les kheys je veux construire la bijection de N dans N², donc j'utilise le principe de cantor ou je numérote les éléments des diagonales descendantes mais j'ai du mal à mettre en page tout ça.
    J'ai l'idée mais la rédaction me manque.
    Faut il que je trouve une formule explicite de cette application puis vérifier l'injectivité et la surjectivité ?
    J'ai du mal à démarrer

    -----

  2. #2
    Médiat

    Re : Bijection de N dans N²

    Citation Envoyé par ssjb007 Voir le message
    Yo les kheys
    ?????????????????
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  3. #3
    JB2017

    Re : Bijection de N dans N²

    Bonjour
    Une formule explicite c'est mieux:
    réalise une bijection de vers
    Dernière modification par JB2017 ; 21/11/2018 à 09h03.

  4. #4
    Seirios

    Re : Bijection de N dans N²

    Avoir quelque chose d'explicite c'est effectivement mieux, mais si on comprend simplement ce qui se passe, c'est encore mieux ! Une construction possible est la suivante :

    Numérotons les nombres premiers , et pour tout et , notons la puissance de dans la décomposition de en produit de nombres premiers (autrement dit, est la valuation -adique de ). On peut alors considérer l'application

    Je triche un peu, c'est une bijection , mais on peut bricoler ce qu'on veut à partir de là.

    L'idée de la construction vient du fait que peut être naturellement identifié avec l'ensemble des suites à support fini à valeurs dans . C'est une conséquence de l'unicité de la décomposition en produits de nombres premiers (dit formellement, est semi-groupe librement engendré par les nombres premiers). Autrement dit, comparer et revient à comparer et . Moralement, on est en train de doubler les coordonnées. L'application

    fait cette identification naturellement. En mettant tout ça ensemble, on obtient la bijection mentionnée tout au début.
    If your method does not solve the problem, change the problem.

  5. A voir en vidéo sur Futura
  6. #5
    Seirios

    Re : Bijection de N dans N²

    Citation Envoyé par ssjb007 Voir le message
    j'utilise le principe de cantor ou je numérote les éléments des diagonales descendantes mais j'ai du mal à mettre en page tout ça.
    Pourrais-tu décrire plus précisément ce que tu as en tête ? Parler de Cantor et de diagonales me fait penser à l'argument diagonal de Cantor permettant de montrer que l'ensemble des réels est indénombrable, mais pour le coup ça n'a rien à voir...
    If your method does not solve the problem, change the problem.

  7. #6
    gg0
    Animateur Mathématiques

    Re : Bijection de N dans N²

    Seirios,

    l'idée classique est de numéroter à la suite les (a,b) avec a+b=n; je suppose que c'est ce que veut dire Ssjb007 avec ses "diagonales descendantes". Ensuite, on fait croître n, pour avoir tous les couples.

    Cordialement.
    Dernière modification par gg0 ; 21/11/2018 à 12h09.

  8. #7
    gg0
    Animateur Mathématiques

    Re : Bijection de N dans N²

    Ssjb007,

    si tu veux aller plus loin dans ton idée, il faut que tu nous dises ce que tu as fait (combien de nombres dans chaque "diagonale" ? pour un couple (a,b), dans quelle diagonale est-il et à quelle place ? ...).

    Cordialement.

  9. #8
    Médiat

    Re : Bijection de N dans N²

    Bonjour

    Citation Envoyé par Seirios Voir le message
    Parler de Cantor
    La formule donnée au message 3 est le "polynôme de Cantor", c'est d'ailleurs la seule solution polynomiale de degré 2 (aux symétries près)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  10. #9
    Resartus

    Re : Bijection de N dans N²

    Bonjour,
    @Seiros : il a été démontré que le polynome de Cantor est le seul possible (à la permutation près des deux variables) pour une bijection. La démonstration était apparemment très compliquée, mais elle implique que ton approche par les facteurs premiers aura tôt ou tard des trous dans le recouvrement

    Bien sûr, si on renonce à une formule explicite, il y aura des infinités d'autre solutions...

    Et la formule qu'a indiquée JB2017 est la mathématisation de la "diagonale" de Cantor : l'intervalle entre les deux produits n(n+1)/2 et (n+1)(n+2)/2 est exactement égal à n+1, ce qui laisse tout juste la place pour caser sans trou toutes les possibilités p+q=n (p variant entre 0 et n)
    Dernière modification par Resartus ; 21/11/2018 à 12h40.
    Why, sometimes I've believed as many as six impossible things before breakfast

  11. #10
    Médiat

    Re : Bijection de N dans N²

    Citation Envoyé par Médiat Voir le message
    c'est d'ailleurs la seule solution polynomiale de degré 2
    et on sait qu'il n'en existe pas de degré 3 ou 4
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  12. #11
    JB2017

    Re : Bijection de N dans N²

    Bonjour
    J'avais pas vu la réponse de Resartus mais je donne la mienne même si c'est redondant
    Rebonjour
    Je ne vois pas en quoi la grosse artillerie pour tuer une mouche permet de comprendre ce qu'il se passe. (du moins c'est mon point de vue)
    La bijection de Nx N avec N vient simplement du fait qu'on peut numéroter par les entiers naturels.
    Pour voir ce qu'il se passe on a que faire des nombres premiers et tutti quanti.
    Pour voir (au sens le plus concret du terme) ce qu'il se passe il suffit de prendre un cahier d'écolier et représenter les NxN par des points. Ensuite je les numérote en suivant les "droites" d'équation p+q=s, s=0,1,....,
    q=0,....,s. (C'est la remarque de GG0)
    Ce qui donne la formule que j'ai donnée.
    Dernière modification par JB2017 ; 21/11/2018 à 12h43.

  13. #12
    Resartus

    Re : Bijection de N dans N²

    Re,
    Mes souvenirs m'ont trahi : Wikipédia donne l'historique de la démonstration https://en.wikipedia.org/wiki/Fueter–Pólya_theorem
    et apparemment, l'unicité n'est démontrée que pour des polynômes.
    Donc la méthode de seiros doit pouvoir donner d'autres solutions non polynomiales (mais je n'ai pas le courage de le vérifier)
    Why, sometimes I've believed as many as six impossible things before breakfast

  14. #13
    Médiat

    Re : Bijection de N dans N²

    Citation Envoyé par Resartus Voir le message
    l'unicité n'est démontrée que pour des polynômes.
    de degré 2 (1923), 3 ou 4 (2001), au dessus, on ne sait pas
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  15. #14
    Seirios

    Re : Bijection de N dans N²

    Citation Envoyé par JB2017 Voir le message
    Je ne vois pas en quoi la grosse artillerie pour tuer une mouche permet de comprendre ce qu'il se passe. (du moins c'est mon point de vue)
    Il n'y a aucune grosse artillerie. Dans la deuxième partie de mon message, j'explique pourquoi l'application est naturelle, mais sinon tout est élémentaire. Je reprends mon application
    L'application est un invariant à gauche, d'où l'injectivité. Ensuite, si et , alors , d'où la surjectivité.

    Ce qui m'a gêné dans ton message c'est que tu parachutes une formule. Je n'avais pas fait attention à l'interprétation qu'il y a derrière. Du coup, effectivement, c'est une formule tout ce qu'il y a de plus naturelle. Par contre, vérifier formellement qu'elle fonctionne (je veux dire, d'une autre manière que simplement dire "ça se voit par construction") doit quand même demander quelques lignes.
    If your method does not solve the problem, change the problem.

  16. #15
    Médiat

    Re : Bijection de N dans N²

    Citation Envoyé par Seirios Voir le message
    Par contre, vérifier formellement qu'elle fonctionne (je veux dire, d'une autre manière que simplement dire "ça se voit par construction") doit quand même demander quelques lignes.
    Le passage de "ça se voit par construction" au formel n'est pas si compliqué (peu de lignes)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  17. #16
    JB2017

    Re : Bijection de N dans N²

    Rebonjour
    Serios oui peut être que c'est la façon dont tu avais présenté ta solution qui m'avait fait penser que c'était un peu compliqué.
    Effectivement je suis d'accord avec toi que ta fonction \phi est évidemment bijective.

Discussions similaires

  1. Bijection de R² dans R²
    Par invitedd2267e2 dans le forum Mathématiques du supérieur
    Réponses: 19
    Dernier message: 03/02/2013, 13h24
  2. bijection de [0;1] dans ]0;1[
    Par Slim Shady dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 19/07/2012, 19h29
  3. bijection de IR^n dans IR
    Par invited37a86e7 dans le forum Mathématiques du supérieur
    Réponses: 25
    Dernier message: 07/03/2010, 06h06
  4. bijection de [0;1[ dans R
    Par invitea67e7256 dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 09/02/2010, 18h40
  5. Bijection dans C
    Par invite6fbd5e88 dans le forum Mathématiques du collège et du lycée
    Réponses: 1
    Dernier message: 29/01/2009, 17h25