Répondre à la discussion
Affichage des résultats 1 à 22 sur 22

Un petit jeu autour de la récurrence



  1. #1
    Médiat

    Un petit jeu autour de la récurrence


    ------

    Un petit jeu autour de la récurrence () :

    Soit p(n) la propriété qui dit qu'il existe un nombre entier m strictement positif divisible par tous les nombres entiers inférieurs ou égaux à n.

    Essayons de démontrer par récurrence que p est vrai pour tous les nombres entiers :

    p(0) est trivialement vrai, il suffit de prendre m = 1.
    Pour montrer que p(n) ==> p(n+1), il suffit de remarquer que si m est un nombre entier qui vérifie la condition pour n, alors m(n+1) vérifie la condition pour n+1.

    La démonstration par récurrence ci-dessus permet donc d'affirmer que p est vrai pour tout n , c'est à dire qu'il existe un nombre entier strictement positif divisible pour tout n, c'est à dire divisible par tous les nombres entiers, ce qui est manifestement faux.

    A votre avis que s'est-il passé :

    1) Cette démonstration invalide-t-elle le raisonnement par récurrence ?
    2) Cette démonstration utilise-t-elle le raisonnement par récurrence dans un contexte où celui-ci ne s'applique pas ?
    3) La démonstration est-elle fautive ?
    4) La démonstration est correcte, mais ce qui est faux c'est d'avoir ajouté "ce qui est manifestement faux"
    5) Autre ? A préciser.

    Merci de répondre avec justification et sous spoiler pour ne pas gâcher le plaisir de ceux qui voudraient chercher.

    -----
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  2. #2
    martini_bird

    Re : Un petit jeu autour de la récurrence

    Salut,

     Cliquez pour afficher


    Cordialement.
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  3. #3
    blable

    Re : Un petit jeu autour de la récurrence

    Salut,

    je commence juste à regarder mais pour moi déjà
     Cliquez pour afficher

  4. #4
    blable

    Re : Un petit jeu autour de la récurrence

     Cliquez pour afficher

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

    Re : Un petit jeu autour de la récurrence

    @martini_bird : sans surprise, évidemment

    @blable : ta première remarque
     Cliquez pour afficher

    @blable : ta deuxième remarque
     Cliquez pour afficher
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  7. #6
    invite986312212
    Invité

    Re : Un petit jeu autour de la récurrence

    salut,

    tu aurais aussi bien pu prendre pour p la propriété p(n) = "il existe un nombre plus petit que n". Elle est vraie pour tout n mais il n'existe pas de nombre plus grand que tous les autres.

  8. #7
    blable

    Re : Un petit jeu autour de la récurrence

    REe Mediat,
     Cliquez pour afficher

  9. #8
    Médiat

    Re : Un petit jeu autour de la récurrence

    @blable
     Cliquez pour afficher
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  10. #9
    God's Breath

    Re : Un petit jeu autour de la récurrence

     Cliquez pour afficher
    Et Dieu, dans sa colère, pour punir les humains, envoya sur la Terre les mathématiciens.

  11. #10
    Médiat

    Re : Un petit jeu autour de la récurrence

    @God's Breath : tout autant sans surprise, évidemment.

    J'expliquerai, sans doute demain, pourquoi j'ai posté ce petit jeu (en plus de me dire que certains peuvent y apprendre quelques petites choses (se méfier de ce qu'on lit, par exemple, même si c'est sous forme "scientifique", ou pour illustrer ta signature )).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  12. #11
    God's Breath

    Re : Un petit jeu autour de la récurrence

    @ Médiat,

    Je me tortures suffisamment les neurones en me méfiant de ce que je lis chez mes étudiants, qui peut se trouver être
    – exact sous des apparences d'exactitude (parfois la pire des situations...) ;
    – erroné sous des apparences d'exactitude ;
    – exact sous des apparences d'erreur ;
    – erroné sous des apparences d'erreur.

    Je suis rompu à ce genre d'exercice.

    Personnellement, je préfère, comme blable, initialiser à 1... Dans p(0), j'ai un problème pour dire que m=1 est un entier strictement positif divisible par 0, lequel est bien un nombre entier inférieur ou égal à 0.
    Et Dieu, dans sa colère, pour punir les humains, envoya sur la Terre les mathématiciens.

  13. #12
    NicoEnac

    Re : Un petit jeu autour de la récurrence

    Bonjour,

    Je ne vois pas l'intérêt de prouver cela par récurrence (même si c'est l'énoncé du post ). Prendre m = n! ne marche pas tout le temps ?
    "Quand les gens sont de mon avis, il me semble que je dois avoir tort."O.Wilde

  14. #13
    Médiat

    Re : Un petit jeu autour de la récurrence

    Citation Envoyé par God's Breath Voir le message
    Je me tortures suffisamment les neurones en me méfiant de ce que je lis chez mes étudiants, qui peut se trouver être
    – exact sous des apparences d'exactitude (parfois la pire des situations...) ;
    – erroné sous des apparences d'exactitude ;
    – exact sous des apparences d'erreur ;
    – erroné sous des apparences d'erreur.
    Tu connais certainement l'histoire qui faisait florès de mon temps (Salut Gwyddon, tu vois je suis ton conseil ):

    Un étudiant remet un document de quelques pages à son directeur pour annoncer un résultat dans sa thèse de maths pures
    Au bout d'une minute de lecture le professeur dit "Mais c'est trivial comme résultat", il reprend sa lecture et une minute plus tard dit "Et en plus c'est faux", il reprend encore sa lecture et une minute plus tard annonce "Et de toute façon je l'ai déjà publié il y a 6 ans".


    Citation Envoyé par God's Breath Voir le message
    Personnellement, je préfère, comme blable, initialiser à 1... Dans p(0), j'ai un problème pour dire que m=1 est un entier strictement positif divisible par 0, lequel est bien un nombre entier inférieur ou égal à 0.
    Tu as parfaitement raison, au départ je voulais tendre un autre piège (trouver un nombre divisible par tous les nombres entiers naturels strictement plus petit que 0), que j'ai abandonné et je n'ai pas assez relu.


    Citation Envoyé par NicoEnac
    Je ne vois pas l'intérêt de prouver cela par récurrence (même si c'est l'énoncé du post ). Prendre m = n! ne marche pas tout le temps ?
    L'intérêt réside dans la discussion à propos de la récurrence, sinon, n! fonctionne tout le temps, pas de problème.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  15. #14
    taladris

    Re : Un petit jeu autour de la récurrence

     Cliquez pour afficher

  16. #15
    NicoEnac

    Re : Un petit jeu autour de la récurrence

    Citation Envoyé par Médiat Voir le message
    L'intérêt réside dans la discussion à propos de la récurrence, sinon, n! fonctionne tout le temps, pas de problème.
    D'accord ! La discussion ne porte pas sur la preuve mais sur le moyen de prouver. J'ai compris
    "Quand les gens sont de mon avis, il me semble que je dois avoir tort."O.Wilde

  17. #16
    Médiat

    Re : Un petit jeu autour de la récurrence

    @taladris : Oui ! D'ici demain soir j'en dirai un peu plus ...
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  18. #17
    God's Breath

    Re : Un petit jeu autour de la récurrence

    Citation Envoyé par Médiat Voir le message
    @taladris : Oui ! D'ici demain soir j'en dirai un peu plus ...
     Cliquez pour afficher
    Et Dieu, dans sa colère, pour punir les humains, envoya sur la Terre les mathématiciens.

  19. #18
    Médiat

    Re : Un petit jeu autour de la récurrence

    @God's Breath : Bien sur, (aurais-tu lu un excellent document sur l'arithmétique récemment , pas d'offense, je me doute que tu le savais avant)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  20. #19
    God's Breath

    Re : Un petit jeu autour de la récurrence

    @Médiat,


    Malgré ma très mauvaise volonté sur certains points, malgré mon esprit borné et provocateur... je me tiens informé des développements récents des mathématiques, et je les étudie de près.
    Et Dieu, dans sa colère, pour punir les humains, envoya sur la Terre les mathématiciens.

  21. #20
    Médiat

    Re : Un petit jeu autour de la récurrence

    D'abord, comme l'a exprimé martini_bird l'erreur est dans l'interprétation de la formule, plus précisément, en l'écrivant en français, j'ai pu échanger l'ordre des quantificateurs sans que cela se voit trop.
    En écrivant les choses de façon formelle, le truc apparaît immédiatement :
    God's Breath, dans son message # 9 donne l'explication formelle, je ne vais pas la redonner à l'identique, pour ne pas faire de doublon, et ouvrir d'autres portes ; God's Breath a écrit des formules valides dans IN (ce qui est un choix légitime à la vue de l'exercice), je vais me placer dans la théorie axiomatique de Peano (noté PA par la suite) dont le langage (égalitaire) est (0, s, +, .), où s est la fonction successeur.

    Avec cette définition, p(0) est bien vérifiée.
    la formule démontrée par la récurrence est donc
    alors que la phrase "il existe un nombre entier strictement positif divisible par tous les nombres entiers" s'écrit (à condition de comprendre "nombre entier" par "élément d'un modèle de PA") :


    Un petit mot pour expliquer pourquoi j'ai présenté ce petit piège :

    J'ai trouvé la relation p(n) dans un livre ("Prédicative arithmetic" de Edward Nelson paru en 1986 aux Presses Universitaires de Princeton) qui présente la conclusion, sans la trahir comme je l'ai fait, comme une bonne raison de ne pas avoir une confiance aveugle en la récurrence (the reason for mistrusting the induction principle ...).
    J'ai trouvé cela d'autant plus bizarre que l'argument utilisé est que n étant donné, il n'est pas possible de borner m (peut-être voulait-il dire borné par un polynome en n ?), alors que manifestement n! est une excellente borne (du coup j'ai quelques doutes soit sur mon anglais, soit sur ce livre).

    Pour prolonger le jeu, je rappelle que l'arithmétique de Peano n'est pas contradictoire avec l'existence d'un élément divisible par tous les nombres entiers "naïfs" (entiers du modèle standard).

    La suite est réservée aux lecteurs du document sur l'arithmétique que j'ai commis, et bien sur aux connaisseur d'un peu de logique du premier ordre (théorème de compacité, par exemple), sinon la première formule ci-dessous risque de poser des problèmes...
    Soit PA la théorie axiomatique de Peano.

    Soit et soit

    Toute partie finie de T peut s'étendre en pour un certain n (le plus grand de la partie finie) ; T' est clairement consistante x =n! étant un bon exemple pour x.

    Par compacité on en déduit que T est consistante.

    Or la théorie T dit clairement qu'il existe un nombre entiers (élément d'un modèle de PA) non nul divisible par tous les nombres entiers du modèle standard, et comme ce nombre entier ne peut appartenir au modèle standard (aucun nombre entier n n'est divisible par (n + 1)), ce qui montre l'existence (Merci, le théorème de complétude de Gödel) de modèle non-standard de l'arithmétique (sous réserve de la consistance de PA).

    Evidemment ce n'est pas le seul moyen (cf. le message # 6 de ambrosio) de montrer l'existence de modèle non-standard, mais l'occasion m'a fait larron.

    J'espère ne pas avoir fait trop de fautes de frappe .
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  22. #21
    invite986312212
    Invité

    Re : Un petit jeu autour de la récurrence

    la logique dans les mathématiques c'est comme le sel dans la soupe: trop peu c'est pas bon et trop c'est pas bon non plus (Médiat te vexe pas ... )

    à propos de récurrence, peut-être une âme charitable va-t-elle m'expliquer un point subtil qui me tracasse depuis que j'ai lu le livre d'Yves Hellegouarch qui doit s'intitule "mathématiques de Fermat-Wiles" (je nel'ai pas sous les yeux). En préambule Hellegouarch explique la méthode de descente de Fermat et dit qu'elle ressemble superficiellement à une sorte de contraposée de la démonstration par récurrence, mais qu'en fait elle en diffère substantiellement (ce qui ne me semble pas évident). Là dessus il donne un exemple qui ne m'éclaire pas vraiment. Qu'en pensez-vous?

  23. #22
    Médiat

    Re : Un petit jeu autour de la récurrence

    Citation Envoyé par ambrosio Voir le message
    la logique dans les mathématiques c'est comme le sel dans la soupe: trop peu c'est pas bon et trop c'est pas bon non plus (Médiat te vexe pas ... )
    Je ne suis pas vexé, paludier est un beau métier avec un beau nom, et il en faut pour saler la soupe des autres, je trouve cela mieux que d'être un simple consommateur .
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

Discussions similaires

  1. Petit jeu mathématique
    Par Azrem dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 24/07/2014, 09h41
  2. Un petit jeu politique
    Par humanino dans le forum Science ludique : la science en s'amusant
    Réponses: 12
    Dernier message: 23/07/2008, 18h56
  3. petit problème d'utilisation de la récurrence...
    Par anais22330 dans le forum Mathématiques du supérieur
    Réponses: 8
    Dernier message: 27/12/2006, 16h13
  4. Petit jeu sympa
    Par Mamie dans le forum Science ludique : la science en s'amusant
    Réponses: 5
    Dernier message: 24/02/2005, 19h39