Rédaction récurrence

Par exemple avec une abréviation ça donne :
Pour $n$ entier naturel on note $H_n$ : "la somme des $n$ premiers entiers naturels est $\frac{n(n+1)}{2}$".
$H_1$.
Pour tout entier naturel $n$, si $H_n$ alors $H_{n+1}$.
Donc par récurrence, pour tout entier naturel $n$, $H_n$.

En fait, la rédaction en langage naturel est simple (quand on a trouvé les preuves des différentes parties) :
Démontrons par récurrence que ...(ici, une propriété dépendant d'un entier que je note n)
.... (première partie) donc la propriété est vraie pour n=0 (ou 1, ou le premier entier pour laquelle elle est vraie)
.... (deuxième partie, où on prouve que si la propriété est vraie pour un entier n elle est vraie pour l'entier suivant n+1)
Donc la propriété est vraie pour tout entier au moins égal à 0 (ou 1, ou le premier entier pour laquelle elle est vraie).

Suivant la difficulté à énoncer la propriété, on l'écrira à chaque étape, ou on la désignera, ou on lui donnera un nom; parfois même, on laisse le lecteur comprendre, il est supposé connaître la méthode.

Par exemple (*), démontrons que tous les termes de la suite définie par $u_0=1,\, u_{n+1}=3u_n-1$ sont des entiers :
Par récurrence : $u_0$ est un entier, si $u_n$ est entier, alors $3u_n-1=u_{n+1}$ est aussi un entier, donc tous les termes de la suite sont des entiers.

Cela suffit largement, inutile d'épiloguer.

En pratique, le problème est généralement dans les deux parties, surtout la deuxième. Là, on a des preuves classiques à rédiger si nécessaire.

Cordialement.

(*) A un niveau bac+2, on laisse le soin au lecteur de faire ce raisonnement élémentaire : "on montre par une récurrence évidente que tous les termes de la suite sont entiers.

C'est cette présentation de @Foys qui m'apparaît la plus claire.

La rédaction serait simple : je note E l'ensemble des entiers tels que...
Je prouve qu'il y a $0$ dedans.
Je prouve que si $n$ est dedans, alors $n+1$ aussi.

Soulevé-je un marronnier ?

Le problème dans le secondaire relève-t-il du terme "ensemble" qui fait peur à tout le monde ?

Math Coss,

Où ai-je laissé la nature de n dans le vague ?
Ta "propriété" ne dépend pas d'un entier n, elle le fixe. Donc, sauf à pinailler sur le français, tu passes à côté du problème.
Mais c'est vrai que sur ce forum, on pinaille facilement sur ce que disent ceux qui aident plutôt que d'aider soi-même ...

Cordialement.

Ce n'est pas une bonne idée de laisser implicites les quantifications universelles.

Exemple vécu plusieurs fois : un étudiant écrit « si la propriété est vraie pour un certain $n$, alors elle est vraie pour $n+1$ » ; je lui demande de préciser si ce $n$ est spécial ou quelconque, si c'est vrai pour tout $n$ ou pas, bref, s'il faut mettre $\forall n$ ou $\exists n$ ; la réponse est confuse et montre que la clé de l'hérédité n'est pas comprise ($\forall n,\ H_n\Rightarrow H_{n+1}$) (éventuellement, pour préciser, l'étudiant répond entre autres : « je suppose $H_n$ vraie pour tout $n$ »).

La quantification universelle implicite n'est pas toujours comprise. De plus, ce n'est pas une bonne idée d'utiliser un symbole (ici, $n$) en laissant à la lectrice le soin de déterminer qui il est, où il vit, comment il est choisi, s'il est sujet à des conditions, etc.

Bref, l'ambiguïté est nuisible. Cela ne coûte rien d'expliciter les quantificateurs (rien n'oblige à utiliser les symboles $\forall$ et $\exists$).

C'est pourquoi je crois que la meilleure façon de présenter une preuve par récurrence d'une propriété de la forme « pour tout $n$ entier naturel, $H_n$ » est :

• [...] donc $H_0$ est vraie.
• Soit $n\in\N$. Supposons $H_n$ vraie. [...] Donc $H_{n+1}$ est vraie.
• Par récurrence, $H_n$ est vraie pour tout $n$.

Effectivement, quand on rédige "les maths pour les nuls", on écrit tout, y compris ce qui est évident. Des générations d'élèves et d'étudiants ont fonctionné sans qu'on ait besoin de préciser que quand on dit "soit n un entier" cet entier était un entier quelconque, non particularisé, c'était ce qu'on écrit en vocabulaire formel avec un quantificateur. Il est vrai qu'ils avaient appris dès l'école primaire, puis confirmé ensuite le rôle de l'article indéfini (*) "un". J'ai connu, pendant ma carrière d'enseignant, une insistance sur le "quelconque", le sens de l'article "un" commençait sans doute à se perdre dans l'esprit des IPR, pourtant formés comme moi. Il fallait dire "un entier quelconque", sorte de pléonasme. Maintenant il faudrait (sur ce forum, bizarrement pas sur tous) mettre des quantificateurs.
Problème : Je rédige ma preuve ainsi :
$u_0$ est un entier
Si, quel que soit l'entier n, $u_n$ est un entier ...
Voilà, l'insistance sur la quantification a fourni l'occasion de dire n'importe quoi !!! Et on le rencontre maintenant souvent chez les élèves de TS qui "veulent bien faire".

Enfin, Math Coss, ta rédaction avec un "soit $n\in \mathbb N$" dit la même chose en fait que celle que j'écrivais. Tu as simplement formalisé là où j'écrivais en bon français. Et ce qui m'amuse, c'est que les mathématiciens, quand ils veulent se faire comprendre, écrive en bon français.

Cordialement.

(*) comparer le sens grammatical de "indéfini" avec la quantification universelle.

La locution « soit $n$ un entier » dont tu parles ici est précisément ce qui me semble manquer dans la formulation de ce message.

L'écriture erronée « Si, quel que soit l'entier $n$, $u_n$ est un entier... » n'est pas empêchée par une rédaction « si $u_n$ est un entier pour un certain $n$ », témoin leurs fréquences respectives dans les copies des élèves et étudiants et dans les cours de leurs professeurs. Elle a au moins l'avantage d'être assez précise (assez fausse) pour être réfutée, au contraire d'autres rédactions erronées qui n'ont au fond aucun sens. Ce n'est pourtant pas du tout celle que je propose, comme tu l'auras constaté.

Quand on écrit « un $n$ », on laisse au lecteur le soin de préciser le statut, l'ordre et la dépendance des variables. En se forçant à écrire « Soit $n$ » avant d'utiliser une phrase qui comporte un $n$, on n'écrit pas plus de texte mais on explicite les choses : que du bonus.

La règle simple

N'utilise pas une variable avant de l'avoir définie (nommée, déclarée, introduite).

évite bon nombre d'abus et d'ambiguïtés et permet de préciser le discours. C'est plus facile de réfuter une erreur si nécessaire.
Les rédactions de récurrence avec du « supposons que $H_n$ soit vraie pour un [certain] $n$ » vont à l'encontre de cette règle. Le fait que le quantificateur intervienne après le « si » est un facteur favorable à l'interprétation erronée « supposons que pour tout $n$, $H_n$ soit vraie ».

Gérard a écrit:

comparer le sens grammatical de "indéfini" avec la quantification universelle.

Deux exemples.

• « Si un réel est le carré d'un réel, il est positif. » Deux traductions raisonnables :\begin{align*}&\forall y\in\R,\ y^2\ge0\;;\\
  &\forall x\in\R,\ \bigl((\exists y\in\R,\ x=y^2)\Rightarrow x\ge0\bigr).
  \end{align*}De façon amusante, le $y$ est précédé d'un $\forall$ dans un cas et d'un $\exists$ dans l'autre...
• « Soit $x$ un réel. Alors $\sin x=0$ si et seulement si $x=2k\pi$ pour un entier $k$ (quelconque). »
  Ici le « un » a plutôt une valeur existentielle. Enfin... si $\sin x=0$, il existe $k$ tel que $x=k\pi$ ; réciproquement, pour tout $k$ entier, $\sin(k\pi)=0$.
  
  Bien sûr, $x$ étant donné, il est faux que $x=2k\pi$ pour tout $k$. Pourtant, il arrive régulièrement que des étudiants le proposent pour préciser ce qu'ils veulent dire par « $x=2k\pi\quad(k\in\Z)$ ».

Gérard a écrit:

Enfin, Math Coss, ta rédaction avec un "soit $n\in\N$" dit la même chose en fait que celle que j'écrivais. Tu as simplement formalisé là où j'écrivais en bon français.

En bon français mais pas dénué d'ambiguïtés pour les étudiants que j'ai (que des nuls ?). Encore heureux que nous écrivions à peu près la même chose.

Flûte ! Là tu insistes lourdement, cher @Math Coss.
Tout est clair dans cette discussion. D'ailleurs, je crois que tout le monde (toi et Gérard) rédige comme cela, je veux dire en écrivant "soit $n$ ...".

Une remarque : Quels que soient les rédactions proposées, voire imposées, par le professeur, on trouvera les mêmes erreurs dans les copies. Une façon de dire que de préciser "on voit ça dans des copies" n'est pas un argument pour dire que les professeurs auraient donné de mauvais conseils.

J'en reste là puisque, je le répète, tout est clair.
Et si ce n'était pas le cas, des nouvelles questions devraient venir.

@cc
Quelle intervention ! J'espère que tu plaisantes à 200% car là tu me fais penser au prof qui récite le théorème de Pythagore en rappant "pour intéresser" les élèves.

christophe c
C'est une catastrophe ce truc là, ils sont indécrottables.
C'est pour ça que j'aime bien les cours de logique classique où $\forall$ et $\implies$ ne sont pas mentionnés (ou introduits comme notions dérivées) comme ça il y a pas ce foutage de gueule insupportable.

[Inutile de reproduire le message précédent. AD]

Bonsoir,

Voici ce qu'en pense Saint Bourbaki. Selon l'auteur, il s'agit d'un critère (métamathématique) déductif. L'on regardera surtout la remarque.

Cordialement,

Thierry

Dom, il n'est pas étonnant qu'un fil sur la récurrence parle de quantificateurs ! C'est un des deux points clés, l'autre étant l'implication (en particulier la différence entre « $P\Rightarrow Q$ » et « $P$ donc $Q$ »).

Par ailleurs, tu fermes les yeux sur d'autres emplois de l'article indéfini. Par exemple...

Dom a écrit:

"Si quelqu'un brûle un feu rouge, alors il est passible de...".

L'article « un » devant « feu rouge » n'est pas clairement un quantificateur universel : s'il existe un feu rouge brûlé par quelqu'un, alors... (Certes, quel que soit le feu rouge brûlé, il y aura passibilité.)

Il y a des différences (donc des pièges) partout quand on passe de la langue « naturelle » à la langue mathématique (tiens, un autre exemple^© associé à « et » : « cette robe est bleue et rouge », qui ne veut pas dire « cette robe est bleue et cette robe est rouge » : les règles correspondantes ne s'appliquent donc pas) et cette dernière n'est intuitive que pour les "matheux". Or les enseignants s'adressent à des "matheux-en-herbe", il me semble qu'il est de notre devoir d'être attentifs à ces différences et de limiter autant que possible les ambiguïtés. Surtout quand ça ne prend pas plus de temps ni de mots.

René Cori croit que les démons existent ?

Rhaaa 0ka, tu es incorrigible ce soir.

Math Coss a écrit:

Ce n'est pas une bonne idée de laisser implicites les quantifications universelles.

Exemple vécu plusieurs fois : un étudiant écrit « si la propriété est vraie pour un certain $n$, alors elle est vraie pour $n+1$ » ; je lui demande de préciser si ce $n$ est spécial ou quelconque, si c'est vrai pour tout $n$ ou pas, bref, s'il faut mettre $\forall n$ ou $\exists n$ ; la réponse est confuse et montre que la clé de l'hérédité n'est pas comprise ($\forall n,\ H_n\Rightarrow H_{n+1}$) (éventuellement, pour préciser, l'étudiant répond entre autres : « je suppose $H_n$ vraie pour tout $n$ »).

Je n'ai pas tout suivi, mais ne suffit-il pas de dire à cet étudiant qu'il ne faut pas confondre : $$
\forall n (H_n\Rightarrow H_{n+1})$$ (principe de récurrence) et $$
(\forall n,\ H_n) \Rightarrow H_{n+1}$$ (d'ailleurs mal définie) ou $$
(\forall n,\ H_n) \Rightarrow (\forall n,\ H_{n+1})
$$

idem a écrit:

C'est pourquoi je crois que la meilleure façon de présenter une preuve par récurrence d'une propriété de la forme « pour tout $n$ entier naturel, $H_n$ » est :

• [...] donc $H_0$ est vraie.
• Soit $n\in \mathbb{N}$. Supposons $H_n$ vraie. [...] Donc $H_{n+1}$ est vraie.
• Par récurrence, $H_n$ est vraie pour tout $n$.

Le second item m'a l'air exactement équivalent à (principe de récurrence avec quantificateur universel) : $$\forall n \in \mathbb{N} (\ H_n\Rightarrow H_{n+1})$$ lorsque l'étudiant met les bonnes parenthèses...

Hum je me suis endormi. Je disais :

La méthode de l'hypothèse auxiliaire de Bourbaki c'est simplement dire "supposons $A$" et ajouter pour un temps $A$ aux axiomes, puis prouver $B$, et en déduire $A\Rightarrow B$ dans la théorie de départ.

La méthode de la constante auxiliaire : si on connaît un objet $T$ qui vérifie $A(T)$, on dit "soit $x$ un objet tel que $A(x)$" et on ajoute pour un temps $A(x)$ aux axiomes, puis on prouve $B$, et on en déduit $B$ dans la théorie de départ.
Alors on pourrait se dire "mais si on connait un tel objet $T$ pourquoi on va s'embêter avec ce $x$ !", mais en général ce $T$ est de la forme $\tau _x(A(x))$ (par exemple dans le scan de Thierry) et la skolemisation ça va 5 minutes mais on en veut pas dans les tomes suivants, alors on se débrouille pour utiliser les mêmes formulations que tout le monde.

Pour la remarque en petit caractère, Bourbaki suggère de démontrer seulement l'implication (sans le quantificateur au début) : $n$ est ici une lettre et elle n'est pas une constante (c'est à dire que elle ne figure pas dans un axiome explicite). Un axiome explicite c'est un axiome qui ne vient pas d'un schéma d'axiomes, eux c'est les axiomes implicites. La théorie des ensembles est une théorie sans constante mais on travaille souvent dans des théories avec des constantes, par exemple pour la méthode de l'hypothèse auxiliaire quand on ajoute un axiome $A$ qui contient des lettres.
Quand on a l'implication, on en déduit l'assertion complète avec le quantificateur universel au début : il n'est pas sous-entendu dans l'implication seule, en logique moderne on dirait ici que $n$ est une variable libre dans l'implication.

C'est un des critères de Bourbaki : quand on a un théorème $R(x)$ et une lettre $x$ qui n'est pas une constante, alors on en déduit que $(\forall x) R(x)$ est un théorème (tout ça dans une théorie donnée).
Un des plus grave contre-sens qu'on puisse faire en lisant Bourbaki c'est de pas bien comprendre cette histoire de constante et de croire que on peut toujours rajouter un $\forall$ au début d'un théorème et que ce sera encore un théorème, voire d'interpréter ce critère comme une équivalence $R(x) \Leftrightarrow (\forall x) R(x)$. Quelqu'un avait fait cette erreur sur le forum il y a un an je crois et j'ai pas osé lui dire que il devait reprendre sa lecture au début parce il n'avait pas pu comprendre une seule démonstration de Bourbaki : c'est comme s'intéresser à l'histoire des guerres de l'antiquité en croyant qu'ils avaient la bombe atomique.

Bon tout ça c'est un peu compliqué, c'est sans doute pour ça que christophe disait qu'il faut chercher très longtemps pour faire mieux que sa présentation avec un démon.

@dom. Je ne plaisante pas.

Je crois que tu n'as pas compris mais (je n'ai pas relu) il me semble que j'avais bien rappelé de relire la définition du jeu universel de la verite (attention pas celui de la preuve).

Et surtout ça n'a rien à voir avec des histoires d'animation de soirées de ski. Ce n'est pas pédagogique. C'est LA SEULE DEFINITION dont on dispose OFFICIELLEMENT des phrases quantifiées. Du coup je pense que tu as trop vite sauté sur ton antipedagogisme et loupé une info

Mais de mon , retrouver des liens n'est pas pratique . J'essaierai. Essaie peut être Google et tape "île déserte" , "protocole scientifique pour se mettre d'accord quand personne n'a la charge de la preuve", etc.

Le démon est juste l'adversaire face à qui par DÉFINITION (sur l'île déserte) si tu gagnes contre son x choisi, le protocole te met gagnant au jeu forall x.

En mode résumé, dans l'énoncé "tous les triangles isocèles sont équilatéraux" le démon choisit un triangle isocèle qui est pas équilatéral. Dans l'énoncé "tout nombre est inversibles" le démon choisit 0, etc.

Tu aurais vraiment besoin de te renforcer en logique mathématique et en plus je suis sur que ça te plairait.

«  je peux te prouver que tu utilisais, disons il y a moins de dix ans, le mot "quelconque" à l'oral, et aussi que tu écrivais des phrases "si...alors..." sans quantifier les objets »

@Dom , c’est parce qu’ « avant le forum » , @cc ne pratiquait pas les mathématiques, en tout pas « essentiellement » comme il me l’a dit en privé quand je lui ai demandé s’il était sérieux.

......

De toute façon, que ce soit avant ou après et en dépit de la longueur des messages, il ne dit jamais rien, enfin « presque » .

Je ne comprends pas trop sur quel pied de amathoue j'ai marché pour qu'il charge comme ça mais bon je suis en vacances à la montagne je ne vais pas fouiller ma mémoire :-D

Yep, allez n'oublie pas que ce sont les derniers jours...et qu'ils raccourcissent !

Je dis ça a tout le monde d'ailleurs !

À bientôt.

Bonsoir,

Dom, merci pour ton post :

http://www.les-mathematiques.net/phorum/read.php?16,1696216,1696538#msg-1696538

J'avais rencontré ce genre de questions justement avant d'établir la formulation logique valide de l'AO (argument ontologique). En ce temps là, Cc voyait déjà le "démon" dans l'existence divine (il semblait me voir formuler l'existence d'un concept $D \Rightarrow E(D)$ là où j'écrivais une existence d'objet $\forall x (D(x) \Rightarrow E(x))$.

Cc : http://www.les-mathematiques.net/phorum/read.php?16,1696216,1696426#msg-1696426

Entre autres vices, tu insulterais certains de tes élèves...d'"intégristes" qui ne cogiteraient pas ? C'est très aimable. Quid de ton intégrism... pardon, "intégrité" professionnelle ?

Thierry :

L'objectif est d'utiliser la méthode de l'hypothèse auxiliaire (appelée ici hypothèse de récurrence). Remarquons au passage que l'on travaille dans une théorie plus forte que $\mathscr{T}$ dont $n$ est clairement une constante.

Tu ne voulais pas dire "une théorie plus forte que l'arithmétique dont $n$ est clairement une constante" ?

Par ailleurs, en restant dans la théorie arithmétique, la propriété :

$$(n\in\Bbb{N}^*\mbox{ et }R(n))\Rightarrow{R(n+1)}$$

n'est-elle pas équivalente à :

$$\forall n \in\Bbb{N}^*(R(n) \Rightarrow{R(n+1)})$$

Bonne nuit.