David Madore's WebLog: C'est dur, la récurrence

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entry #0305 [older|newer] / Entrée #0305 [précédente|suivante]:

(lundi)

C'est dur, la récurrence

En mathématiques, pour démontrer par récurrence une proposition qui dépend d'une variable n (parcourant les entiers naturels), on commence par démontrer la proposition pour la valeur 0 de n (initialisation de la récurrence), puis on démontre que la proposition est hériditaire, c'est-à-dire que, pour tout n, si la proposition est vraie pour n alors elle est encore vraie pour n+1. Le postulat de récurrence assure alors que la proposition est vraie pour toute valeur de n (ce qui se conçoit fort bien, intuitivement : l'initialisation assure qu'elle est vraie pour 0, puis l'héridité permet de déduire le cas 1 du cas 0, le cas 2 du cas 1, et ainsi de suite).

La subtilité concerne la rédaction, et la logique derrière celle-ci. J'ai écrit, ci-dessus : pour tout n, si la proposition est vraie pour n alors elle est encore vraie pour n+1. Ce n'est pas du tout pareil que si j'avais écrit si pour tout n la proposition et vraie pour n alors [pour tout n?] elle est encore vraie pour n+1. Quand on veut prouver l'héridité de la proposition, on doit supposer que la proposition est vraie au rang n pour un certain entier n, et non pas qu'elle est vraie au rang n pour tout entier n (sans quoi il n'y aurait plus rien à démontrer, puisque c'est exactement la conclusion qu'on cherche à atteindre au final !).

Je suis tellement habitué au raisonnement par récurrence (et, de façon générale, aux principes d'induction de ce genre, car il y en a de beaucoup plus compliqués) que j'ai du mal à comprendre comment cette histoire peut poser un problème. Mais manifestement il y en a un : sur un tas de copies, même si tous n'ont pas choisi de tenter une récurrence pour prouver ce qu'on leur demandait (et on pouvait très bien faire sans), seuls deux étudiants ont réussi à faire une récurrence correcte tout du long, et encore, seule une est vraiment irréprochable. Pourtant, j'ai lourdement insisté sur ces difficultés en TD ; j'ai choisi de changer la lettre désignant la variable pour présenter l'héridité de la récurrence, peut-être était-ce un bon choix (ça évite d'écrire des choses comme maintenant n vaut n+1 qui causent d'immenses confusions), peut-être pas (ils oublient souvent de remplacer la variable partout où elle apparaît, et ils sont alors perdus).

On leur parle de logique et de quantificateurs, mais on pourrait tout aussi bien parler de théosophie pour ce que ça évoque chez eux : les quantificateurs sont quelque chose d'absolument abscons, qu'on met au feeling, et parfois on tombe juste et souvent non. Ils savent faire certaines manipulations formelles (notamment, la grande majorité d'entre eux a compris comment écrire la négation d'une affirmation commençant par des quantificateurs), et ils comprennent le sens des quantificateurs dans certains cas faciles (du style, pour tout x, x²+1 est positif, ça, ils voient ce que ça veut dire), mais dès que le motif devient un peu complexe, les manipulations formelles ne leur suffisent plus, et leur intuition ne leur dit rien du tout. C'est déprimant. Ils ont énormément de mal à apprendre (ne serait-ce que par cœur, sans comprendre) la définition de la limite, parce qu'il y a trois quantificateurs qui se succèdent et qui ne sont pas n'importe quoi. Dans ces conditions, il est hors de question de leur écrire formellement le schéma de récurrence,

((P(0))∧((∀n)((P(n))⇒(P(n+1)))))⇒((∀n)(P(n)))

[Ci-dessus, « ∀ » est le symbole du quantificateur universel, « ∧ » est un et logique, et « ⇒ » est une flèche d'implication.] Et si on l'écrivait, il faudrait expliquer pourquoi quand il s'agit de voir l'héridité (« (∀n)((P(n))⇒(P(n+1))) »), on doit supposer pour un certain n que P(n) est vrai alors que c'est écrit « pour tout n ». Et d'ailleurs il faut aussi expliquer que ce n'est pas pareil de supposer pour un certain n que P(n) est vrai que de supposer que pour un certain n P(n) est vrai ! Parfois j'ai l'impression de jouer à la scholastique byzantine, c'est triste.

S'il y a des mathématiciens qui rigolent in petto dans le fond de la salle, je leur conseille de se demander quel est le sens profond de l'affirmation suivante :

Si x est un ensemble et y une partie de x, et si on suppose que tout élément z de x vérifiant la propriété que « tout élément de x qui appartient à z est dans y » est dans y, alors y est x tout entier.

Soit, avec des symboles : (∀x)(∀y)((yx)⇒(((∀z)((zx)⇒(((∀t)((tx)⇒((tz)⇒(ty))))⇒(zy))))⇒(y=x)))

— ce n'est, après tout, qu'une version améliorée du principe de récurrence, si on veut.

↑Entry #0305 [older|newer] / ↑Entrée #0305 [précédente|suivante]

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées