Discussion:Raisonnement par récurrence

Discussion de 2007

Pourquoi lorsque vous voulez démontrer que, pour n>ou=3, 3^2n -2^n-3 est un multiple de 7 vous passez à 3^2n+2 -2^n-2 ?

On essaie d'être clair mais semble-t-il insuffisamment. Pour démontrer la propriété précédente en utilisant le principe de récurrence, il faut démontrer que la propriété est vraie pour la première valeur de n (c'est à dire n = 3) et ensuite qu'elle est héréditaire c'est à dire qu'elle se transmet d'un entier n quelconque à l'entier suivant n + 1, d'où l'idée de la supposer vraie pour un entier n - donc de supposer que $3^{2n}-2^{n-3}$ est multiple de 7 - et de s'en servir pour démontrer qu'alors $3^{2(n+1)}-2^{(n+1)-3}$ est multiple de 7 (écriture de la propriété pour l'entier suivant ) . HB 21 septembre 2006 à 19:36 (CEST)

merci pour cette explication je comprends mieux !!!

Je me suis permis une petite correction : il y avait une coquille à la fin, à la dernière ligne de votre démonstration : On a n+1=dd' et non n=dd' comme on lisait initialement, Bien à vous, Guillaume.

Merci d'avoir repéré et corrigé l'erreur. HB 9 janvier 2007 à 20:05 (CET)

Non standard

Je propose d'effacer la passage sur l'analyse non standard, qui est à peu près un contresens sur le sujet (un modèle non-standard de l'arithmétique c'est un modèle qui justement satisfait en particulier la récurrence pour les propriétés exprimables dans le langage considéré). Ca ne semble pas nécessaire d'aborder ce sujet dans cet article. Proz 26 juin 2007 à 20:49 (CEST)

Pas d'opinion pour ma part car connaissances insuffisantes en analyses non-standart mais si c'est faux, il faut évidemment le supprimer. HB 27 juin 2007 à 11:26 (CEST)

Le passage sur l'analyse non standard est tres mal tournee. Si P est un predicat non standard, alors le principe de recurrence ne peut pas s'appliquer. Exemple : P(n)="n est un ensemble standard". Si P(n) est vrai, alors P(n+1) est aussi vrai. Mais comme N est un ensemble infini, il existe un entier non standard. La raison est que l'ensemble des entiers verifiant P n'est pas dans ce cas un ensemble stabdard et n'est donc pas egal a N.

Par contre, si P est une formule standard, le principe de recurrence s'applique evidemment.

Je suis d'accord avec Proz : le passage merite d'etre retravaille !

Ekto - Plastor 27 juin 2007 à 14:23 (CEST)

Oui, ce n'est pas vraiment faux mathématiquement, mais ça n'est pas du tout une bonne présentation : contredire la récurrence c'est facile, il suffit d'ajouter des éléments, ce qui est utile c'est de la conserver pour des propriétés "standards". Plutôt que de retravailler, je propose d'effacer, il y a un passage sur les modèles non standards de l'arithmétique dans arithmétique de Peano, on n'est pas obligé de parler d'analyse non standard dans cet article dont j'ai l'impression qu'il doit plutôt être introductif. Proz 27 juin 2007 à 21:15 (CEST)

Démonstration du raisonnement par récurrence

Il faudrait écrire la démonstration du raisoonement par récurrence. On a parle trop peu souvent, c'est beau de parler de réccurence mais il faudrait l'expliquer d'où sa démonstration. Sinon l'ensemble est bien.

Oui, cela manque. Avant les améliorations de Proz, figuraient dans l'article ce que vous appelez "démonstration". En réalité, le théorème de récurrence est un axiome équivalent à deux autres (axiome de Péano et principe de Fermat). Ce qui explique qu'il peut se démontrer à partir de l'un des deux autres. J'attendais que Proz finisse l'article avant de faire des remarques mais comme il n'est pas intervenu sur celui-ci depuis 10 jours, je tiens à signaler que les équivalences avec le cinquième axiome de Péano ou le principe de Fermat se doivent de figurer dans l'article. HB 11 juillet 2007 à 10:12 (CEST)

Il manque effectivement quelquechose, mais je n'aurai pas le temps ces jours-ci, désolé. Le raisonnement par récurrence se "démontre" en théorie des ensembles, c'est simplement la définition des entiers, c'est un axiome dans l'arithmétique de Peano, mais dans ce dernier cas il faut se poser la question du langage. Il m'a semblé qu'il était mieux de commencer par une approche informelle, implicitement en théorie des ensembles. Après relecture, peut-être est-ce trop informel, et il faudrait ajouter deux lignes en introduction pour que cela n'est pas l'air de sortir de nulle part (propriété des entiers, ou axiome sans détailler). Sinon en fait l'équivalence avec le principe de Fermat y est (décomposée en à passant par la récurrence forte). Pour le 5ième axiome de Peano s'il s'agit bien de remplacer les prédicats par des ensembles (je crois d'ailleurs que pour Peano c'était plus ou moins la même chose, ∈ c'est "est" pour lui), cela y est au début. Si ça ne se voit pas, c'est un défaut. Pour la partie axiomatisation je comptais ne pas trop en dire, poser la question du langage dans lequel on axiomatise, et renvoyer aux articles sur l'axiomatique de Peano et sur la construction des entiers. Proz 11 juillet 2007 à 11:03 (CEST)

Je ne vois pas l'intérêt d'écrire une démonstration du principe de récurrence, qui ne pourra s'appuyer que sur des axiomes plus compliqués, ceux de la théorie des ensembles, et finalement proférera une banalité : les entiers sont les éléments d'un ensemble qui vérifie le principe de récurrence. Il vaut mieux présenter le principe de récurrence comme un axiome, sans faire appel à la théorie des ensembles. C'est dans ce sens qu'il me paraissait intéressant de parler d'analyse non standard, puisqu'un axiome peut être admis ou rejeté. L'analyse non standard est précisément le cadre où il existe un prédicat primitif (être non standard) qui ne vérifie pas le principe de récurrence. Cela présentait l'intérêt de souligner le caractère non-évident du principe de récurrence, contrairement à ce qu'on lit trop souvent dans nombre de livres, dont celui cité dans l'article, qui considèrent ce principe comme allant de soi. Theon 11 juillet 2007 à 12:10 (CEST)

Le principe de récurrence tel qu'énoncé parle d'ensembles (ou de propriétés mathématiques "en général"), il fait donc de toute façon implicitement référence aux axiomes plus compliqués. L'intérêt dans la construction ensembliste des entiers c'est la clôture (ça se généralise), mais je suis d'accord que la démonstration est une banalité. Je suis d'accord sur le fait que le principe de récurrence ne va pas de soi, mais il repose sur l'intuition très forte que nous avons des entiers, et on peut s'appuyer dessus dans un article introductif. Parler de non standard ne me semble pas nécessaire dans cet article, j'ai peur qu'à ce niveau ça introduise de la confusion. Il n'y a aucune difficulté en soi à nier la récurrence en ajoutant des éléments aux entiers (cf. ci-dessus). En tout cas ce qui existait n'allait pas. Proz 11 juillet 2007 à 12:31 (CEST)

Je comprends bien votre avis à tous les deux, nous sommes donc devant un problème de niveau d'article. Il est vrai que, formellement,on peut prendre le principe de récurrence comme un axiome de N, mais épistémologiquement ce n'est pas une propriété évidente de N; d'autre part, une personne peut très bien connaitre le principe de récurrence sans connaitre l'analyse non standard. En mathématiques élémentaires le principe de récurrence se démontre en s'appuyant sur une des propriétés (admises) de N : tout ensemble non vide possède un plus petit élément. Cela ne nécessite pas l'artillerie lourde de la théorie des nombres et permet de justifier une propriété qui semble complexe à l'aide d'une propriété dont tout jeune "voit l'évidence". Je ressens personnellement l'absence de cette démonstration comme un manque dans l'article et il me semble que je ne suis pas la seule. HB 12 juillet 2007 à 10:16 (CEST)

Ce qui me gêne dans le fait de vouloir "démontrer" le principe de récurrence par une propriété "évidente", celle par exemple que toute partie non vide possède un plus petit élément, c'est qu'on retombe dans la notion d'axiome antérieure au XIXème, à savoir un axiome était une propriété "évidente" qui ne nécessitait pas de démonstration. Or un axiome est une propriété non pas évidente, mais arbitraire. C'est donc tromper le lecteur sur la nature d'un axiome. A la rigueur, on peut démontrer l'équivalence entre principe de récurrence, existence du minimum d'une partie non vide ou principe de la descente infinie de Fermat, et souligner que ces propriétés (ou l'une d'elles) sont admises en tant qu'axiomes, c'est-à-dire relève d'un choix, mais non pas faire croire qu'il puisse exister une démonstration du principe de récurrence reposant sur une propriété "évidente". On tombe alors dans les travers de nombre de livres du secondaire ou même du supérieur, faisant croire qu'ils démontrent le principe de récurrence, alors qu'ils utilisent une propriété... qui se prouve à partir du principe de récurrence. Theon 13 juillet 2007 à 10:43 (CEST)

« A la rigueur, on peut démontrer l'équivalence entre principe de récurrence, existence du minimum d'une partie non vide ou principe de la descente infinie de Fermat, et souligner que ces propriétés (ou l'une d'elles) sont admises en tant qu'axiomes, c'est-à-dire relève d'un choix »

C'était le principe adopté dans la version du 13 juin où l'on précisait bien qu'on pouvait prendre le principe de récurrence comme un axiome ou le démontrer à partir d'axiomes équivalents (avec démonstration à la clé). Ce sont ces remarques (et leur démonstration) dont je regrette l'absence dans l'article actuel. HB 13 juillet 2007 à 13:49 (CEST)

L'important est de ne pas omettre l'approche historique. J'ai récupéré récemment quelques phrases de l'article anglophone. Il semble que le raisonnement par récurrence ait été utilisé pour la première fois pour démontrer la formule du binôme de Newton. Je pense sans exagération qu'alors la question du bien-fondé de ce raisonnement ne se posait pas, mais je n'ai pas de référence sérieuse. J'ai mis un lien vers le livre original de Maurolico qui est illisible. D'après ce que je comprends, il utilise une récurrence pour calculer les nombres pentagonaux, carrés, ... Mais j'ai l'impression qu'il se contente d'expliquer comment par récurrence obtenir le troisième nombre pantagonal, puis le quatrième, puis le cinquième, ... N'arrivant pas à lire le latin (c'est du latin ?), je ne sais pas s'il énonce réellement le principe de récurrence ou non. Je vais demander une traduction du texte en français pour vérifier.

On trouve dans le traité du triangle arithmétique de Pascal des formulations très proches de notre récurrence moderne, mais je crains qu'on ne trouve pas de formulation telle que nous la connaissons aujourd'hui avant le XIXème et Dedekind. En effet, jusqu'à cette époque, le raisonnement par récurrence consiste, sur des exemples numériques précis (2, 3, 4...) à expliquer comment on passe au cas suivant, sans jamais traiter véritablement le passage algèbrique de n à n+1. Les démonstrations les plus convaincantes (tels celles de Pascal), sont celles pour lesquelles le raisonnement au rang 2, 3, 4 n'est qu'un cas particulier du cas général que le lecteur moderne pourrait formaliser sans difficulté. Les démonstrations les moins convaincantes sont celles pour lesquels l'auteur se borne à vérifier la propriété aux rangs 2, 3, 4 et à dire qu'on peut continuer indéfiniment. Tel est le cas par exemple de la page 7 de Maurolico (c'est effectivement du latin), où il montre que la somme des impairs donne les carrés, et le vérifiant pour 4, 9, 16 et en disant qu'on peut continuer indéfiniment. Mais peut-être Maurolico est-il plus précis dans d'autres passages. Le lien qu'a donné Ektoplastor vers Maurolico est en tout cas très intéressant, et il faut le garder. Theon 14 juillet 2007 à 14:43 (CEST)

Pour revenir au débat ci-dessus, j'ai inséré une partie Principes équivalents où sont énoncés des principes équivalents au principe de récurrence. Il faut bien mentionner l'évolution historique des idées alors : à telle époque tel mathématicien a déduit le principe de récurrence de tel principe.

HB, peux-tu me donner une source expliquant comment le raisonnement de récurrence doit expliqué au ... collège ou lycée, je ne sais plus ? Cela peut compléter l'article. Sinon, je suis d'accord avec, on ne devrait pas se limiter à une présentation purement formelle où le raisonnement de récurrence est une propriété que doivent vérifier les entiers naturels. Même si au final, c'est bien de ça dont il s'agit.

Enfin, l'article a un manque sérieux : la définition d'une suite par récurrence. Par exemple, quel sens donné à aⁿ ou à n.a ou à $C_{n}^{k}$ ? Quelqu'un peut-il donner quelques mots à ce sujet ?

Conclusion : c'est vachement dur à tout présenter.

Ekto - Plastor 13 juillet 2007 à 14:27 (CEST)

C'est toujours important de se référer à des textes et non à des souvenirs que l'on a d'eux. Une enquête incomplète sur les programme de lycée m'a permis de découvrir qu'en 71, le raisonnement par récurrence est vu en terminale en arithmétique après avoir présenté l'ensemble des entiers naturels, Vissio le déduit du cinquième axiome de Péano, Revuz le démontre par la propriété de Fermat. En 1986, l'arithmétique a disparu des programmes et le raisonnement par récurrence est vu en première à l'occasion des suites donc comme une propriété intrinsèque. En 1991, la récurrence semble disparaitre en 1er et Terminale mais reste la notion de suite définie par récurrence sans que le sens de ce mot ne soit relié au principe de récurrence. Le raisonnement par récurrence passe ensuite en terminale en tronc commun alors que l'arithmétique n'est abordée qu'en spécialité et ce n'est que dans les accompagnements du programme de 2002 que l'on rappelle aux professeurs qui l'auraient éventuellement oublié que le principe de récurrence est équivalent à l'énoncé "toute ensemble non vide d'entiers positifs est minoré" ou à l'énoncé " toute suite décroissante d'entier positifs est constante à partir d'un certain rang" tout en précisant qu'il "ne faut pas entrainer les élèves dans ces subtilités ni leur faire établir l'équivalence". HB 13 juillet 2007 à 17:48 (CEST)

De quelle étude fais-tu référence ?

J'ai trouvé plusieur informations contradictoires sur l'apparition du raisonnement par récurrence. Selon certains, le raisonnement par récurrence aurait été défini par Dedekind ; selon d'autres, il serait déjà présent dans des travaux antérieurs dont ceux de Maurolico. Mais j'ai des doutes. J'attends donc une traduction du livre, pour vérifier.

C'est vrai que les programmes évoluent assez rapidement. Je me suis toujours demandé si les professeurs "respectaient" toujours ces évolutions. Mais il faudrait comparer avec l'enseignement des mathématiques dans d'autres pays francophones.

Cet article aurait besoin d'une meilleure organisation des idées. Ekto - Plastor 13 juillet 2007 à 19:01 (CEST)

• Pour moi la récurrence est quand même première, puisqu'elle est vraiment caractéristique des entiers. La descente infinie, le fait d'être bien ordonné, c'est équivalent modulo le fait que l'on sait que 0 est le seul élément qui n'est pas un successeur. Il me semble que l'on peut donner une intuition directe de la récurrence, qui pour moi est au moins aussi évidente que le principe de Fermat, mais bon ...

• Vis à vis de la version du 13 juin je n'ai enlevé aucune preuve des équivalents, mais les ai réécrite, et en ai ajouté une (celle de la récurrence forte). Apparemment pas de façon claire, ce dont je suis désolé. La version du 13 juin compliquait les choses en énonçant une propriété de récurrence à partir d'un rang arbitraire, alors que c'est une conséquence immédiate, et c'est même équivalent, au cas où l'on part de 0, chose que j'avais mise dans l'article et qui a disparu d'ailleurs. Du coup l'équivalence entre la récurrence "avec des ensembles" et celle "avec des propriétés", qui est une trivialité (à la limite du changement de notation en théorie naïve) prenait plusieurs lignes. L'équivalence avec le principe de Fermat se fait très facilement par "récurrence forte", donc là aussi j'ai préféré modifier.

• Le fait de savoir si l'on peut démontrer la récurrence à partir de principes plus évidents a fait l'objet de débats ardents vers 1900 (Poincaré, Russell, ...). La récurrence se démontre en théorie des ensembles, et c'est intéressant parce que on n'a pas besoin d'ajouter un axiome. Est-ce que l'on a pour autant déduit cette propriété d'axiomes plus simples, dit quelquechose de la nature des entiers ? Probablement pas. Je ne souscrirais tout de même pas au fait que les axiomes sont entièrement arbitraires, et que l'on doit éliminer tout recours à l'intuition, je ne crois pas que les mathématiciens fonctionnent comme ça, et un système axiomatique doit être cohérent, or on a en général aucun moyen de le savoir si ce n'est en se ramenant à un autre système "de même force" (th. d'incomplétude), dans lequel, ultimement, on aura confiance pour des raisons parmi lesquelles l'intuition doit bien jouer son rôle.

• suite définie par récurrence : c'est un autre principe, que l'on utilise souvent sans estimer que cela demande une démonstration. Ca se démontre en théorie des ensembles (en gros on peut montrer l'existence du graphe de la suite comme intersection de graphes de relation ayant la propriété ad hoc). C'est à mon avis l'objet d'un autre article.

• Historique : je signale les deux articles de Bussey et Cajori, en référence dans la version anglaise, (accessibles par Jstor). Il ya une discussion dans Bussey sur Maurolycus, il semble bien qu'il utilise, dans l'exemple cité par Theon sur la somme des impairs, la récurrence au sens moderne (le cas n -> n+1 est bien traité, Bussey donne une référence précise), à la différence qu'il n'y a pas d'axiome ou de principe invoqué (ça ce doit être Dedekind 1888, et Peano 1889). Pascal se réfère à Maurolycus. Il y a aussi un référence à Cauchy (gallica) dans la version allemande. J'ai l'impression qu'il faudrait citer les mathématiciens grecs, tout autant que les arabes, et que Maurolycus apporte vraiment un progrès. Enfin je ne sais pas d'où vient le mot "récurrence", Poincaré utilise "récurrence" mais aussi "induction". Proz 15 juillet 2007 à 18:58 (CEST)

• Aucun étudiant visant à faire des mathématiques n'a de difficulté à faire un raisonnement par récurrence correct. Soit. Cependant, je pense que l'introduction d'une nouvelle méthode de démonstration pose au moins la difficulté d'être acceptée par les mathématiciens. Il n'est pas impensable qu'une nouvelle méthode soit un jour donnée. Le plus difficile dans la présentation de l'histoire d'une science, c'est de ne pas réécrire l'histoire a posteriori.
• Pour les références historiques, il faudrait que je consulte les articles que tu as mentionnés.
• Suite par récurrence : d'accord avec ce que tu dis. Mais reconnais que c'est lié, historiquement, et du point de vue actuel ! Les deux ont été introduits à la même période et probablement par les mêmes personnes. Ekto - Plastor 15 juillet 2007 à 20:58 (CEST)

• Ben en math. on en invente assez souvent de nouvelles méthodes de démonstration, non ?
• histoire : j'avais juste commencé de regarder, je crois que ça évite d'attendre la traduction de Maurolycus (j'ai lu ça en dessous, il y a des candidats ?), mais il faudrait sûrement d'autres références.
• suite : c'est sûrement historiquement lié, je crois bien que c'est dans Dedekind et Peano (à vérifier), mais il ne faut pas laisser croire que l'existence d'une suite définie par récurrence sur les entiers est une conséquence directe du raisonnement par récurrence. Il y a un article relation de récurrence, qui est à retravailler, y compris le titre, mais me semble sur le sujet.

Le début de l'introduction actuelle ne me plait pas trop, elle me semble trop redondante avec la section récurrence simple, on ne peut pas faire plus léger ? Enfin il faudrait placer ailleurs le petit paragraphe actuellement final sur l'évidence de la récurrence (pourquoi ne pas avoir gardé le titre ?). Je n'arrive pas à croire que l'on ne justifie pas la récurrence dans le secondaire (justifier ne signifie pas démontrer). Proz 15 juillet 2007 à 22:27 (CEST)

Démonstration du raisonnement par récurrence : ça existe en effet

Il se trouve, comme le demande le requérant initial que l'on peut démontrer le raisonnement par récurrence (comme l’a dit Proz ). Car si c'est un schéma d'axiomes dans la théorie arithmétique, c'est un théorème de la théorie des ensembles (qui s'étend même à tous les ordinaux). J'ai donc initié une nouvelle section énonçant le principe général et esquissant sa démonstration (finalement assez simple si on connait un peu ZF).

Je suis un peu perdu dans le plan de l'article (j'ai un peu modifié le titres des sections) et j'ai mis mon ajout sous une section "récurrence sur les ordinaux". Je crois hors apport historique sur lequel bosse Ektoplastor (purée demander la traduction d'un bouquin en latin médieval sur le bistro, perso j'eus pas osé le faire en espérance; :-) mais si ça marche ...) qu'il faudrait un peu réorganiser les §§ afin que soit plus visible que ce principe est un axiome de AP et un thm de ZF.

Voilou, --Epsilon0 14 juillet 2007 à 21:04 (CEST)

Un paragraphe sur les ordinaux de von Neumann, ça me semble un changement d'orientation complet de l'article. Pour ce qui est de la récurrence, c'est juste une reformulation de la propriété de bon ordre, dans le cas des ordinaux. Franchement je ne crois pas que ça aide beaucoup, une référence à l'article sur les ordinaux ne suffirait-elle pas ? Sinon il faudrait le déplacer dans une autre partie de l'article. Proz 15 juillet 2007 à 18:57 (CEST)

Une généralisation du principe me semble au moins aussi pertinente que diverses formulations équivalentes. Que ce soit "juste une reformulation de la propriété de bon ordre" peut être, mais on ne va p.e pas supprimer cet article car c'est dit sous une autre forme ailleurs. Et si ça peut amener les lecteurs à voir ce que peut être la généralisation de la notion d'entier, ben ce peut être bien et c'est p.e. le but d'une encyclopédie d'inciter à construire du savoir nouveau. Avis des autres? --Epsilon0 15 juillet 2007 à 20:30 (CEST)

Oui pour quelques mots très courts sur les ordinaux.

Pour la "démonstration", je n'aime pas ce mot. Je crois que, en théorie des ensembles, l'ensemble des entiers naturels est construit dans un modèle comme le plus petit ensemble stable par une opération de succession. Donc, on "réaliserait" plutôt par construction le principe de récurrence. Il n'y a rien à démontrer !

Pour la traduction, je vais voir où on en est. Je vais consulter les articles qu'a cité Proz. En ce moment, je réfléchis à la réécriture de l'article géométrie ; j'imagine que la traduction complète du livre prendra un certain temps. L'article Raisonnement par récurrence est très instable. Ekto - Plastor 15 juillet 2007 à 20:49 (CEST)

Oui, la récurrence est effectivement donnée directement par la définition de l'ensemble des entiers. Pour les ordinaux, je voulais juste dire que si on le sait pour les bons ordres on le sait pour les ordinaux (pas besoin de connaître la représentation de von Neumann). Disons qu'actuellement ça fait une rupture de ton, pour les entiers la construction ensembliste n'est même pas donnée, là on part directement sur la définition formelle ... Proz 15 juillet 2007 à 23:22 (CEST)

Ordinaux

Le paragraphe sur les ordinaux me semble totalement déplacé dans cet article qui est d'un niveau relativement élémentaire. On peut à la rigueur faire une allusion avec un lien vers Nombre ordinal mais tout développement supplémentaire est hors de propos ici. Le présent article parle de la récurrence sur les entiers, et non de théorie des ensembles et encore moins d'ordinal, sujets abondamment traités par ailleurs. Ce paragraphe devrait donc être supprimé. Theon 19 juillet 2007 à 16:36 (CEST)

Je ne vois pas où dans l'article il est précisé qu'il ne faut se limiter qu'aux entiers. Je viens de constater par exemple (mais ce n'est pas un argument) que côté anglais il y a une petite section "Generalization" ici et sur le B.A. en allemand une phrase "Diese Art der Induktion kann auf Ordinalzahlen angewendet werden (Ordinalzahlen können unendlich und größer werden). In diesem Fall wird die Methode transfinite Induktion genannt. Sie ist wichtig in der Mengenlehre und der Topologie." Bon, je ne défends pas cette section et si vous (Proz, EktoPlastor et Theon) estimez qu'il faut la supprimer où la déplacer je ne m'y opposerai pas. --Epsilon0 19 juillet 2007 à 21:02 (CEST)

Personnellement je n'ai pas du tout d'objection à une section "Généralisation", que je préfèrerais également assez minimaliste et non formelle, avec des pointeurs sur d'autres articles. Proz 23 juillet 2007 à 19:00 (CEST)

Bon, j'avoue ne pas avoir de bonnes idées en terme de formulation qui puisse satisfaire les pertinentes remarques de Théon, Ekto et Proz et les exigeances du sujet.

Comme dit Ekto je pense que la "dem" est p.e. inutile, je ne l'avais mise que parce que j'avais l'impression qu'elle était demandée (cf la section d'avant). Maintenant si on la retire de la section est-ce que le reste satisfait tout le monde?

Ce n'est pas sûr car quitte à généraliser aux ordinaux autant aller sur les ensembles munis d'une relation de bon ordre (b.o.) en général, mais là il faudrait harmoniser avec la section qui parle des bons ordres. Mais perso une telle généralisation me semble inessentielle modulo le thm (sans AC pour ceux qui auraient des doutes) :tout ens muni d'une relation de b.o est isomorphe à un et un seul ordinal.

Aussi je suis tout à fait d'accord pour mettre essentiellement dans une section "généralisation" des liens vers d'autres articles, mais en l'état je ne vois pas où (sur quel article) une formule comme :

∀ α { On(α) ⇒ [ ∀ β ( β ∈ α ⇒ F(β) ) ⇒ F(α) ] } ⇒ ∀ γ { On(γ) ⇒ F(γ) }

est mentionnée (c'est pq j'ai parlé de déplacement).

Elle semble (pas pour moi) trop élevée pour cet article, mais elle est aussi trop particulière pour les articles (nbreux comme dit Théon) sur les ordinaux. Et qu'elle ne soit pas mentionnée me semblerait une perte pour l'encyclopédie. On fait un article à part comme sur :en "Transfinite induction", alors que pour moitié il reprend les sections "Transfinite induction", "Proof or reformulation of mathematical induction" et "Generalization" (au passage, voilà 3 sections un peu redondantes) de l'article "Mathematical induction" ?

Bref, nous sommes face à un pb d'organisation du savoir sachant que wp est organisée en articles et non de manière thématique (format manuel). Ce qui m'a paru le plus judicieux était de faire cette section ici. Maintenant, lors que pr bcp de bonnes raisons cela s'avère inadéquat, que faire (comme dirait Lénine pompant un nihiliste russe) ? Donc je reviens à la première phrase de ce post : je n'ai pas de bonnes idées (sauf à garder en l'état + ajout de liens en virant la "dem"). Via je vous invite réellement à couper-coller-sabrer-renommer la section "rec sur les ordinaux" afin d'harmoniser son contenu avec le reste de l'article et les autres articles (liens). Pour moi elle ne m'appert que comme une section ayant du matos mais à remodeler.

Bon je ne touche à rien et espère fortement que quelqu'un ayant une vision plus synthètique que la mienne touche bcp cette section (j'avoue avoir songé à tout reverter, ce qui est possible, mais au vu des avis ne me semble pas forcèment la bonne solution)

cordialement, --Epsilon0 25 juillet 2007 à 10:27 (CEST)

J'ai l'impression que l'article nombre ordinal, que je trouve plutôt bien (hors sujet : dans les notions basiques, il me semble qu'il manque juste les définitions par récurrence sur un ordinal et d'une classe sur la classe des ordinaux) doit beaucoup à Theon. La récurrence sur la classe des ordinaux y est (exprimée un peu moins formellement). Peut-être est-il le mieux à même de juger si on peut intégrer quelquechose et comment ? Proz 26 juillet 2007 à 01:00 (CEST)

Références

Je suis surpris que des références soient demandées sur des choses qui n'existent pas. Il est ainsi demandé des références pour les deux phrases : Les auteurs des premières utilisations du raisonnement de récurrence ne justifiaient pas pourquoi le résultat obtenu devait être vrai et Si le raisonnement par récurrence est aujourd'hui enseigné dans l'enseignement secondaire, sa justification en est absente. Mais si les justifications sont absentes, comment faire une référence vers cette absence ? C'est bien évidemment l'inverse qu'il faut faire. Si un auteur présente le principe de récurrence, alors on peut faire une référence vers son texte. Theon 19 juillet 2007 à 16:56 (CEST)

Hem. Je suis en train de réfléchir à une nouvelle version.

Dire que "les auteurs des premiers raisonnements par récurrence ne justifiaient pas pourquoi le résultat devait être vrai" est une analyse des documents écrits retrouvés. Le sourçage consiste à attribuer cette analyse ou cette lecture des textses d'origine à tel ou tel historien des mathématiques. Il existe de nombreux articles publiés sérieux dont les auteurs ont une opinion personnelle sur l'histoire du raisonnement par récurrence. Les textes d'origine ne peuvent servir de source car ils peuvent être interprétés différemment selon ceux qui les lisent.

Pour la seconde affirmation, non essentielle, elle dit que la justification du raisonnement par récurrence (soit par construction de l'ensemble des entiers naturels, soit en s'appuyant sur une approche axiomatique de l'arithmétique) n'a pas à être enseigné dans l'enseignement secondaire (et pour causes !). HB a donné des informations ci-dessus sur l'évolution de l'enseignement du raisonnement par récurrence dans l'enseignement secondaire en France. En France, les directives et les programmes scolaires peuvent servir par exemple de source. Plus simplement, il existe des sources, des articles sérieux et publiés dont l'étude porte spécifiquement sur les méthodes d'enseignement et sur leur évolution.

Donc, si, si, les sources existent. Je suis en train de rassembler le maximum de sources intéressantes autour de ce thème.

Ekto - Plastor 19 juillet 2007 à 19:09 (CEST)

L'article anglais a évolué et des sources sont fournies. L'absence dans l'article français d'une quelconque allusion à Pascal et son traité du triangle arithmétique est surprenante car il est souvent cité comme le premier à avoir "conçu et employé" le principe de récurrence (Nicolas Bourbaki, éléments d'histoire des mathématiques p 38) . Theon semble considérer que ce n'est pas le cas mais doit-on se lancer dans des travaux inédits ? HB 24 juillet 2007 à 10:14 (CEST)

La difficulté est de s'y retrouver, de comprendre à partir de quand on peut considérer qu'un raisonnement utilise vraiment le principe de récurrence. D'après Bussey (1917), Moritz Cantor, cite d'abord Pascal, puis Maurolico à la suite d'une remarque de Vacca l'auteur de cet article http://www.ams.org/bull/1909-16-02/S0002-9904-1909-01860-9/S0002-9904-1909-01860-9.pdf, qui attribue la récurrence à Maurolico et indique que Pascal l'a lu (il le signale par ailleurs dans une lettre), même s'il n'y fait pas référence dans son traité du triangle arithmétique. D'après Bussey (et Vacca), je comprend que Maurolicus, en une occasion, utilise un lemme qui permet de passer du cas n au cas n+1 (pour montrer que la somme des n premiers impairs est un carré parfait), donc on peut dire qu'il s'agit vraiment de la récurrence au sens moderne. Evidemment il n'utilise pas nos notations algébriques. Mais en d'autres occasions il procède comme ces prédécesseurs, en traitant (de façon suffisament générale) les premiers cas. Toujours d'après ce que je comprend de Bussey (je n'ai pas le traité de Pascal sous la main), Pascal utilise beaucoup plus systématiquement la récurrence comme nous l'entendons (il traite vraiment le passage de n à n+1). Donc il me semble qu'ils doivent bien être cités tous deux, en disant les choses de façon précise on ne s'engage pas sur qui serait vraiment "le premier". L'article anglais cite Jacob Bernoulli : pour des questions de date ça me parait curieux, et Fermat : probablement la descente infinie. Est-ce que Bourbaki dit d'où vient le mot récurrence ? Proz 24 juillet 2007 à 12:18 (CEST)

Pour la descente infinie, avant Fermat, il y a Euclide qui démontre que tout nombre possède un diviseur premier en utilisant le principe de la descente infinie. Bourbaki ne donne pas l'origine du terme. Il précise en outre que l'on trouve des applications du raisonnement par récurrence plus moins conscientes bien avant Pascal. HB 24 juillet 2007 à 12:33 (CEST)

Oui, présenter l'histoire des mathématiques n'a rien d'évident. Comme je l'ai dit plus haut, chaque lecture d'un texte d'origine reste une analyse personnelle, : il suffit de sourcer les informations introduites. Il ne faut pas se limiter à une version unique de l'histoire. La vérité historique dépend de celui qui l'expose. Ekto - Plastor 24 juillet 2007 à 13:16 (CEST)

Toujours dans les références de la version anglaise (vraiment fort intéressante de ce point de vue), l'article de Roshdi Rashed de 1972 [1] (en accès limité hors d'une bibliothèque ou d'un site universitaire), débute par une discussion générale sur l'histoire de l'induction qui je trouve éclaire bien les choses. En bref et simplificateur, Vacca (sur Maurolico) est contesté (usage très réduit), Pascal est remis en avant. Pour les prédécesseurs de Pascal il s'agit de discussions assez fines sur des formes "archaïques" de raisonnement par induction. Quelle est l'édition de Bourbaki (d'après ce que je lis il semble que Bourbaki citait d'abord Maurolico, s'ils ont évolué c'est une indication) ? Sinon je me répond à propos de Bernouilli : il est bien correct de le citer, c'est lui qui le premier critique explicitement certains raisonnements par induction (de Wallis) en demandant que le cas n -> n+1 soit traité explicitement (d'après Cajori). Proz 29 juillet 2007 à 22:34 (CEST)

Pour Bourbaki (éléments d'histoire des mathématiques) c'est l'édition de 1984 et il ne cite aucunement Maurolico. HB 31 juillet 2007 à 18:37 (CEST)

Merci. J'avais finalement pu vérifié directement en bibliothèque : note 17 (hum ... hum ...) du texte actuel.

J'ai fini par me faire une idée à peu près générale, que j'ai rédigée en brouillon, et que je compte mettre à la place de l'historique actuel, reprise partielle de la version anglaise, qui est vraiment inexacte à ce jour, curieux alors que le travail sur les références semble (avis de profane) si bon. C'est long. N'étant pas historien les approximations ne sont pas exclues, j'espère éviter les contresens. La bibliographie suivra. Proz 31 juillet 2007 à 18:12 (CEST)

Sources

Lister ci-dessous toutes les sources qui pourraient être utilisées :

• Mathematics and its applications in the sciences de Feibleman ;
• The origin of mathematical induction de Bussey ;
• A paradox relating to mathematical induction d'Albert (amusante erreur)
• Mathematical induction in the classroom d'Avital-Libeskind ;
• On proofs by mathematical induction d'Hoar ;
• A mathematical induction d'Ernest ;
• Origin of the Name "Mathemtical Induction de Cajori ;

Ekto - Plastor 16 juillet 2007 à 13:18 (CEST)

De la cohérence interne des modifications

Les deux exemples de récurrence simples ont été changées. Pourquoi pas. Cependant cela élève d'un cran la difficulté de l'exposé car on travaille dans les deux cas sur une somme à nombre de termes non fixes (serie pour la première, formule du binome pour la seconde) . L'exemple de la formule du binome me parait historiquement légitime. Mais quand on modifie, il vaut mieux regarder la suite : dans les "précautions à prendre" qui retombent à une niveau basique, on évoque un exemple qui a maintenant disparu. Il faut donc corriger cela : ou bien on remet l'exemple arithmétique (qui ne fait pas appel à une série et qui a ma préférence je l'avais choisi après mûre réflexion, ou bien on change aussi le contenu de "précaution à prendre". HB 31 juillet 2007 à 23:32 (CEST)

Le changement du premier exemple ça a l'air bien ancien, quel était-il ? Pour le second, effectivement ça ne va pas, je suis plutôt pour le retour à l'ancien exemple. Autant effectivement mélanger les genres et garder un exemple très simple. Peut-être conserver les coefficients binômiaux, plus compliqué mais aussi plus convainquant que la somme des n premiers entiers, que l'on fait mieux en manipulant les sommes (récurrence implicite) et l'ancien second exemple ? Ou alors retour également à l'ancien premier exemple, je vois la somme des carrés en 2005 ? Proz 1 août 2007 à 00:38 (CEST)

J'ai rétabli l'ancien exemple. Ca règle le problème de cohérence. Je me demande si pour le second, il ne faudrait pas quelquechose de plus simple que les coefficients binômiaux. La somme des n premiers nombres impairs est je trouve un bon exemple introductif (l'étape de récurrence donne naturellement le résultat, même si c'est au fond la même chose, c'est plus immédiat que la somme des n premiers entiers), et on pourrait l'illustrer géométriquement. Proz 26 août 2007 à 11:53 (CEST)

Ah, je suis responsable. Non. Je ne suis pas d'accord. Ni avec ce que dit HB, ni avec ce que dit Proz.

Se pose le problème du choix des exemples. A force de choisir des exemples parce que zy zon zolis, parce que ze les zaime bien, on va finir par être encombré d'exemples. On n'écrit pas un traité de mathématiques. Pour les exemples, on peut, pourquoi pas, envoyer le lecteur vers un site en proposant (et il y en a certainement des tas), ou, ce à quoi peu de contributeurs ne pensent malheureusement, l'envoyer vers un cours de la Wikiversité. Si ce cours n'existe pas (ce qui est fort probable), il suffit de l'ébaucher, et de donner les exemples. En plus, on peut donner des tas d'exercices avec solutions.

En quoi l'exemple sur la divisibilité a-t-il la moindre légitimité ? J'ai l'impression que c'est un simple exercice de kholles dont la solution a été rédigée ici. Mais cela ne me semble pas être le lieu. Les seuls exemples qui mériteraient à mon avis d'être cités sont ceux qui présentent soit un intérêt culturel (comme la fractale de Von Koch, mais là, franchement non), un intérêt conceptuel (comme le groupe Z/nZ, mais là, franchement non) ou un intérêt historique (comme l'exemple sur le binôme de Newton ou la somme des n premiers entiers injustement supprimé). On supprime sans réfléchir les exemples historiques et on garde des exemples soit disant pour la pédagogie.

A mon avis, l'intérêt pédagogique devrait être réservé logiquement à la Wikiversité. La plupart des articles des mathématiques me semblent mal rédigées à cause de ça. On a encore la chance de ne pas être nombreux, car imaginez que chaque contributeur écrive son petit exemple favori, on n'aura jamais terminé. Je vais bientôt ouvrir une PdD sur la manière de rédiger un article portant sur les mathématiques, et ce sera l'occasion de reparler sur la manière de choisir un exemple.

Ekto - Plastor 27 août 2007 à 00:00 (CEST)

Je suis tout à fait d'accord sur la non multiplications des exemples introductifs (par ailleurs il faudrait un autre paragraphe d'applications, plus dans le sens de ce que tu proposes). L'exemple supprimé (somme des n premiers entiers) ne s'est sûrement pas fait historiquement comme il était rédigé (c'était de la récurrence implicite, en additionnant la somme retournée, c'est explicite dans certains des articles historiques, Rashed ?, qui le citent comme forme primitive de récurrence). L'intérêt de l'exemple sur la divisibilité (qui a été rétabli, avec quelques modifs mineures, ce n'est pas une nouveauté), c'est le paragraphe "précautions à prendre", ça ne me semble pas inconvenant, mais je n'ai pas de point de vue très affirmé en dehors du fait qu'il faut faire un choix cohérent, et qu'au bout de 26 jours de n'importe quoi, il fallait bien faire quelquechose. Un bon exemple introductif, ça fait aussi partie du mode d'exposition, le choix doit être d'abord celui de la clarté, et de l'accessibilité au plus grand nombre (puisque c'est introductif). Accessoirement celui que je propose est l'exemple de Maurolico, que l'on trouve je crois déjà plusieurs siècles avant chez les mathématiciens arabes. Quant aux "supprime sans réfléchir", "parce que ze les zaime bien", etc., je mets ça sur le compte de la fatigue puisque tu l'invoques. Proz 27 août 2007 à 01:08 (CEST)

Désolé. Je me suis un peu emporté.

Je ne trouve pas que l'exemple d'arithmétique soit plus "simple" que l'exemple de la somme des premiers entiers, ou des premiers entiers impairs ou des premiers carrés (trois exemples qui se valent). Comment définit-on 2^n ? A bien y réfléchir, 2^n se définit par récurrence, au même titre que $\sum _{i=1}^{n}i^{2}$ par exemple. Il me semble impossible de donner une propriété qui se démontre par récurrence et dont les objets étudiés peuvent se définir sans utiliser le prinicipe de récurrence (ou une propriété équivalente). Ne serait-ce parce que je ne sais pas définir autrement l'addition et la multiplication que par récurrence.

Enfin, d'un point de vue oral, il est plus facile de parler de la somme des n premiers entiers, carrés, entiers impairs, ... que de 3 élevé à la puissance 2n que soustrait 2 élevé à la puissance n-3.

J'aurais essayé tous les arguments pour convaincre que l'exemple d'arithmétique n'est pas souhaitable comme exemple introductif ou comme exemple tout court. Kelemvor 28 août 2007 à 13:26 (CEST)

Pour la somme des premiers entiers, ou des premiers entiers impairs ou des premiers carrés : c'est bien du détail. La somme des entiers impairs est la seule des 3, pour laquelle, si je devais l'expliquer sur un coin de nappe, je choisirais quelquechose qui ressemble à la récurrence formelle, d'où ma préférence.

Pour l'exemple arithmétique : tu sous-estimes à mon avis la familiarité que peut avoir le lecteur avec le maniement de certains symboles, en dehors de ça je suis en gros d'accord, le résultat n'a pas d'intérêt en soi, il ne devrait pas apparaître en exemple 1 (erreur de ma part, c'était l'exemple 2 avant). Je propose de le réduire (laissons tomber le calcul de (u_n) ...) et de l'incorporer au § "précautions d'emploi", en précisant son côté "exercice" (l'idéal serait de trouver un exemple "intéressant", susceptible du même traitement, un exemple très similaire qui ne marche pas à cause de l'initialisation mais je ne vois pas). Le premier exemple serait alors la somme des n premiers entiers impairs (ou des entiers si tu y tiens), plus simple que la formule du binôme (moins de symboles, relation de récurrence simple). Proz 28 août 2007 à 20:40 (CEST)

Justification du principe de récurrence

Il me semble que le texte de Pascal cité dans la partie historique donne bien une justification (intuitive) de la récurrence. Celle citée dans ce paragraphe est d'ailleurs analogue. Je suppose que certains enseignants du secondaire ne se privent pas d'en faire autant. Je ne pense pas que l'on puisse laisser le texte actuel en l'état. Proz 26 août 2007 à 22:47 (CEST)

ou plus généralement sur tous les entiers supérieurs à un entier donné

Je serais partisan de supprimer le membre de phrase « , ou plus généralement sur tous les entiers supérieurs à un entier donné » qui n'apporte pas grand chose, surtout au niveau de la présentation générale, et qui, de plus, n'est pas dans l'esprit (contemporain) de la récurrence ; une garde du genre $n\geq n_{0}\Rightarrow ...$ suffit pour avoir la propriété pour tous les entiers. Pierre de Lyon (d) 8 janvier 2008 à 09:33 (CET)

Le début doit être accessible à un public "débutant" (la récurrence ça s'enseigne dans le secondaire). Les propriétés qu'ils démontrent ça doit être le plus souvent des égalités ou des inégalités : aucune complexité logique. Même dans les premières années de fac les étudiants ont bien des problèmes dès que la formule à démontrer a la moindre complexité logique, l'implication en particulier (que tu peux imaginer, une hypothèse dont on peut se servir, l'autre qu'il faut démontrer). Je ne parle pas des quantifications. La récurrence à partir de n_0 est aussi intuitive que celle à partir de 0 (c'est la même structure). Je ne vois pas le problème. Pour moi ça démontre que la récurrence à partir de 0 a pour conséquence la récurrence à partir de n_0 (démonstration qui est déjà indiquée, avec une disjonction, ce qui me semble un poil plus simple à comprendre, cf. ci-dessus et surtout l'initialisation), ou avec addition (une façon un peu détournée de dire que la structure est la même). Maintenant qu'est-ce qui doit apparaître dans le résumé ? Quand je suis intervenu sur cet article (avec d'autres), j'ai eu l'impression que certains tenaient à ce que la récurrence soit "par défaut" à partir de n'importe quel entier. Tant que l'on dit bien que ça se ramène à celle à partir de 0 , pour moi ça va. Par contre je ne suis pas pour ta reformulation dans le paragraphe "précautions d'emploi", qui n'a d'intérêt que pour des débutants. Ta modification à mon avis ne leur facilite pas la lecture.

Le principe de récurrence Artin est très amusant : as-tu un exemple court, ou un redirect vers un autre article où il y en a un ?

Pour le dernier paragraphe : il y avait plus ou moins accord pour que les aspects formels (axiomatiques) soient traités dans un autre article (il y a arithmétique de Peano) (et je ne comprends pas en quoi parler de fonction booléennes aide). Proz (d) 8 janvier 2008 à 22:51 (CET)

complément voilà ce que j'avais mis pour l'intro http://fr.wikipedia.org/w/index.php?title=Raisonnement_par_r%C3%A9currence&oldid=18344697, avec une belle faute d'orthographe mais quelqu'un est revenu dessus. Je trouve effectivement plus simple de partir de 0 dans le § d'ouverture, mais il faut en dire un peu plus sur la récurrence à partir de k dans le § "récurrence simple". Proz (d) 8 janvier 2008 à 23:14 (CET)

Je me suis mal fait comprendre, je ne souhaitais pas parler de « garde » dans l'introduction de l'article, surtout pas, car j'ai tous les arguments que tu donnes dans la tête, notamment celui de l'enseignement secondaire. Je voulais seulement indiquer que la récurrence est une méthode pour démontrer une propriété sur tous les entiers naturels. Mon argument sur la garde (qui n'avait pour but d'être que dans la page de discussion) était pour monter qu'ainsi on ne perdait rien par rapport à une récurrence soi-disant plus générale.

J'avais reformulé la section "précaution à prendre" par ce que je ne comprenais pas celle qui y était, ce qui est très embêtant, car si moi qui suis bac + 10n; je ne comprends pas, je ne crois pas qu'un bac-2 puisse comprendre. C'est en général ce qui guide mes propositions de reformulation. Ceci dit, j'adhère complètement à la formulation actuelle.

Artin utilise sa méthode de récurrence pour monter que si une fonction (dite convexe) satisfait

$f({\frac {x_{1}+x_{2}}{2}})\leq {\frac {f(x_{1})+f(x_{2})}{2}},$

alors elle satisfait:

$f({\frac {x_{1}+...+x_{n}}{n}})\leq {\frac {f(x_{1})+...+f(x_{n})}{n}}.$

Je discutais de ce principe de récurrence avec l'un des auteurs du livre sur Coq, dit « Coqart », qui l'appelaient « bizarre » ("weird") dans l'exercice 8.18 et quelqu'un m'a dit que ce principe aurait été déjà connu de Poincaré et utilisé par lui.

Pierre de Lyon (d) 14 janvier 2008 à 15:26 (CET)

Oui j'ai un peu enfoncé des portes ouvertes, désolé. J'ai simplifié et déplacé la récurrence à partir d'un certain rang dans le § définition.

Pour l'exemple d'Artin : y-a-t-il une hypothèse sur f ? Proz (d) 14 janvier 2008 à 22:49 (CET)

Non pas que je sache. On montre que

$f({\frac {x_{1}+...+x_{n}}{n}})\leq {\frac {f(x_{1})+...+f(x_{n})}{n}}.$

implique

$f({\frac {x_{1}+...+x_{2n}}{2n}})\leq {\frac {f(x_{1})+...+f(x_{2n})}{2n}}.$

puis que

$f({\frac {x_{1}+...+x_{n}}{n}})\leq {\frac {f(x_{1})+...+f(x_{n})}{n}}.$

implique

$f({\frac {x_{1}+...+x_{n-1}}{n-1}})\leq {\frac {f(x_{1})+...+f(x_{n-1})}{n-1}}.$

en utilisant

$f({\frac {x_{1}+x_{2}}{2}})\leq {\frac {f(x_{1})+f(x_{2})}{2}},$.

Pierre de Lyon (d) 15 janvier 2008 à 20:54 (CET)

Pour les curieux, j'ai trouvé la référence actuelle du livre d'Artin sur la fonction gamma qui a été réédité en 2006, il s'agit de Emil Artin, "The Gamma function", in Rosen, Michael (ed.) Exposition by Emil Artin: a selection; History of Mathematics 30. Providence, RI: American Mathematical Society (2006). Et si vous êtes très pressé ou très curieux, allez là, puis feuilletez jusqu'à la page 5.

N. B. L'édition originale en allemand, de 1931, est Einführung in die Theorie der Gammafunktion. — Leipzig, B. G. Teubner, 1931 (Hamburger mathematische Einzelschriften, 11). Pierre de Lyon (d) 4 mars 2008 à 08:21 (CET)

J'ai failli dire, faut mettre la ref dans l'article et non ici, mais je vois que tu l'as fait. Donc oui, je suis un curieux qui va aller voir. --Epsilon0 ε₀ 4 mars 2008 à 10:19 (CET)

Je serais pour plutôt citer cet exemple de Artin (en résumant évidemment), et en faisant ressortir le principe utilisé, plutôt que des généralisations que l'on peut imaginer assez vite, mais sans applications. Il manque par ailleurs dans l'article quelques exemples d'utilisations un peu "élaborées" de la récurrence (ça pourrait être une une section à organiser, il ne s'agit pas d'aligner des exemples en vrac). Proz (d) 4 mars 2008 à 14:49 (CET)

Théorème de récurrence

Ne pourrait-on, à côté de la version qui fait référence à N, rajouter quelques mots pour dire que la propriété de récurrence peut s'établir sans faire appel à l'axiome de l'infini (Krivine, théorie des ensembles p. 44) ? --Michel421 (d) 9 avril 2009 à 22:32 (CEST)

Il s'agit alors d'un schéma de théorèmes. La récurrence ne peut plus s'exprimer sous sa forme ensembliste. Il faut expliquer comment définir la classe des entiers (qui n'est plus nécessairement un ensemble). C'est rentrer dans bien des subtilités si on veut être compris, pour un intérêt limité (ça permet de montrer que la théorie des ensembles sans axiome de l'infini est essentiellement l'arithmétique de Peano) et je ne pense pas que l'article soit destiné à ce genre de développements. Déjà actuellement on ne comprend pas bien la cohérence de ce paragraphe. Proz (d) 11 avril 2009 à 09:38 (CEST)

En fait, le paragraphe n'avait pas de sens, j'ai corrigé. --Michel421 (d) 11 avril 2009 à 11:11 (CEST)

Ce n'était peut-être pas des notations très standard, mais c'était équivalent :-) Outs (d) 12 avril 2009 à 16:21 (CEST)

Pas du tout : confusion appartenance-inclusion, absence d'une variable pour les éléments de P, oubli d'un étage (il faut deux implications). Cordialement --Michel421 (d) 12 avril 2009 à 17:08 (CEST)

Sisi, je rappelle ce que j'avais marqué : $\forall P\subseteq \mathbb {N} ,(0\in P\land succ[P]\subseteq P)\Rightarrow \mathbb {N} \subseteq P$ avec $succ[P]$ l'image de P par la fonction successeur des entiers.Donc, selon la définition de l'image d'un ensemble par une fonction on peut remplacer $succ[P]\subseteq P$ par $\{y|\exists x\in P\cdot succ(x)=y\}\subseteq P$. Et on peut réécrire l'inclusion par $\forall n\cdot n\in \{y|\exists x\cdot x\in P\land succ(x)=y\}\Rightarrow n\in P$ c'est à dire $\forall n\cdot \exists x\cdot x\in P\land succ(x)=n\Rightarrow n\in P$. Après on peut enlever la quantification existentielle en instanciant x par n-1, on obtient $\forall n\cdot n-1\in P\Rightarrow n\in P$. (On peut remplacer n par n+1 si tu veux). Mais je ne suis pas contre la version actuelle qui est probablement plus facile à comprendre, bien que plus longue. Cordialement Outs (d) 14 avril 2009 à 10:25 (CEST)

... visant à démontrer une propriété portant sur tous les "entiers naturels"

N'est-ce pas trop restrictif de ne parler que des entiers naturels ? Mes étudiants s'amusent à utiliser la récurrence sur des entiers, ou même des rationnels. N'est-il pas plus juste de dire qu'elle s'applique "sur un ensemble infini-dénombrable de nombres" ? Mais naturellement, du coup, cela complique le formalisme P(0) et P(n)->P(n+1) puisque, par exemple, on ne vérifie plus d'abord la propriété pour 0, mais pour "le premier nombre de la suite".

Ici l'article est plutôt centré sur l'ensemble des entiers mais ce peut en effet se généraliser sur tout ensemble muni d'une relation de bon ordre et ce même au delà du dénombrable, voyez récurrence transfinie. Cordialement --Epsilon0 ε₀ 14 août 2009 à 17:58 (CEST)

"Généralisation"

Je copie ici une discussion qui s'est tenue au Thé :

Je suis assez mal à l'aise sur les généralisations du raisonnement par récurrence mais celle qui vient d'être présentée ici me parait bizarre. Quelqu'un pourrait-il vérifier et valider cela comme un raisonnement par récurrence ? Merci. HB (d) 25 août 2009 à 17:25 (CEST)

Si je ne me suis pas fait avoir à lire ce que je pensais plutôt que ce qui était écrit, c'est indéniablement juste. Une fois qu'on a dit ça, savoir si quelqu'un a déjà appelé ça une "généralisation de la récurrence" c'est plausible tant de choses ont été écrites en mathématiques élémentaires ; mais exiger une source semble s'imposer (or l'IP doit être repartie après avoir pondu son oeuf...). En tous cas, je n'avais jamais vu cette remarque ; poser un "référence nécessaire" sur la première phrase attendre trois mois et effacer tout le paragraphe si elle n'est pas venue à ce moment serait la politique que je recommanderais. Maintenant le fait que je ne connaisse pas n'est pas la preuve que ça ne soit pas raisonnablement canonique, évidemment, je partage simplement ton doute. Touriste (d) 25 août 2009 à 17:37 (CEST)

"c'est indéniablement juste". D'accord, mais cela me paraît trivial et je pense que cela n'aide pas à démontrer le principe de récurrence. À mon avis, ce n'est pas une généralisation du principe de récurrence. Je supprimerais.

Marvoir (d) 25 août 2009 à 17:58 (CEST)

A ce que je comprends de cette "généralisation" c'est que si pour tt sous-ens strict A d'un ensemble E, il existe un élément de E-A, qui a une certaine propriété P, alors tout élément de E a la propriété P ... ce qui me semble tout de même assez évident et ne pas avoir grand chose à voir avec le raisonnement par récurrence, mais p.-e. qqch m'a échappé. jJ' ai l'impression en regardant en diagonale la suite de l'ajout que ce dont il parle à plus à faire avec l'axiome du choix, dont on a p.-e. besoin pour démontrer le thm en toute généralité, qu'avec la récurrence. --Epsilon0 ε₀ 25 août 2009 à 17:59 (CEST)

Il n'est quand même pas correct de dire comme c'est fait que la récurrence sur les entiers est un cas particulier de cette propriété, qui est au contraire plus faible. La "vraie" généralisation c'est la récurrence sur les relations bien fondées (dont la récurrence sur les entiers est bien cette fois un cas particulier). On ne peut donc pas laisser en l'état, ça semble difficile de corriger (jamais vu non plus), donc je suis plutôt pour supprimer. Proz (d) 25 août 2009 à 21:40 (CEST)

Je dois dire qu'après avoir lu le passage supprimé, je ne suis pas d'accord avec vous: il s'agit bien d'une démonstration du type récurrence. La récurrence c'est tout de même de dire que, quelque soit l'ensemble A, strictement inclus dans E, donné, et supposé contenir tous les éléments de E satisfaisant la propriété P, s'il en existe un à l'extérieur de A, alors la propriété P est vraie sur E. C'est pour le raisonnement par récurrence sur les entiers l'équivalent de la propriété du plus grand entier satisfaisant P.Il n'y avait donc rien de choquant là-dedans. Il s'agissait seulement d'une formulation de la récurrence en termes d'ensembles d'indices quelconques.Claudeh5 (d) 26 août 2009 à 09:11 (CEST)

Vu le consensus, je vais supprimer le passage litigieux.
Marvoir (d) 26 août 2009 à 08:05 (CEST)

"La récurrence c'est tout de même de dire que, quelque soit l'ensemble A, strictement inclus dans E, donné, et supposé contenir tous les éléments de E satisfaisant la propriété P, s'il en existe un à l'extérieur de A, alors la propriété P est vraie sur E." A mon avis, non. Si c'était ça la récurrence, ce serait quelque chose de trivial. Pour conclure par récurrence, il suffit d'établir (par exemple, car le raisonnement par récurrence a plusieurs formes) que si P(i) est vrai pour tout i < n, alors P(n) est vrai. Cela établi, il n'en résulte pas directement que "quel que soit l'ensemble A, strictement inclus dans E, donné, et supposé contenir tous les éléments de E satisfaisant la propriété P, il en existe un à l'extérieur de A". Évidemment, puisque de l'hypothèse "si P(i est vrai pour tout i < n, alors P(n) est vrai" on tire P(n) pour tout n, on peut ensuite en tirer que "quel que soit l'ensemble A, strictement inclus dans E, donné, et supposé contenir tous les éléments de E satisfaisant la propriété P, il en existe un à l'extérieur de A", mais cette prétendue généralisation n'a joué aucun rôle dans la démonstration. En fait, la notion de bon ordre joue un rôle essentiel dans le principe de récurrence, et elle n'apparaît pas dans la prétendue généralisation.

On pourrait tout aussi bien prétendre que l'énoncé suivant est une généralisation du principe de récurrence : si l'ensemble des éléments de X qui possèdent une certaine propriété n'est pas une partie propre de X, c'est X tout entier.

Marvoir (d) 26 août 2009 à 10:25 (CEST)

On doit avoir une différence de point de vue sur le terme trivial ! La récurrence m'apparaît être un raisonnement "trivial" à l'instar de monter sur une échelle. Si je peux mettre le pied sur le premier échelon et, ayant atteint un échelon quelconque, mette le pied sur l'échelon suivant, je peux grimper tout en haut de l'échelle.Claudeh5 (d) 26 août 2009 à 11:07 (CEST)

Il ne faut pas trop non plus se poser de question. Personne n'a vu ce principe. Il n'est donné aucune application. Il est impropre de parler de généralisation pour un résultat, qui comme le détaillait le passage supprimé, est obtenu en généralisant l'hypothèse de récurrence, donc en affaiblissant (fortement !) le principe de récurrence. Cette partie était donc au minimum trompeuse. Rien n'est perdu, l'auteur peut toujours réagir et s'expliquer s'il s'avèrait que le résultat ait un intérêt, (mais j'ai bien l'impression que sur le fond cela revient à l'énoncé de Marvoir). Proz (d) 26 août 2009 à 11:19 (CEST)

On peut ajouter qu'il y a une différence fondamentale entre le principe de récurrence sur les entiers et le passage qui a été supprimé ; c'est que le principe de récurrence est un axiome et ne peut se démontrer (sauf si on se place dans le cadre d'une théorie plus puissante englobant les entiers), alors que le passage supprimé contenait une preuve simple. Je pense que c'est cela qui a fait dire à Marvoir : Si c'était ça la récurrence, ce serait quelque chose de trivial. Theon (d) 27 août 2009 à 09:04 (CEST)

Admettons que "trivial" est un jugement subjectif. Pour voir plus clair, je propose aux partisans de la "généralisation" de la faire fonctionner sur un cas précis. Voici un exemple de démonstration par récurrence. Prouvons que tout naturel non nul n est décomposable en produit de facteurs premiers. Supposons que ce soit vrai pour tout nombre naturel non nul < n et prouvons que c'est vrai pour n. Si n = 1, n est le produit d'une famille vide de nombres premiers, donc la thèse est vraie. Si n est premier, il est décomposable (en un produit d'un facteur premier), donc la thèse est vraie. Si enfin n est > 1 et n'est pas premier, il est le produit de deux nombres naturels non nuls a et b tous deux < n; par hypothèse de récurrence, a et b sont tous deux décomposables, donc n est décomposable, ce qui achève la démonstration.

Un partisan de la "généralisation" pourrait-il démontrer ce théorème à l'aide de la "généralisation" et sans utiliser le principe de récurrence ordinaire autrement que comme un cas particulier de la "généralisation" ? (Attention : raisonner sur le plus petit naturel non décomposable et obtenir une contradiction reviendrait à utiliser le principe de récurrence.)

Marvoir (d) 27 août 2009 à 12:13 (CEST)

ou plus généralement sur tous les entiers supérieurs à un entier donné, 2ème édition

Je viens juste de voir que tout a été dit plus haut. Le compromis me plaisait (ne mentionner cette formulation qu'en cours d'article mais pas dans le résumé introductif), et ce n'est que pour parfaire la modif d'un IP que je suis intervenue dans sa foulée, sans conviction, le 27. Le 28, Theon a "reverté" (au sens large) le tout. Dfeldmann semble avoir des doutes sur le bien-fondé de ce "revert". Moi, plus aucun, maintenant que j'ai lu plus attentivement l'article et sa PdD. Anne Bauval (d) 29 décembre 2009 à 00:58 (CET)

Le plus simple serait de laisser en intro le raisonnement à partir de 0, et, si on y tient, de mettre dans le paragraphe Raisonnement par récurrence#Généralisations la récurrence à partir de m. Après tout, le raisonnement de récurrence repose sur l'axiome de Peano qui démarre à 0, et la justification de la récurrence à partir de m repose sur le même axiome ou sur la récurrence à partir de 0. Autrement dit, ce n'est pas la récurrence à partir de 0 qui est un cas particulier de la récurrence à partir de m, c'est le contraire, malgré les apparences. Theon (d) 29 décembre 2009 à 09:48 (CET)

Chacun des deux peut être considéré comme un cas particulier de l'autre. Je crois que le mieux pour la lisibilité et la cohérence de l'article serait de laisser les choses comme ça. Tout ça a déjà été discuté l'an dernier sur cette PdD, et il y a déjà la justification de la récurrence à partir de m dans le paragraphe Raisonnement par récurrence#Récurrence simple sur les entiers. Anne Bauval (d) 29 décembre 2009 à 10:30 (CET)

Images dans le texte et caractères spéciaux

Les modifs d'aujoud'hui empirent pour moi (et certainement pas que pour moi) la lisibilité : tous les N sont remplacés par des carrés ! (déjà que les $\in$ et les $\Rightarrow$ étaient des carrés ...) Anne Bauval (d) 15 avril 2010 à 22:22 (CEST)

je partage ton avis : ce n'est pas au lecteur d'être obligé de télécharger la bonne fonte pour lire les articles de math. passe encore que des caractères chinois ne soient pas lus mais ici cela nuit gravement à la compréhension de l'article. Je retourne à la version du N en gras (suivant ainsi les recommandations pour la composition des textes scientifiques rédigé par le groupe des mathématiques de l'Inspection Générale, reprenant l'ouvrage de référence : Lexique des règles typographiques en usage à l'Imprimerie nationale). HB (d) 16 avril 2010 à 07:51 (CEST)

Concernant les autres symboles, le changement sera plus dur, il faudrait, ou bien tout écrire en math, ou tout écrire en français : déjà lis-tu ce symbole ⇒ ? HB (d) 16 avril 2010 à 08:05 (CEST)

non Anne Bauval (d) 16 avril 2010 à 20:50 (CEST)

Oui, c'est triste... je tente donc sur une section une version rédigée. Si pas d'avis opposé, je continuerai plus tard sur les autres sections. HB (d) 16 avril 2010 à 22:15 (CEST)

Merci, au moins c'est lisible. Après, c'est une affaire de goût, d'habitude, de paresse ...

Personnellement ça me fatigue plus (et me prend plus de temps) non seulement d'écrire, mais de lire, par exemple

"Pour tout entier naturel n, (n appartient à E implique n+1 appartient à E)"

et "Pour tout entier n supérieur ou égal à k, [P(n) implique P(n+1)]"

plutôt que

"$\forall n\in \mathbb {N} ,(n\in E\Rightarrow n+1\in E)$"

et "pour tout entier $n\geq k$, ($P(n)\Rightarrow P(n+1)$)"

mais ce n'est que mon avis Anne Bauval (d) 16 avril 2010 à 22:50 (CEST)

ach! après une formation bourbakiste qui me ferait aussi préférer la forme symbolique, il y a eu l'influence des inspecteurs pédagogiques qui demandent de privilégier le français...Le français étant un langage plus répandu que le symbolisme mathématique, j'ai tendance ici à le privilégier mais ce n'est qu'une proposition.D'autre part, j'ai aussi appris qu'il est déconseillé de mélanger symbolisme et français. et j'écrirais donc pour ma part plutôt

$(\forall n\in \mathbb {N} )[(n\geq k{\text{ et }}P(n))\Rightarrow P(n+1)]$

ce qui est plutôt lourd. Je ne suis en fait attachée à aucune des deux formes et cherche à trouver ce qui est le mieux pour l'article. Il serait donc bon que d'autres contributeurs donnent leur avis. HB (d) 17 avril 2010 à 08:02 (CEST)

Pour démontrer que tout entier naturel supérieur ou égal à 2 possède un diviseur premier.

Je trouve que cet exemple de récurrence est mal choisi car on peut démontrer très simplement ce résultat sans récurrence. En effet, le plus petit diviseur p>1 d'un entier n>1 est un nombre premier : tout diviseur de p>1 divise n, donc vaut p ou 1 par minimalité de p. Je pense qu'il faudrait changer d'exemple. Leon1789 (d) 1 octobre 2010 à 11:59 (CEST)

Votre démonstration me semble en effet beaucoup plus simple et plus élégante. Il vaudrait sans doute mieux réserver la récurrence à la preuve de la décomposabilité de tout nombre naturel (non nul) en produit de facteurs premiers. Sauf avis contraires, vous pourriez le faire si le coeur vous en dit, ou je pourrais m'en charger. Marvoir (d) 1 octobre 2010 à 12:20 (CEST)

Oui, mais la décomposition des entiers est abordée sur la page du théorème fondamental [2]. Personnellement, pour illustrer le principe de récurrence, je pensais à un exemple simple : $1^{2}+2^{2}+3^{2}+\cdots +n^{2}=n(n+1)(2n+1)/6$. Je peux l'écrire si personne n'est contre. Leon1789 (d) 1 octobre 2010 à 12:34 (CEST)

Mince, j'avais oublié que c'était l'illustration d'une récurrence dite forte. Je vais réfléchir à un exemple autre que celui du théorème fondamental... Leon1789 (d) 1 octobre 2010 à 12:37 (CEST)

A toutes fins utiles, j'ai mis sur Wikiversité une démonstration (par récurrence dite forte) de la décomposabilité qui ne repose pas sur une démonstration préalable de l'existence d'un diviseur premier. Mais on peut évidemment préférer une démonstration qui repose sur la démonstration préalable de cette existence. Marvoir (d) 1 octobre 2010 à 12:41 (CEST)

Oui, c'est aussi la preuve donnée pour le théorème fondamental sur wikipédia.

Autre exemple : que pensez-vous de celui-ci ? Prouver que la seule solution $(m,n)\in \mathbb {N} ^{2}$ de l'équation $m^{2}=2n^{2}$ est (0,0). Bon, c'est connu et la rédaction peut paraître un peu alambiquée, bien que courte... Pour répondre au problème, on va démontrer par récurrence forte sur n l'assertion $P(n):\forall m\in \mathbb {N} ,m^{2}=2n^{2}\Rightarrow m=n=0$. Prouver P(0) est facile. Hérédité : soit n>0, supposons $P(0),\dots ,P(n-1)$ et prouvons P(n). Considérons $m\in \mathbb {N} ,m^{2}=2n^{2}$. On a nécessairement m pair, d'où $n^{2}=2(m/2)^{2}$ (quotient entier). On a de plus $(m/2)^{2}=n^{2}/2<n^{2}$, donc m/2<n. Ainsi l'hypothèse P(m/2) justifie n = m/2 = 0, d'où finalement m=n=0 prouvant l'hérédité. Le principe de récurrence permet de conclure $\forall n,m\in \mathbb {N} ,m^{2}=2n^{2}\Rightarrow m=n=0$ Leon1789 (d) 1 octobre 2010 à 15:46 (CEST)

La démonstration me semble juste mais ce qui m'ennuie c'est que des exemples de récurrences fortes on peut en créer par millier. On peut donc mettre ton exemple ou un autre. Quelqu'un peut critiquer ton exemple comme tu critiques celui existant en montrant qu'il existe des démonstrations beaucoup plus simple de l'irrationalité de $\sqrt 2$. Il faut donc trouver un critère d'édition : ce critère pourrait être "cet exemple est souvent cité dans la littérature". Selon ce critère, la démonstration actuellement présentée est plus fréquente que celle que tu proposes. J'en profite juste pour te faire remarquer que lorsque tu parles de plus petit diviseur de n strictement plus grand que 1, tu utilises sans le dire le principe de récurrence, car tu utilises l'existence d'un plus petit diviseur, existence qui n'est prouvée que par la propriété "toute partie de N non vide possède un plus petit élément" (*), propriété qui est , si je ne m'abuse, équivalente au principe de récurrence. Donc je ne suis pas favorable à un changement. HB (d) 1 octobre 2010 à 16:17 (CEST)

Je suis d'accord que l'exemple sur la résolution de $m^{2}=2n^{2}$ n'est pas satisfaisant, bien que je demande à voir une preuve plus simple de ce résultat (un raisonnement par l'absurde avec disjonction de cas ??). Pour le critère d'édition, on peut effectivement choisir "cet exemple est souvent cité dans la littérature". Dans ces conditions, je préfère le théorème fondamental à l'exemple actuellement en ligne que je trouve (c'est absolument subjectif) bien lourd pour le peu qu'on en retient. Cela dit, pourquoi ne pas choisir le critère "cet exemple n'est pas fréquent dans la littérature" et donner un exemple qui sort des sentiers hyper-battus ? Mais il en faut un pas trop complexe. En as-tu un parmi tes milliers ? Par ailleurs, si on rentre le détail des preuves et des principes qu'elles utilisent, oui, il y a équivalence entre la propriété (*) et le principe de récurrence, à condition d'utiliser le principe du tiers exclu. Pour moi, dans le cas de l'exemple en ligne, l'utilisation d'une récurrence avec tiers exclu (être premier ou pas) donne une version explicitement affaiblie par rapport à la version utilisant la propriété (*). C'est aussi pour cela que je suis favorable à un changement. Leon1789 (d) 1 octobre 2010 à 17:23 (CEST)

Non je n'en connais pas de plus simple que celui qui figure actuellement ici. Celui sur la décomposition en facteurs premiers me parait plus compliqué et utilise deux fois le principe de récurrence (une fois pour "le plus petit diviseur, et l'autre fois pour la récurrence forte). Prendre comme critère "sortir des sentiers battus" risque de créer une surenchère sur l'originalité. Enfin je ne suis pas la seule, et de loin, à suivre cet article donc d'autres avis seraient souhaitables. HB (d) 1 octobre 2010 à 17:45 (CEST)

Pour prouver que la seule solution $(m,n)\in \mathbb {N} ^{2}$ de l'équation $m^{2}=2n^{2}$ est (0,0), le plus simple me semble d'utiliser le théorème fondamental : si m et n sont tous deux des naturels non nuls, la puissance de 2 dans la décomposition de m² est paire et la puissance de 2 dans la décomposition de 2n² est impaire, donc m² et 2n² ne peuvent pas être égaux. Ceci dit, je continue à penser que la démonstration donnée dans l'article de l'existence d'un facteur premier est trop lourde, même si, comme le note HB, la démonstration de Leon1789 utilise une propriété de N (bon ordre) qu'on peut considérer comme équivalente au principe de récurrence. Je proposerais de donner comme exemple de récurrence forte la démonstration de la décomposabilité telle qu'elle est donnée dans l'article sur le théorème fondamental. (Je n'avais pas pris garde que la démonstration que j'ai mise sur Wikiversité est identique à celle qui est donnée dans l'article de Wikipédia sur le théorème fondamental.) Marvoir (d) 1 octobre 2010 à 17:52 (CEST)

Pour la résolution de $m^{2}=2n^{2}$, utiliser le théorème fondamental demande sa démonstration préalable. Ensuite le cas où les deux entiers m et n sont nuls est traité. Reste l'autre cas à traiter : si m ou n est nul, alors les deux sont nuls, ce qui donne une solution (la seule). Je ne vois pas en quoi tout ceci (théorème préalable et disjonction de cas) est plus simple que la preuve par récurrence forte que je propose. Mais bon, effectivement, cet exemple n'est pas satisfaisant.

Autre exemple : une plaquette de chocolat est composée de n carrés séparés par des petites rainures ($n\geq 1$). En cassant le chocolat suivant les rainures, en combien de coups minimum peut-on réduire la plaquette en carrés ? Réponse : quelle que soit la méthode, la réduction en carrés se fait en n-1 cassures. Prouvons-le par récurrence forte sur n. Pour n=1, il n'y a rien à faire, 0 cassure, c'est bien n-1. Supposons le résultat vrai pour tous les entiers inférieurs à n et montrons le résultat pour n+1. On casse une plaquette de n+1 carrés en a>0 carrés d'un coté et b>0 carrés de l'autre : on a alors a+b=n+1 et $1\leq a,b\leq n$. On peut appliquer la propriété pour l'entier a (ce qui produit a-1 cassures) et l'entier b (ce qui produit b-1 cassures). Au total, on a cassé la plaquette initiale (1)+(a-1)+(b-1) = n fois, ce qui conclut l'hérédité. Cet exemple n'est-il pas trop "enrobé" ? Leon1789 (d) 1 octobre 2010 à 19:41 (CEST)

Ne suffit-il pas de dire que chacune des n-1 rainures doit avoir été cassée ? Franchement, cet exemple ne me plaît pas, parce qu'il faudrait encore formaliser la mathématisation du problème. D'autre part, si vous trouvez que la démonstration classique de l'irrationalité de la racine carrée de 2 (celle que j'ai donnée, et qui est facilement généralisable à d'autres exposants et à d'autres radicands) n'est pas plus simple et plus satisfaisante que la vôtre, je crois que nous ne nous entendrons jamais. Marvoir (d) 1 octobre 2010 à 20:29 (CEST)

Marvoir, Il n'y a pas toujours n-1 rainures (prendre une plaque de 3 x 4) et pourtant n-1 cassures sont nécessaires et suffisantes. Je trouve cet exemple très joli. Hélas pas dans la littérature mais très joli. HB (d) 1 octobre 2010 à 20:41 (CEST)

Effectivement, la tablette est rectangulaire en général. Mais revenons à quelque chose de plus mathématique car trop de chocolat pèse sur le foie ... Je n'ai jamais voulu évoquer l'irrationalité de ${\sqrt {2}}$ : j'aurais pu considérer l'équation $x^{2}+y^{2}=3z^{2}$ par exemple et opérer de manière assez analogue. Au fait, puisqu'il a été question de généralisation, avez-vous remarqué que la preuve que je donne pour résoudre $m^{2}=2n^{2}$ se généralise de même manière que votre preuve utilisant le théorème fondamental (à démontrer avant d'attaquer l'équation) ? C'est parce que ces deux preuves utilisent essentiellement la division par 2... Mais là, on s'engage dans une autre discussion que la récurrence forte, surtout que j'ai écrit au-dessus effectivement, cet exemple n'est pas satisfaisant. Je rappelle que mon but n'est pas de trouver un exemple le plus simple possible, mais un peu moins rengaine qu'une démonstration du théorème fondamentale que l'on voit partout dès qu'on parle de récurrence forte. C'est évidemment subjectif. Leon1789 (d) 1 octobre 2010 à 23:23 (CEST)

Désolé, je n'avais pas bien compris l'exemple de la plaquette de chocolat. (Je pensais à une barre au lieu de penser à une plaquette.) Cet exemple est en effet très joli. Voici la généralisation dont je parlais : un nombre naturel qui n'est pas la r-ième puissance d'un nombre naturel n'est pas non plus la r-ième puissance d'un nombre rationnel. Autrement dit, si un nombre naturel a n'est pas la r-ième puissance d'un nombre naturel, il n'existe pas de nombres naturels non nuls b, c tels que b^r = ac^r. En effet, il existe au moins un facteur premier de a qui ne figure pas dans a avec un exposant divisible par r, donc ce facteur premier ne figure pas dans ac^r avec un exposant divisible par r. Comme il figure dans b^r avec un exposant divisible par r, b^r et ac^r ne peuvent donc pas être égaux. Pensez-vous que vous pourriez généraliser votre démonstration à ce cas général sans faire intervenir le théorème fondamental, et que votre généralisation serait plus élégante que celle que je viens de donner ? Marvoir (d) 2 octobre 2010 à 08:59 (CEST)

ok, il n'y a pas de généralisation de ma preuve par récurrence. Je n'avais pas constaté que l'exposant r=2 est important dans cette démo, et que le coefficient a doit être premier pour passer simplement du couple (b,c) au couple (c,b/a)... Si on veut généraliser à tout exposant et tout coefficient "admettant un premier qui", il faut alourdir la preuve par récurrence. Cela étant dit, dans la preuve que j'ai présentée au début, c'est vrai que c'est bien compliqué de passer de $m^{2}=2n^{2}$ à $n^{2}=2(m/2)^{2}$ et voir que m/2<n pour appliquer l'hypothèse de récurrence... Leon1789 (d) 2 octobre 2010 à 12:44 (CEST)

Sur tous les exemples discutés ci-dessus, celui qui me paraît le plus important est celui de la décomposition de n en produit de facteurs premiers (ce que suggérait Marvoir dans sa première réponse), mais, comme le dit Leon1789, cet exemple figure in extenso dans le théorème fondamental de l'arithmétique. Il n'est sans doute pas utile de le faire figurer deux fois. Celui de la plaque de chocolat est amusant et non évident. Il peut être intéressant de le faire figurer, mais il faudrait une figure pour l'illustrer, la discussion ayant montré que son énoncé seul peut être mal compris. Theon (d) 2 octobre 2010 à 14:58 (CEST)

Je dois avouer que j'ai été étourdi à propos de la plaquette de chocolat. Mais, en effet, une illustration préviendrait sans doute tout malentendu. Si j'ai bien compris, cet exemple a été inventé par Leon1789 et est inédit, mais, pour ma part, je n'ai rien contre la publication dans Wikipédia d'un travail inédit si elle est approuvée unanimement. Marvoir (d) 2 octobre 2010 à 15:11 (CEST)

Arf, l'exemple de la plaquette de chocolat n'est pas de moi . La première fois, j'ai été surpris par cet exemple amusant. Leon1789 (d) 2 octobre 2010 à 16:58 (CEST)

L'exemple est paru dans un article de Jean-Paul Delahaye, Pour La Science, août 2007. Theon (d) 13 novembre 2010 à 17:30 (CET)

Eh bien, puisque tout le monde semble aimer cet exemple, pourquoi ne pas le mettre dans l'article, si possible avec une référence ? Marvoir (d) 2 octobre 2010 à 17:14 (CEST)

Je suis de la même opinion que Theon, sur l'existence d'une factorisation primaire et sur le chocolat. Pour ce dernier, un dessin explicatif est nécessaire pour permettre une compréhension rapide. Mais pour éviter cet enrobage non mathématique, on peut étudier un arbre binaire sur le même principe que le chocolat.

Exemple : soit $n$ le nombre de noeuds d'un arbre binaire [3], $N_{f}$ son nombre de feuilles et $N_{p}$ le nombre de pères (on a $n=N_{f}+N_{p}$). Montrons $N_{f}\leq N_{p}+1$ par récurrence forte sur $n\leq 0$. Le résultat est évident lorsque $n=0$ ou $n=1$. Pour un entier $n\geq 1$ fixé, supposons le résultat vrai pour les graphes binaires ayant $0,1,2,\dots ,n$ noeuds, et montrons le résultat pour $n+1\geq 2$. En supprimant la racine de l'arbre, on obtient deux sous-arbres avec au plus n noeuds (l'un des deux sous-arbres est vide lorsque la racine a un seul fils) : l'hypothèse de récurrence appliquée aux deux sous-arbres donne $N_{f_{1}}\leq N_{p_{1}}+1$ et $N_{f_{2}}\leq N_{p_{2}}+1$. Or les feuilles de l'arbre initial sont exactement les feuilles des sous-arbres, i.e. $N_{f}=N_{f_{1}}+N_{f_{2}}\leq N_{p_{1}}+N_{p_{2}}+2$. De plus, les pères de l'arbre initial sont d'une part sa racine et d'autre part les pères des sous-arbres, i.e. $N_{p}=1+N_{p_{1}}+N_{p_{2}}$. Au final on a $N_{f}\leq N_{p}+1$, ce qui prouve l'héridité. En rédigeant, je trouve que c'est, encore une fois, un peu lourd... Leon1789 (d) 3 octobre 2010 à 10:56 (CEST)

Depuis ces discussions, l'exemple de l'article (montrer que $\forall n\geq 2\quad D(n)$ où D est la propriété « avoir un diviseur premier », présent depuis la création le 9/9/4) est resté

dans le même état et à la même place jusqu'au 2/4/11 : on prouvait

• (0) $D(2)$
• (1) $\forall n\geq 2\quad {\Big (}2\leq k\leq n\Rightarrow D(k){\Big )}\Rightarrow D(n+1)$

comme exemple de récurrence forte. Le lendemain il a été modifié et déplacé : on prouvait par les mêmes arguments

• (0) $D(2)$
• (2) $\forall n\geq 2\quad {\Big (}2\leq k<n\Rightarrow D(k){\Big )}\Rightarrow D(n)$

sans qu'il soit précisé (et pour cause, cf. ci-dessous) si c'était un exemple de récurrence forte ou de bonne fondation .

Puis cela a été classé comme récurrence forte, par permutation de § le 1/2/12 et n'a pas bougé depuis.

Or (2) tout seul, sans (0) est un exemple de bonne fondation : il équivaut

• à $\forall m\geq 1\quad {\Big (}2\leq k\leq m\Rightarrow D(k){\Big )}\Rightarrow D(m+1)$)

… donc à (0) + (1) Anne (discuter) 18 août 2014 à 22:24 (CEST)

 Proz : quand tu auras un moment, peux-tu passer remettre de l'ordre dans l'article stp ? Anne (discuter) 18 septembre 2014 à 22:08 (CEST)

Ok, si je comprends bien je suis le coupable mais je renonce à l'archéologie wikipedique pour comprendre pourquoi. En fait, pour répondre au début du fil datant de 2010 (que je n'avais pas suivi à l'époque), bien entendu que cette démonstration est (un peu) maladroite, mais le but était de mettre en évidence que la récurrence bien fondée (pas d'initialisation à part) ou le bon ordre, ça peut être effectivement plus élégant que de distinguer les deux cas de la "récurrence forte". D'où le traitement du mêm exemple de plusieurs façons. Un exemple où c'est plus naturel par "récurrence forte" serait bien aussi.

Pourquoi énoncer formellement le principe en 2ème ordre ?

dans le §§ "Énoncé formel du principe de récurrence" le principe est énoncé en 2ème ordre, or que ce soit dans Axiomes de Peano (axiomes) que dans la théorie des ensembles (voir Récurrence transfinie#Sur la classe des ordinaux (thm) c'est un schéma d'énoncés du 1er ordre (çàd qu'on a une infinité d'énoncés), ce qui est normal puisque ce sont 2 théories du 1er ordre (même s'il existe une arithmétique du 2ème ordre).

Aussi je ne vois aucune différence entre : $\forall P\subseteq \mathbb {N} \quad (P(0)\wedge (\forall n\in \mathbb {N} ,P(n)\Rightarrow P(n+1)))\Rightarrow (\forall n\in \mathbb {N} ,P(n))$ et : $\forall P\subseteq \mathbb {N} \quad [0\in P\land \forall n(n\in P\Rightarrow n^{+}\in P)]\Rightarrow \mathbb {N} \subseteq P$ qui sont pour moi 2 énoncés strictement équivalents.

Sinon je pense unir le nouveau §§ que j'ai mis "Sur la force du pas de récurrence à la vue de l'oméga-inconsistance" (sans doute à renommer d'ailleurs ;-) ) avec la section "Justification du principe de récurrence" et la sous-section "Énoncé formel du principe de récurrence".

Via 1/ bien distinguer, ce qui n'est pas fait ailleurs dans l'article : pour tout n P(n) (dont parle essentiellement l'article) de ∀n, P(n) (qui est ce qu'on a dans AP) 2/ rester en langage ordinaire et en 1er ordre (ou alors créer une autre section sur le 2ème ordre). --Epsilon0 ε₀ 22 octobre 2010 à 14:36 (CEST)

Dans la partie que tu as ajoutée, il me semble que les seules hypothèses P(0) et $\forall n,P(n)\Rightarrow P(n+1)$ permettent précisément, pour tout n, de donner une preuve de P(n), mais que c'est justement la conclusion du principe de récurrence (et non ses hypothèses) qui permet d'affirmer plus, à savoir $\forall n,P(n)$. C'est d'ailleurs ce qui est expliqué dans la partie Justification du principe de récurrence. Il vaudrait mieux d'ailleurs placer ta partie après celle-ci. Theon (d) 22 octobre 2010 à 16:15 (CEST)

J'ai déplacé la partie. Sinon je suis d'accord avec toi, mais p.-e. vois-tu quelque chose qui ne va pas (et que je n'aurais pas compris dans ton commentaire) et comme tu me sembles une des personnes les plus avisées sur le sujet, n'hésite-pas à modifier ce que j'ai mis (je ne pourrai sans doute pas vraiment y revenir ce week-end). --Epsilon0 ε₀ 22 octobre 2010 à 16:38 (CEST)

Ayé j'ai compris ce que tu dis et en effet ce que j'ai écrit est mal formulé, ce n'est pas P(0) et $\forall n,P(n)\Rightarrow P(n+1)$ qui impliquent $\forall n,P(n)$, mais P(0) et $\forall n,P(n)\Rightarrow P(n+1)$ + principe de récurrence qui impliquent $\forall n,P(n)$. Je change déjà le titre (qui me plaisait pas trop) et j'y réfléchis (--> là on est un peu comme le célèbre paradoxe de Lewis Carroll What the Tortoise Said to Achilles, qui se résout par une règle de détachement), mais si tu vois quoi faire (et si tu as le temps) let's go. --Epsilon0 ε₀ 22 octobre 2010 à 16:52 (CEST)

Compliquer pour simplifier

« Il faut parfois compliquer un problème pour en simplifier la solution » disait parait-il Paul Erdős. Ça s'applique à merveille à un phénomène qui me fait jubiler quand par hasard je le pratique. Ça peut valoir le coup d'en parler dans l'article (?) mais je n'ai pas de joli exemple en tête ni de source. Je veux dire : parfois il est impossible de prouver $\forall n,P(n)$ par récurrence même forte, mais si on "rentre" vraiment dans le problème, on arrive à trouver une propriété Q(x) plus sophistiquée, telle que $Q(x)\Rightarrow P(x)$ et telle que $\forall n,Q(n)$ soit, lui, facile à prouver par récurrence. Anne Bauval (d) 23 octobre 2010 à 15:02 (CEST)

Un exemple classique : montrer par récurrence que 1+1/4/1/9+...+1/n^2 < 2 est impossible, mais 1+1/4/1/9+...+1/n^2 <= 2-1/n est facile--Dfeldmann (d) 23 octobre 2010 à 15:45 (CEST)

Oui, j'avais pensé à ce genre d'exemple, mais j'en ai déjà rencontré hélas, je perds la mémoire de plus jolis, où quand on trouve Q, on est vraiment content d'avoir compris "en profondeur" ce qui se passe. Anne Bauval (d) 23 octobre 2010 à 16:10 (CEST)

Ceci illustre un fait un peu curieux : dans une démonstration par récurrence, la thèse sert en quelque sorte d'hypothèse. Donc, en rendant la thèse plus forte (ce qui peut sembler la rendre plus difficile à démontrer), on rend aussi l'hypothèse plus forte, ce qui rend la démonstration plus facile. J'ai rencontré un exemple (mais moi aussi, je n'ai plus très bonne mémoire...) où, pour démontrer deux relations par récurrence, le plus simple n'est pas de démontrer chacune des deux relations, mais de démontrer la conjonction des deux relations. En somme, ce principe d'Erdös montre que la règle de Descartes "diviser le problème en parties plus simples" n'est pas toujours bonne en mathématiques, loin de là. Marvoir (d) 23 octobre 2010 à 17:02 (CEST)

Non standard et autres

Gödel n'a pu inspirer Skolem et Robinson, les modèles non standards de Skolen sont construits de façon à conserver certaines propriétés de N (éventuellement toutes) exprimables dans un certain langage en ajoutant des éléments, rien n'à avoir avec l'incomplétude de Gödel. Méthodes entièrement différentes. Ca n'a pas de sens de faire un rapport entre les deux comme cela a été ajouté. Je reviens sur quelque chose de déjà discuté : je pense que de parler d'ensemble des entiers standards comme exemple d'ensemble ne satisfaisant pas la propriété de récurrence pousse à la faute, et c'est une trivialité, que le prédicat être standard ne satisfait pas la propriété de récurrence (qui ne peut être définissable dans le langage d'origine pour cette raison) dans un modèle non standard de la récurrence.

Omega-cohérence : faut-il vraiment parler de ça dans l'article ? C'est une conséquence directe du premier th. d'incomplétude de Gödel. Le choses ne se conçoivent manifestement pas aussi aisément qu'affirmé dans l'article, une phrase comme "il ne suffit pas de démontrer que pour tout n, P(n) [soit P(0), P(1), P(2), ... ] pour démontrer ∀n P(n)" est un contresens (je suppose que le quantificateur porte sur N). 0n ne sait pas écrire une infinité de preuves, évidemment, donc le "il ne suffit pas" ne veut rien dire. Quand on formalise ce genre de choses (omega-règle) c'est plus fort que la récurrence. Proz (d) 27 mars 2011 à 19:26 (CEST)

Suite : après relecture et réflexion je ne vois pas comment sauver le paragraphe omega-cohérence. Il n'a de sens que dans une théorie donnée. Pour n'importe quel mathématicien, une démonstration de P(n) pour tout entier n est une démonstration de $\forall n\in \mathbb {N} \ P(n)$. La question qui est abordée dans ce paragraphe est de savoir si cette démonstration est valide dans une théorie donnée, par exemple dans l'arithmétique de Peano. Elle a un sens, mais c'est incompréhensible comme c'est introduit (voire ça donne des idées fausses). Introduit correctement ça devient tout à fait hors sujet. (au passage : Au passage l'indécidabilité de la conjecture de Goldbach dans par ex. l'arithmétique de Peano, a pour conséquence qu'elle est vraie dans N, donc démontrable dans une théorie plus forte).

Pour parler de modèle non standard de façon intelligible on devrait parler de théorie axiomatique (dans un langage bien défini), un cadre plus naturel est par exemple axiomes de Peano, un article dédié est possible. Proz (d) 27 mars 2011 à 20:34 (CEST)

(écrit avant cette dernière modif) Ben si, puisqu'on est au niveau métathéorique. On dispose effectivement dans PA d'une infinité de preuves de résultats de la forme 2+3=3+2 et d'une preuve de ∀m ∀n m+n=n+m, et c'est même exactement de ça qu'il s'agit quand on parle d'omega-cohérence : dans le cas de Gödel, la certitude (si PA est consistent) qu'on a une infinité de résultats (quasiment triviaux, qui plus est) du type "preuve de P(n)" (où P(n) code pour "il n'y a pas de démonstration de longueur n de 0=1"), mais pas de preuve de Consis (PA), qui serait , justement , codé par ∀n P(n). Ou alors, je ne comprends rien à ton objection... Et pour l'ANS, c'est parel : c'est justement ce genre d'énoncé qui caractérise les entiers non standards... (autrement dit, si une propriété est vraie pour tous les entiers standards, la possibilité qu'elle soit fausse pour un entier non standard implique l'omega incohérence)--Dfeldmann (d) 27 mars 2011 à 20:38 (CEST)

Je sais bien tout ça, mais l'article ne parle pas de PA mais de la récurrence. Le simple fait de distinguer un niveau mathématique et metamathématique ne va pas de soi, cela veut dire que l'on formalise (ce que rien n'indique). Il n'y a aucune raison de se situer dans PA par défaut. Laisser croire que l'on pourrait démontrer pour tout entier n P(n) (en fait une démonstration avec un principe plus fort que la récurrence) mais pas $\forall n\in \mathbb {N} \ P(n)$ est un non-sens si l'on ne précise pas que c'est dans une théorie donnée. Au sens commun, on a bien démontré$\forall n\in \mathbb {N} \ P(n)$ (mais pas dans PA si c'est de PA qu'il s'agit). Ce n'est absolument pas contextualisé, tout ce qui précède est dans un cadre "théorie naïve", et on a vaguement l'impression que démontrer pour une infinité d'entiers n P(n) est une chose simple, ce qui est un contresens, une infinité de démonstrations, une pour chaque entier, est un objet évidemment plus complexe qu'une démonstration.

Pour les constructions type Skolem : la méthode permet de "construire" un modèle non standard élémentairement équivalent au modèle standard. On cherche à conserver les mêms énoncés valides. On a des énoncés qui ne sont pas vrais dans le modèle standard en étendant le langage, évidemment puisque les modèles sont différents, et la méthode ne peut pas en fournir dans le langage initial. Ca n'a pas du tout la même signification. Les outils utilisés n'ont rien à voir avec ceux du th. d'incomplétude. Proz (d) 27 mars 2011 à 21:50 (CEST)

L'axiomatisation des mathématiques étant rarement présentée avant (au mieux) la troisième année de licence, voire le master, je pense que la quasi-totalité des étudiants en mathématiques de ce niveau et peut-être même une bonne partie des professeurs de mathématiques de lycée ne voient pas que l'argumentation naïve "P(0) vrai et P(0) => P(1) donc P(1) vrai et P(1) => P(2) donc P(2) vrai, etc..." ne constitue pas une démonstration de "pour tout n, P(n)", et qu'un axiome est nécessaire (d'ailleurs ce genre de raisonnement se trouve dans certains ouvrages y compris du supérieur pour présenter le principe de récurrence comme évident, ex : Pierre Weis, Xavier Leroy, Le langage Caml, InterEditions (1993) p.54). Le passage sur l'analyse non-standard avait pour but de donner un exemple relativement abordable pour le lecteur de situation qui montre que les choses ne sont pas si simples. Il est donc dommage que toute référence à l'ANS ait été supprimée. Il me paraît essentiel de garder un lien vers l'article Analyse non-standard, ne serait-ce que pour qu'un lecteur tant soit peu curieux ait l'occasion d'élargir son champ de vision. Theon (d) 30 mars 2011 à 10:10 (CEST)

Peut-on se mettre d'accord déjà sur le fait que ce n'est pas une bonne idée de lier ça avec les modèles non standards obtenus par incomplétude ? Voir en:Non-standard model of arithmetic qui distingue me semble-t-il bien les choses.

Pour les questions que tu soulèves : lien avec l'analyse non-standard, pourquoi pas, c'est une jolie théorie, le rapport avec la récurrence est quand même très ténu, et surtout elle est ignorée d'une très grande partie des étudiants enseignants etc, donc ça n'est pas franchement une aide, mais pourquoi pas ?

Peut-être que j'interprète mal, mais tu sembles voir un "raisonnement" dans Weiss-Leroy (en note dans l'article), mais il me semble clair au contraire que c'est une "justification" intuitive, assez courante. On peut discuter le "évident", mais ils précisent bien "jusqu'à un entier donné", c'est tout à fait correct. On se passe difficilement de notre intuition sur les entiers pour axiomatiser les entiers ce qui apparaît clairement dans la justification.

Il me semble que les prof. de lycée insiste énormément sur l'aspect formel de la récurrence au contraire. Les "on voit bien que ça va marcher pour tout entier" ne sont pas tolérés.

Il me semble que la chose à faire remarquer (mais c'est un peu évident), c'est qu'une démonstration est un objet fini. A partir de là l'argumentation "naïve" ne peut constituer une démonstration, il me semble au contraire que c'est quelque chose de bien ancré qu'il faut une nouvelle "règle". Je ne vois pas le danger.

Ce qui me gêne dans l'exemple de l'analyse non standard, c'est que le contexte est complexe, il y a une chose intéressante et non triviale qui est au contraire que les propriétés usuelles (les instances de la récurrence en particulier) sont conservées, donc valide pour le modèle standard même si elles sont démontrées en non standard. Dire que le prédicat "être standard" ne satisfait pas la récurrence est un truisme dans un modèle non standard qui satisfait la récurrence, la conséquence est que l'on ne peut pas définir "être standard" dans le langage usuel. Or toutes ces choses sont complètement mystérieuses hors contexte. L'article ne parle pas un instant du langage dans lequel exprimer la propriété de récurrence (à raison, il existe d'autres articles plus adaptés).

Pour des raisons un peu différentes le paragraphe sur l'omega-incohérence me gêne. Là c'est le fait de trouver un énoncé de la bonne forme qui n'est pas évident, on insiste sur un danger inexistant, et c'est incompréhensible dans un contexte "théorie naïve". Proz (d) 30 mars 2011 à 22:42 (CEST)

Tu dis que l'argumentation "naïve" ne peut constituer une démonstration, et qu'il te semble au contraire que c'est quelque chose de bien ancré qu'il faut une nouvelle "règle". Je crains malheureusement que ce ne soit pas le cas. Outre le livre déjà cité dont je trouve la formulation très dommageable, je peux également citer un article de la revue Tangente de décembre 1987, qui prétend démontrer le principe de récurrence. Quand on regarde la démonstration, on s'aperçoit que l'auteur utilise la propriété selon laquelle si, pour tout n, $x_{n+1}\leq x_{n}-1$ alors $x_{n}\leq x_{0}-n$, et ceci, sans se rendre compte qu'il utilise implicitement une récurrence. Je me souviens aussi d'un de mes étudiants surpris qu'un ouvrage en sa possession prétende démontrer le principe de récurrence alors que je lui avais dit qu'un axiome était nécessaire. Bien entendu, l'ouvrage s'appuyait sur un propriété annexe admise, à savoir le fait que toute partie non vide des entiers admettait un minimum. Bref, j'ai l'impression que, non seulement la nécessité d'une nouvelle règle n'est pas du tout bien ancrée, mais qu'au contraire, beaucoup de personnes pensent que le principe de récurrence est non pas un axiome, mais une propriété évidente, vraie en soi. Theon (d) 2 avril 2011 à 09:51 (CEST)

Bon, je reviens en arrière, parce que j'ai enfin compris ce qui me gênait dans ton argument: Si P(n)=>P(n+1), on a de manière évidente, formalisée ou non, une démonstration de P(42), à savoir P(1)=>P(2)=>...=>P(42) (et le modus ponens), et donc clairement, de même, une démonstration de P(n) pour tout entier n naïf (ou standard) ; il est donc indispensable, pour montrer le problème, de faire apparaître la notion d'entier non standard (et c'est même eux qui te donneront des modèles naturels d'omega-inconsistence, puisque c'est de ça qu'il s'agit). Bon, une façon un peu plus facile de faire consiste à montrer qu'il existe (dans PA) des entiers si grands qu'on ne peut même pas les atteindre par récurrence naïve (voir le théorème de Goodstein pour un exemple explicite, ou les remarques de Borel sur les nombres inaccessibles ; en un sens assez technique, ces entiers sont, de fait, non standards), et donc qu'on ne peut espérer démontrer quoi que ce soit sur eux qu'en ajoutant de nouveaux axiomes (récurrence transfinie par exemple) --Dfeldmann (d) 30 mars 2011 à 23:20 (CEST)

Je ne connais pas les nombres inaccessibles de Borel. La récurrence transfinie et les entiers non standards, c'est indépendant : les méthodes déjà mentionnées s'appliquent, à partir d'un modèle de la théorie des ensembles, on a un nouveau modèle avec entiers non standards (disons extension de ceux du modèle de départ), ou la récurrence ordinaire suffit, et où la récurrence transfinie est valide (avec ces entiers comme ordinaux finis). Je crois être assez d'accord sur le fond avec ce que tu dis au début, pour bien comprendre l'incomplétude il faut parler de modèle non standard de l'arithmétique, et le th. de Gödel fournit directement (par complétude) un modèle d'une théorie omega-inconsistante. Je conteste deux choses : la première qu'il y ait besoin de développements là dessus dans cet article, la seconde la forme du développement actuel. Est-ce que tu pense vraiment que ça ait un sens d'écrire "il ne suffit pas de démontrer que pour tout n, P(n) [soit P(0), P(1), P(2), ... ] pour démontrer ∀n P(n)". Comme si c'était plus simple de faire une infinité de démonstrations. Que veulent dire les ... ? La réalité à ce niveau c'est plutôt que les démonstrations informelles de P(0), P(1), ... sont en fait des démonstrations par récurrence qu'il faut formaliser, ou sont fausses (on ne tombe pas si facilement sur des contre-exemples). Par ailleurs l'arithmétique de Peano, ce n'est pas seulement une restriction de la récurrence, mais du langage. 31 mars 2011 à 00:17 (CEST)

P fonction ou partie de N ?

Je m'aventure assez rarement dans la fin de cet article que je laisse aux spécialistes de la théorie axiomatique des ensembles mais ce changement n'a-t-il pas introduit une erreur ? HB (d) 31 mars 2011 à 07:42 (CEST)

Tu as parfaitement raison ; il faut remplacer "P inclus dans IN" par "P fonction (ou application) allant de IN vers les booléens {vrai, faux}. Mais j'ai pas le temps de m'en occuper, là...--Dfeldmann (d) 31 mars 2011 à 10:11 (CEST)

Peut-être peut-on se contenter de la forme ensembliste, et juste de mentionner la forme avec "prédicat" (personne n'écrit ce qui est écrit actuellement). Proz (d) 31 mars 2011 à 21:47 (CEST)

Question : est-il utile de donner ces énoncés formalisés pour que l'on comprenne qu'il faut quantifier sur un prédicat ou un ensembles ? (les énoncés sont donnés plus haut). Il est par ailleurs probablement utile de le mentionner. Proz (d) 31 mars 2011 à 21:56 (CEST)

Il me semble que cette dernière section vient trop tard. La section sur "Le principe de récurrence et l'ω-incohérence" qui la précède est tellement formalisée qu'elle est peu accessible (mais il faut bien aussi un peu de haut niveau tant qu'il n'intervient pas trop tôt), du coup la formalisation qui suit est peu lue : elle est inutile pour ceux ayant compris la section précédente et les autres ont arrêté de lire depuis longtemps. La preuve que la section est peu lue c'est que l'erreur que j'ai décelée y est présente depuis 2 ans alors que l'article est loin d'être abandonné. Je ne peux pas me prononcer sur l'opportunité de supprimer la première formalisation. Elle est inséparable de son commentaire « La quantification sur P est une quantification qui porte sur une fonction[32], on dit qu'il s'agit d'une quantification du second ordre. C'est cet aspect qui fait de l'axiome de récurrence un axiome très différent des autres axiomes qui régissent les entiers naturels. » qui me dépasse un peu (la section semble opposer les deux versions, l'une serait un principe et l'autre un théorème (?) ). Comme me dépasse un peu toute la fin de l'article. Que signifie par exemple la phrase « Le raisonnement par récurrence se généralise naturellement, sous la forme de la récurrence bien fondée indiquée ci-dessus » alors que l'article ne parle nulle part, en clair, de ce qu'est la récurrence bien fondée en question. HB (d) 1 avril 2011 à 09:30 (CEST)

second ordre : on peut parler directement d'ensemble ou de prédicat, parler de fonction n'est pas nécessaire. le plus compréhensible convient.

"principe" est vague mais ne s'oppose pas à "théorème", ça n'a rien d'essentiel

le "haut niveau" du paragraphe ω-incohérence n'est à mon avis pas maîtrisé (pour plusieurs raisons, cf. ci-dessus), il faudrait effectivement parler de formalisation avant, mais le rapport de la récurrence et de la ω-incohérence (qui a un rapport étroit avec les résultats d'incomplétude) est ténu. Proz (d) 2 avril 2011 à 02:15 (CEST)

Merci HB d'avoir corrigé, je ne sais pas ce que j'avais regardé quand j'avais édité ça. Michel421 _{parfaitement agnostique} 2 avril 2011 à 18:56 (CEST)

Mais je suis assez d'accord que cette formule sur des fonctions n'apporte rien de plus (et en toute rigueur P(n) est une valeur, pas une proposition, il faudrait écrire « P(0)=1 », « P(n)=1 » et « P(n+1)=1 », (ou P(0) = vrai, etc...) non ?) Michel421 _{parfaitement agnostique} 2 avril 2011 à 22:10 (CEST)

En l'absence de réponse depuis 3 semaines, je supprime ce paragraphe. Michel421 _{parfaitement agnostique} 24 avril 2011 à 17:29 (CEST)

Terminologie: hypothèse de récurrence

En lisant cet article il me frappe que le terme "hypothèse de récurrence" est utilisé dans un sense constraire à ce que j'ai toujours vu. Dans cet article, notamment dans "Bon ordre et principe de descente infinie" et "Justification du principe de récurrence", le terme est utilisé pour la totalité de l'implication qu'il faut démontrer (en plus du cas initial) pour faire marcher le raisonnement par récurrence. Mais pour moi l'hypothèse de récurrence est juste l'hypothèse de cette implication (sur laquelle on s'appuye en général au moins une fois dans une preuve par récurence en incitant "par hypothèse de récurence... ") en non pas l'implication entière. C'est vrai, elle forme l'une des hypothèses du principe de récurrence, mais (mis à part dans cet article) c'est peu de gens qui passent leur temps à prouver le principe, mais beaucoup de gens qui l'appliquent, et qui démontrent une instance concrète de l'implication nécessaire, en utilisant son hypothèse "de récurrence". Marc van Leeuwen (d) 28 octobre 2011 à 17:57 (CEST)

Corrigé. Proz (d) 28 octobre 2011 à 18:17 (CEST)

Démonstration du principe

Ca ne me saute pas aux yeux, où est la faille dans cette démonstration révoquée ? Pas compris à quoi réfère le msg de diff --Epsilon0 ε₀ 30 janvier 2012 à 20:05 (CET)

Il n'y a pas de faille dans la démonstration, c'est celle du principe de récurrence à partir de celui du bon ordre ce qui est déjà fait. Cette démonstration ne justifie rien de plus que par exemple : l'ensemble des entiers est le plus petit ensemble contenant 0 et clos pas successeur, ce qui fournit directement la récurrence. C'est parler de "justification" qui ne me semble pas correct. Proz (d) 30 janvier 2012 à 20:13 (CET)

PS. Ah désolé ! J'avais fait une modif vide (vide par erreur) avec justification en boîte de résumé, et j'ai cru qu'elle était prise en compte, d'où ma référence à la boîte de résumé précédente. Donc je laisse un message ici pour expliquer que je suis désolé d'annuler la première intervention de YellowJyst, le problème n'est pas que ce ne soit pas correct, mais que ce n'est pas une "justification" de la récurrence par la théorie des ensembles, mais une démonstration de la récurrence par le bon ordre. Proz (d) 30 janvier 2012 à 20:44 (CET)

(conflit de modif : pour le résumé tu me feras un pater et pour YellowJyst une solution est p.-e. -->) Ok, mais dans ce cas on pourrait réintroduire ce passage dans une section "démonstration du principe en supposant le bon ordre". Mais j'avoue que je ne sais trop où, car en parcourant l'article je ne vois pas clairement où on a explicitement mentionné le principe de récurrence à partir de celui du bon ordre. Ceci car je trouve cette dem. "ensembliste" assez élégante et un peu moins, disons, logico-centrée que la section "Autres formes de récurrence, énoncés équivalents" et suivantes ; ce que peuvent apprécier certains lecteurs. --Epsilon0 ε₀ 30 janvier 2012 à 20:52 (CET)

Elle est dans le paragraphe "Bon ordre et principe de descente infinie de Fermat". Parler d'ensemble ou de propriété ne change pas grand chose, et surtout il ne faut pas donner l'impression en grande partie fausse que c'est une question de "théorie des ensembles". Proz (d) 30 janvier 2012 à 21:27 (CET)

OK. J'ai créé la section "Démonstration du principe de récurrence en supposant le bon ordre de N", avec la dem donnée par YellowJyst (d · c · b), en supprimant la mention à la théorie des ensembles et en ajoutant seulement " Comme E est non-vide et minoré dans l'ensemble des entiers N, vu comme ensemble bien ordonné. J'ai aussi changé "R" en "P", mais là c'est de la convention subjective de notation : "P" pour une relation unaire. ;-). Bon c'est sans doute à améliorer et à mieux contextualiser. --Epsilon0 ε₀ 30 janvier 2012 à 22:18 (CET)

Pas du tout OK, c'est un doublon (que je t'ai pourtant signalé), je ne vois pas l'intérêt. Un raisonnement par l'absurde plutôt qu'une contraposée ? Le titre de la section est douteux (la récurrence sur les entiers utilise aussi que tout entier est 0 ou un successeur (pas besoin de grimper jusqu'à ton ordinal éponyme pour s'en rendre compte). Proz (d) 30 janvier 2012 à 23:15 (CET)

Qu'en pensent les 29 autres qui suivent cet article, est-ce un doublon dommageable, est-ce pertinent, autre ? --Epsilon0 ε₀ 31 janvier 2012 à 07:16 (CET)

avis HB

Pour moi, clairement il s'agit d'un doublon, surtout si la démonstration est placée après la section sur bon ordre et descente infinie. Cependant, le fait qu'Epsilon ne voit pas le lien doit nous interpeller. Il me semble que cela provient du fait que le lecteur moyen cesse de lire un article mathématique quand il prend conscience que celui-ci fait appel a des concepts qui lui échappent (et là je parle plus pour moi que pour Epsilon). Pour moi, j'arrête ma lecture à la section bonne fondation(?) et à la phrase On peut ré-énoncer ce principe de façon à évacuer toute référence aux entiers : 0 et le successeur qui à n associe n+1, au profit de la seule relation d'ordre. dont je ne comprends pas le sens , surtout après les deux points. Bref, je rate ainsi la section bon ordre et descente infinie qui n'attire pas le lecteur s'il ne connait pas la notion de bon ordre. Il me semble pourtant que l'on peut très tôt dire que le principe de récurrence s'appuie sur la propriété Tout ensemble non vide de N possède un plus petit élément et cela avant même que l'on évoque le cas de la récurrence forte. C'est flagrant en lisant l'article puisque, c'est seulement au milieu de la section descente infinie que l'on dit Tiens, au fait, la démonstration directe que la propriété de récurrence se déduit de celle de bon ordre est cependant particulièrement simple. Peut-être pourrait-on envisager un autre plan

4. autres formes de récurrences - énoncé équivalent

intro expliquant qu'il existe de nombreuse variantes s'appuyant sur le principe de bon ordre

4.1. Récurrence et principe de bon ordre

Rappel de def d'un bon ordre (tout ensemble non vide admet un plus petit élément). Vient la dem d'Epsilon (sans distinction entre P et R qui m'est inaccessible) ou celle qui figure dans la section actuelle descente infinie

Pour une propriété P héréditaire (P(n) => P(n + 1) ) et vérifiée en 0, il suffit de considérer le minimum de l'ensemble des entiers ne vérifiant pas celle-ci. Il n'existe que si cet ensemble est non vide. Si ce minimum est 0 cela contredit l'initialisation. Si ce minimum est le successeur n + 1 d'un entier n, alors n contredit l'hérédité. L'ensemble des entiers ne vérifiant pas P est donc vide : tout entier vérifie P.

On explique alors que cette propriété justifie l'existence des autres énoncés et la généralisation à d'autres ensembles que N

4.2 Récurrence double

4.3 récurrence forte

4.4 descente infinie (seulement l'énoncé)

4.5 récurrence dans un ensemble bien ordonné

énoncés (ensembliste et propositionel sous forme d'inégalité - affirmation de l'équivalence entre bon ordre et récurrence forte (ce qui est un résultat plus fort et moins accessible que la simple implication)

Question naïve, si le principe de récurrence s'applique à d'autres ensembles que N, un exemple serait le bienvenu.

mais ma proposition représente un certain chamboulement et si les 28 autres personnes qui suivent cet article proposent d'autres solutions on n'est pas encore rendu; HB (d) 31 janvier 2012 à 08:48 (CET)

Non, non, une solution raisonnable vaut mieux que 28 excellentes, mais incompatibles, donc, sans même chercher à faire mieux, j'approuve pleinement le plan de HB--Dfeldmann (d) 31 janvier 2012 à 09:37 (CET)

Pour répondre à la question naïve : ben je la comprend pas très bien. Sous a forme classique, c'est juste un axiome de Peano ; sinon, y'a des tas d'ensembles bien ordonnés, sans parler de la réscurrence noetherienne, non?--Dfeldmann (d) 31 janvier 2012 à 09:40 (CET)

Tout d'abord, je suis d'accord que l'on ne peut progresser utilement que par une relecture critique de l'article. Je comprends dans ce que tu proposes qu'il faut retarder l'introduction des concepts et vocabulaire plus avancés (bonne fondation : la propriété de récurrence indiquée est celle de relation bien fondée, plus générale que celle de bon ordre).

Dans cette perspective la récurrence double et la récurrence forte viennent avant le bon ordre. Elles se justifient très directement sans en parler. Elles viennent également avant, me semble-t-il "pédagogiquement" (on les utilise très vite dès que l'on a la divisibilité).

L'équivalence est entre "récurrence bien fondée" et "bonne fondation de la relation" (bon ordre pour un ensemble totalement ordonné). C'est essentiellement de la reformulation par contraposée et complémentaire. Mais on peut dire aussi la réciproque 'plus directement" : en montrant par récurrence "forte" que si un sous-ensemble E de N n'a pas de plus petit élément, tout entier est dans le complémentaire de E. Ca n'est pas plus compliqué que le sens direct, excepté que celui-ci se fait aussi facilement par récurrence simple (d'où l'intérêt de refaire la preuve dans la version actuelle). Au passage je trouve que c'est plutôt éclairant de passer par la contraposée de la propriété de bon ordre.

Donc je serai plutôt pour une première partie récurrence (à partir de 0 puis à partir d'un certain rang, puis double, puis forte, énoncé puis justification par récurrence simple (donc équivalence, en précisant bien les conditions si on le mentionne),

Puis bon ordre sur N avec la démonstration d'équivalence (sens direct rédigé comme cité par HB, et réciproque comme amorcé ci-dessus).

Puis descente infinie et récurrence bien fondée

Puis remarques sur le fait que certains énoncés se généralisent avec renvois aux articles bon ordre (et peut-être nombre ordinal), relation bien fondée, énoncés précis des équivalences (conditions), ... Proz (d) 31 janvier 2012 à 10:31 (CET)

oui, on peut placer le bon ordre après la récurrence forte (bien que dans mon cours de TS spé, je place la justification du principe de récurrence simple par le bon ordre avant) à condition de mettre en évidence l'implication : Bon ordre => récurrence simple très abordable en évitant au maximum tout formalisme pour ensuite présenter l'équivalence récurrence forte <=> bon ordre à l'aide de négation et contraposée, résultat plus complet, intellectuellement très joli mais plus difficilement accessible. et terminer ensuite par descente infinie et bonne fondation. Que penses-tu epsilon de cette version qui mettrait plus en évidence la démonstration que tu tenais à ajouter ? HB (d) 31 janvier 2012 à 11:37 (CET)

Ceci me convient tout à fait, d'autant plus que je n'avais pas particulièrement réfléchi à l'ordre précis des sections comme vous venez de le faire. Pour la démonstration de YellowJyst, elle me semblait simplement, disons, jolie, sans même tenter de la rattacher à un plan général ; donc si elle est retirée cela ne me dérange pas plus que cela. Je vous laisse faire, je vois que vous avez une vision plus claire (notamment par retour d'expérience d'enseignement de cette notion) de la progression de l'article que moi. HB : Pour P et R (d'ailleurs j'ai fait une boulette en ne remplaçant pas partout, ce qui est p.-e. ce qui t'a légitimement dérangée), rien de profond : j'ai l'impression qu'on utilise plus "P" (comme Propriété) pour un prédicat unaire et "R" (comme Relation) pour un prédicat avec 2 ou plus d'arguments, comme on dit "soient n un entier et x un réel" et non "soient x un entier et n un réel". Rien de plus ;-) --Epsilon0 ε₀ 31 janvier 2012 à 20:44 (CET)

Il me semble avoir constaté (forcément subjectif) que l'utilisation de la récurrence est (quelques années plus tard) mieux maîtrisée que celle de bon ordre (même si pour la récurrence, dès que la formule de récurrence est un peu compliquée ...). Est-ce que les paragraphes actuels récurrence d'ordre 2 et récurrence forte évitent suffisamment "tout formalisme" ? Est-ce la formulation de la récurrence bien fondée (une seule hypothèse) qui en elle-même semble plus abstraite ? (on peut l'introduire après le bon ordre). Proz (d) 1 février 2012 à 01:29 (CET)

(beaucoup de questions). Il est normal que la récurrence soit mieux maitrisée que le bon ordre car le terme de bon ordre est inconnu au lycée et la propriété "tout ensemble non vide de N possède un plus petit élément" n'est plus explicitement au programme depuis plusieurs années (il en est de même d'ailleurs de la "descente infinie" pas explicitement au programme mais apparaissant dans les sujets de bac). Je suis un dinosaure en la présentant encore aux élèves et en l'utilisant dans mes démonstrations de cours. Sur le formalisme de récurrence d'ordre 2 et forte, il est effectivement presque évité (je ne suis pas sure que l'écriture logique avec parenthèse, crochets, quantificateur, implication logique soit bien maitrisée par tous mais rien de dramatique) - oui la récurrence bien fondée me parait plus abstraite d'une part par la disparition de la condition initiale et d'autre part à cause de la notion de relation bien fondée à mettre donc après le bon ordre que l'on doit définir explicitement "tout ensemble non vide de N possède un plus petit élément". HB (d) 1 février 2012 à 10:48 (CET)

La récurrence descendante

manque. Anne (discuter) 12 mai 2014 à 20:40 (CEST)