Un petit jeu autour de la récurrence

[Médiat]

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.
-----

[martini_bird]

Salut,

 Cliquez pour afficher

La démonstration par récurrence ci-dessus permet donc d'affirmer que p est vrai pour tout n ,

Oui.

c'est à dire qu'il existe un nombre entier strictement positif divisible pour tout n,

Non.

Cordialement.

[invitead1578fb]

Salut,

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

 Cliquez pour afficher

P(0) n'est pas trivialement vraie... 1 divisible par 0 , il vaudrait pas mieux initialiser à 1?

[invitead1578fb]

 Cliquez pour afficher

Pour moi c'est le manifestement faux qui est faux ... cf m! divisible par tout entier inférieur à n si m plus grand, mais comme dans la démo tu utilises je peux même dire que n! est manifestement divisible par tout entier inférieur ou égal à n

[A voir en vidéo sur Futura]

[Médiat]

@martini_bird : sans surprise, évidemment

@blable : ta première remarque

 Cliquez pour afficher

Ce n'est pas correct, mais c'était aussi clairement un piège, je détailelrai un peu plus tard.

@blable : ta deuxième remarque

 Cliquez pour afficher

Et non, ce n'est pas cela non plus

[invite986312212]

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.

[invitead1578fb]

REe Mediat,

 Cliquez pour afficher

cependant ta démonstration utilise bien le fait que m>n en fait tu n'as même pas utilisé la récurrence dans le sens où c'est plutôt une méthode constructive du nombre que tu cherches, ta démonstration dérape donc pour moi au moment où tu passes à l'infini le , mais bon n'y connaissant pas grand chose en topo j'arrive pas à le mettre en forme; en tout cas il me semble que la récurrence n'est là que pour cacher ce passage rapide à l'infini...

[Médiat]

@blable

 Cliquez pour afficher

cependant ta démonstration utilise bien le fait que m>n en fait tu n'as même pas utilisé la récurrence

Si, si, j'utilise bien la récurrence (même si elle n'est pas obligatoire), puisque je montre p(0) et (p(n) ==> p(n+1)).

ta démonstration dérape donc pour moi au moment où tu passes à l'infini

Si tu veux dire que la conclusion à partir de [p(0) et (p(n) ==> p(n+1))] que p(n) est vraie pour tous les n, cette partie de la démonstration est correcte.

en tout cas il me semble que la récurrence n'est là que pour cacher ce passage rapide à l'infini...

Le truc est ailleurs

[God's Breath]

 Cliquez pour afficher

On a bien montré, par récurrence, que



mais pas que



C'est un problème de «non uniformité» de la propriété...

[Médiat]

@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 )).

[God's Breath]

@ 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.

[NicoEnac]

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 ?

[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.

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".

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.

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.

[taladris]

 Cliquez pour afficher

Réponse 5: la récurrence est valide, c'est sa conclusion qui est abusive: l'entier m dépend de n (plus précisément, l'ensemble des entiers m qui conviennent dans la proposition p(n) dépend de n). Et il n'en existe aucun qui marche pour tous les entiers n.

[NicoEnac]

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

[Médiat]

@taladris : Oui ! D'ici demain soir j'en dirai un peu plus ...

[God's Breath]

@taladris : Oui ! D'ici demain soir j'en dirai un peu plus ...

 Cliquez pour afficher

Voudrais-tu en venir à l'existence de modèles non standard en obtenant l'interversion des quantificateurs par compacité ?

[Médiat]

@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)

[God's Breath]

@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.

[Médiat]

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 .

[invite986312212]

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?

[Médiat]

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 .