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)((y⊆x)⇒(((∀z)((z∈x)⇒(((∀t)((t∈x)⇒((t∈z)⇒(t∈y))))⇒(z∈y))))⇒(y=x)))
— ce n'est, après tout, qu'une version améliorée du principe de récurrence, si on veut.