L'encyclopédie philosophique

Publié en novembre 2017

 

L’induction mathématique ou induction complète est un mode de raisonnement devenu très courant en mathématiques, appelée également raisonnement (ou démonstration) par récurrence ou encore inférence de n à n + 1. En première approximation, et pour en rester à l’arithmétique élémentaire, le principe de ce mode d’inférence est le suivant : supposons que l’on veuille établir que tous les entiers naturels (finis) ont une propriété, disons P. Il est souvent possible d’établir cela « par récurrence » ainsi :

- 1. On démontre que 0 (ou 1…) a la propriété P.

- 2. On fait l’hypothèse (dite « hypothèse de récurrence ») qu’un entier n quelconque, a la propriété P.

- 3. On démontre alors, en se fondant sur cette hypothèse, que n + 1 a la propriété P.

- 4. On en conclut que tous les entiers ont la propriété P.

Intuitivement, le ressort de ce mode d’inférence est que, par 3., il est démontré que la propriété P « est transmise » par le passage d’un entier à son successeur immédiat (+1) ; ou, pour utiliser une autre métaphore, que lorsqu’un entier possède cette propriété, son successeur immédiat en « hérite » (tout comme lorsque une femme et un homme ont les yeux bleus, leurs enfants « héritent » de cette propriété en vertu des lois de l’hérédité). Si donc on a montré à l’étape 1 que 0 (ou 1 ou 2…) a la propriété P, il s’ensuit qu’il en est de même pour son successeur immédiat 0 + 1 (= 1) et donc pour le successeur immédiat de 1, 1+1 (= 2), etc.

A la suite de Couturat (1905/1965, p. 55), on peut énoncer simplement ce mode d’inférence sous les formes suivantes :

- Si le nombre 0 possède une certaine propriété, et si, dès qu’un nombre entier la possède, le suivant la possède aussi, tous les nombres entiers la possèdent.

- Si une proposition est vraie pour zéro et si, dès qu’elle vraie pour n, elle encore vraie pour n+1, elle est vraie pour tous les nombres entiers.

1. Un exemple de démonstration par induction mathématique

Pour fixer immédiatement les idées, nous allons prendre un exemple très simple et classique d’inférence par induction complète.

Soit A[n] la proposition : la somme des n premiers nombres pairs est égale à la somme de n² et de n (ou, ce qui revient au même, au produit de n par son successeur immédiat n + 1)

Dans ce qui suit on admet que le n-ième nombre pair est de la forme : 2n (le premier nombre pair, 2 = 2.1, le deuxième, 4 = 2.2, etc.). Il s’agit donc de démontrer que, quel que soit n, entier naturel, 2 + 4 +…+ 2n = n²+ n (ce que l’on note : ).

- Pour n =1, cela est immédiat : 1² +1 = 2 (pour n = 2, on a 2² + 2 = 6 = 2 + 4, etc.)

- Hypothèse de récurrence : pour un nombre pair m donné quelconque, A[m] est vraie ; i.e. .

- A démontrer : A[m+1] est vraie, i.e., .

On note tout d’abord que : , et puisque 2(m + 1) = 2m + 2, on obtient : .

En vertu de l’hypothèse de récurrence : ; mais (en réorganisant) : , et (en vertu de l’identité remarquable ) : .

On a donc : . CQFD.

- Donc A[n] est vraie pour tout n.

De la même manière, le lecteur pourra s’amuser à démontrer par récurrence que la somme des n premiers nombres impairs est égale à n², sachant que le n-ième nombre impair est de la forme 2n-1 ; ou bien encore que la somme des n premiers entiers est égale à , etc.

2. Rappel historique succinct

Ce mode d’inférence peut sembler très « naturel », et certains historiens des mathématiques ont cru le voir mis en œuvre depuis l’Antiquité, chez Euclide par exemple, ou chez les mathématiciens arabes. Quoiqu’il en soit de ces supputations (qui posent d’intéressants problèmes, évoqués dans l’article principal), il semble que la première formulation explicite de la « mécanique » des preuves pas induction mathématique ait été le fait de Pascal, en 1654, avant donc J. Bernoulli à qui elle est parfois attribuée, en raison de la mention qu’il en fait dans un article de 1686 critiquant J. Wallis (ce pourquoi, dans certains pays l’induction mathématique fut parfois appelée « induction de Bernoulli »).

Dans son Traité du Triangle Arithmétique, écrit en 1654 (mais publié seulement après sa mort en 1665), Pascal, dans la « douzième conséquence » traitant du rapport qu’entretiennent deux coefficients binomiaux « contigus » (peu importe ici les détails techniques, voir l’article développé pour plus de détails), écrit ce qui suit (Pascal, 1654/1998, p. 290) :

« Quoique cette proposition ait une infinité de cas, j’en donnerai une démonstration bien courte, en supposant 2 lemmes.

Le premier, qui est évident de soi-même, que cette proportion se rencontre dans la seconde base ; car il est bien visible que  est à  comme 1 à 1.

Le second, que si cette proportion se trouve dans une base quelconque, elle se trouvera nécessairement dans la base suivante.

D’où il se voit qu’elle est nécessairement dans toutes les bases : car elle est dans la seconde base, par le premier lemme ; donc par le second elle est dans la troisième base, donc dans la quatrième, et à l’infini. »

Dans les traités annexes au Traité du Triangle, Pascal invoque encore deux fois ce mode d’inférence dans des termes très semblables (Pascal, 1654/1998, p. 302 et p. 313).

Il est probable que dans l’esprit de Pascal, de ses contemporains et de leurs successeurs, vu le discrédit dans lequel était tombée la vieille logique scolastique, et son incapacité à justifier les modes d’inférence à l’évidence valides que l’on trouve en mathématiques, un tel mode d’inférence, même s’il fut abondamment utilisé à partir du 17^ème siècle, ne pouvait être justifié que par son évidence intrinsèque ou quelque chose du même ordre ; ce qui était une raison de plus pour ne pas adopter la thèse leibnizienne que les mathématiques sont fondées sur le principe de non-contradiction, tenu à cette époque, mais à tort, pour le principe logique suprême.

Ce n’est qu’à la fin du XIXème qu’il fut codifié sous sa forme actuelle et qu’il devint le cinquième des axiomes de l’arithmétique dans l’axiomatisation qu’en fournit, à la suite de R. Dedekind, le mathématicien italien G. Peano. C’est également à cette époque qu’il fit l’objet d’intenses discussions dans le contexte de la « nouvelle logique » élaborée par les mathématiciens-philosophes G. Frege, en Allemagne, et B. Russell en Grande Bretagne. Au centre de ces discussions, se trouve la question de la légitimité logique d’un tel mode d’inférence: s’agit-il d’un mode d’inférence dont la légitimité est sui generis et non logique, ou, au contraire, un tel mode d’inférence peut-il être logiquement justifié ?

3. L’induction mathématique et la logique

La refonte, et l’extension considérable, de la logique due aux deux auteurs cités ci-dessus, Frege et Russell, fut motivée en grand partie par le projet de renouer, contre l’ « intuitionnisme » kantien, avec la thèse leibnizienne, et cela supposait en particulier que l’on devait pouvoir trouver une place en logique pour le principe d’induction complète. Il n’est donc pas surprenant que Frege, dans son ouvrage fondateur, la Begriffsschrift de 1879, ait eu comme premier objectif de justifier logiquement ce qu’il considère comme étant au fondement de l’« l’induction de Bernoulli », à savoir : « Si x a une propriété F qui est héréditaire dans la f-suite, et si y suit x dans la f-suite, alors y a la propriété F » (Frege, 1879/1964, p. 63-64, théorème 81 ; une f-suite est une suite déterminée par une fonction (relation) f, par ex. la suite des entiers naturels est une suite déterminée par la fonction successeur, f(n) = n + 1). Frege pensait avoir ainsi posé le premier jalon d’une entreprise considérable : montrer que les mathématiques ne sont qu’une branche de la logique (ce que l’on appelle la thèse « logiciste »). Par la suite, Russell soutiendra que le principe d’induction complète n’est pas un principe (comme dans l’axiomatisation due à Peano) et que sa validité n’a rien de mystérieux, car il n’est qu’une définition : «  Nous savons maintenant que (…) l’induction mathématique est une définition, pas un principe. (…) Nous définissons les « nombres naturels » comme étant ceux auxquels peuvent s’appliquer les preuves par induction mathématique, i.e. comme ceux qui possèdent toutes les propriétés inductives » (Russell, 1920/1993, p. 27).

4. En guise de conclusion : débats autour de l’induction mathématique ; Poincaré, Wittgenstein

Le grand mathématicien français, H. Poincaré, s’éleva vigoureusement contre une telle manière de voir les choses. Pour lui, le raisonnement par récurrence, qui est à ses yeux au cœur des mathématiques, est irréductible à la logique car la conclusion qu’on en tire enveloppe l’infini et il affirmait, dans un article fameux de 1894, « Sur la nature du raisonnement mathématique », que « la règle du raisonnement par récurrence est irréductible au principe de contradiction. » Et il ajoutait : « Cette règle, inaccessible à la démonstration analytique et à l’expérience, est le véritable type du jugement synthétique a priori. … elle n’est que l’affirmation de la puissance de l’esprit qui se sait capable de concevoir la répétition indéfinie d’un même acte dès que cet acte est une fois possible » (Poincaré, 1902/1968, p. 41). Par la suite, lors de sa polémique contre Russell et Couturat dans les années 1900, il ne cessa de faire remarquer que toute tentative de réduire les mathématiques à un système axiomatisé, ou à la logique axiomatisée, présupposait nécessairement l’emploi du principe d’induction et ne pouvait donc prétendre intégrer et justifier ce dernier. Cela allait de pair, dans son esprit, avec la thèse que les entiers naturels sont une donnée primitive, dont toute prétendue définition ne peut qu’être circulaire.

Comme on le voit, les discussions autour du principe d’induction, touche aussi bien au rôle de l’intuition en mathématique que, plus spécifiquement, au statut des entiers naturels et même plus généralement à la considération de l’infini, actuel ou potentiel. Car, comme notre exemple le montre, la conclusion du raisonnement par récurrence est de la forme « pour tout n, P(n) » (plus exactement : x (Nx Px), avec « Nx » = « x est un entier naturel »). Cela semble supposer qu’il y a sens à évoquer la totalité infinie « actuelle » des entiers naturels (qui sont, eux, tous finis, notons le bien), autrement dit que l’on accepte que considérer que les entiers naturels forment un ensemble qui a un « cardinal » bien déterminé, que depuis Cantor on note (lire : aleph 0), et qui est le plus petit cardinal infini. Ainsi, logiquement, une proposition comme « tous les français vivant le 10 juin 2016 à 10h du matin sont grincheux » serait de la même forme que : « tous les entiers naturels sont factorisables en nombres premiers », c’est à dire de la forme : x (Px Qx).

C’est, pour une part, contre cette manière de comprendre les choses que s’élevait Poincaré, lui qui récusait l’« infini actuel », et que, plus tard, dans les années trente, mais sur la base d’autres considérations, le philosophe autrichien L.Wittgenstein se dressera, soulignant que le « pour tout n… » de la conclusion d’un raisonnement par récurrence, n’a pas du tout la même « grammaire » que le « pour tout x… » d’une proposition comme celle concernant les français grincheux. Par exemple, dans ce dernier cas, si cette proposition est fausse, c’est qu’il y a au moins un français qui n’est pas grincheux le 10 juin 2016 à 10h du matin, alors que fausseté de « pour tout n, la somme des n premiers entiers est égale à n.(n+1) » ne tient pas à ce qu’il existerait un entier m, tel que la somme des m premiers entiers ne serait pas égale à m.(m+1) ; elle conduit à chercher une autre formule.

Bibliographie

J. Bernoulli, « Demonstratio rationum, quas habent series numerorum naturali progressione sese insequentium… », Acta Eruditorum, sept 1686, p. 360.

L. Couturat, Les Principes des Mathématiques (1905), G. Olms, Hildesheim, 1965, p. 55.

G. Frege, Begriffsschrift und andere Aufsätze, (I. Angelelli, éd.) Hildesheim, G. Olms, 1964.

B. Pascal, Traité du triangle arithmétique (1654), in Œuvres complètes (M. Le Guern, éd.) t. 1, Paris, Gallimard, Bibliothèque de la Pléiade, 1998.

H. Poincaré, La science et l’hypothèse (1902), Paris, Flammarion, 1968.

B. Russell, Introduction to Mathematical Philosophy (2^ème édition, 1920), New-York, Dover Publications, 1993.

L. Wittgenstein, The Big Typescript, TS 213, (texte allemand avec une traduction anglaise par C. G. Luckardt et M. A. E Aue), Oxford, Blackwell, 2005.

François Schmitz

Université de Nantes

francois.schmitz@univ-nantes.fr