Cas de la récurrence, et premières idées sur les règles non récursives
Lorsque l’on se
penche sur la règle mathématique qu’est la récurrence, ou l’addition, on
s’aperçoit rapidement que ces règles expriment une certaine généralité :
elles disent qu’en appliquant un certain procédé, un résultat précis sera obtenu
(et si une règle n’exprimait pas une certaine généralité, elle ne serait pas
vraiment une règle). Si, pour tout entier naturel, on a bien $P(0)$, et qu’il existe un entier naturel tel que, si $P(n)$ est vraie, que $P(n) \Rightarrow P(n+1)$, alors $P(n)$ est vraie pour tout entier naturel (par la
règle du modus ponens). Appliquer cette règle au calcul d’une somme,
d’un produit ou autre opération sur les entiers permet de vérifier qu’une
certaine proposition est vérifiée. La récurrence nous dit qu’il en est ainsi
pour tout entier naturel. Pour autant, la récurrence est une règle de raisonnement
(contrairement à l’addition), et c’est ce qui va nous occuper dans un premier
temps.
Pourtant, est-ce que cette généralité doit porter sur un
ensemble fini, comme dans le cas avec la récurrence ? Par exemple, en
géométrie, le théorème de Pythagore énonce qu’il en va pour tout triangle que
le carré de l’hypoténuse est égal au carré de l’un et de l’autre côté. Bien
sûr, on a envie de dire qu’un théorème n’est pas une règle. Pourtant, ce que
dit le théorème est une règle lorsqu’on utilise son contenu de manière
normative pour conduire un raisonnement autre (se servir de ce théorème pour
calculer l’aire, par exemple). Ainsi, tout théorème mathématique ne devient-il
pas une règle lorsque l’on s’en sert pour raisonner ? Il semble alors que
ce deuxième genre de généralité, qui réside dans l’application du
théorème, ne soit pas vraiment identique à une généralité héréditaire
sur les entiers. Comment alors qualifier cette généralité d’application ?
Est-elle si différente d’une règle portant sur des entiers naturels ? En
effet, bien que la récurrence porte sur le domaine fini des entiers naturels,
il reste qu’elle est également appliquée lors des raisonnements. Comment
alors bien caractériser la généralité propre aux règles mathématiques ?
Les réflexions proposées par Wittgenstein sur les règles mathématiques dans
nombre de textes ont semblé constitué la voie naturelle pour répondre à cette
question.
I.
Que disent les règles
mathématiques ?
La
voie de l’interprétation sceptique du paradoxe des règles (dans la mesure où
Kripke prend explicitement l’addition comme exemple) est une première option assez
classique à étudier. Le problème de Kripke porte sur la psychologie et le
critère d’application d’une règle : le sujet n’appliquerait-il pas la
règle de la quaddition, qui consiste à additionner un nombre jusqu’à une
quantité n quelconque, et ensuite, par exemple, à passer à la
quaddition, qui consiste à ajouter quatre à chaque nombre ? Plus
généralement, qu’est-ce qui nous confirme que quelqu’un suit effectivement une
règle, à savoir à partir de quand les « rails » sont bien en
place ? C’est un problème bien plus large que la question de savoir de
quel type de généralité il est question « dans » les règles (en
particulier car cela fait appel à la psychologie et le langage), mais il est
pourtant utile de s’y confronter pour étudier la généralité.
Une
règle possède bien évidemment un contenu, qui est normatif : elle indique
ce qu’il faut faire dans un cas particulier (que ce soit une règle sur les
entiers, ou un théorème). Pourtant, comme le remarque à juste titre Bouveresse,
« la règle dit ce qui doit être fait, et non ce qui sera
fait »
(p. 100). En effet, pour reprendre la règle de la récurrence sur les entiers,
celle-ci indique comment procéder de manière générale, et pourtant, elle ne dit
en aucun cas quelle « action » ou démonstration sera effectuée.
Ainsi, comme lorsqu’une règle de jeu aux échecs ne stipule pas tous ses
cas d’application, la règle de la récurrence dit ce qui doit être fait dans un
contexte donné (le raisonnement sur les entiers) dans un but précis (prouver
une proposition) : « Ce qui est général, c’est la répétition d’une
opération. Chaque étape de la répétition a sa propre individualité. Mais ce
n’est pas comme si j’employais l’opération pour passer d’un individu à un autre
de sorte que l’opération soit un moyen pour aller de l’un à l’autre
[nous soulignons]. »
Il est indubitable que, pour Wittgenstein, les règles
grammaticales (les règles d’usage) des propositions mathématiques sont la clé
pour espérer « comprendre » leur généralité. À peu près au même
moment d’écrire la Grammaire philosophique, Wittgenstein a dicté ses
réflexions à deux membres du Cercle de Vienne, Moritz Schlick et Friedrich
Waismann.
Dans la dictée « Voir la généralité dans » (Das
Hineinsehen der Allgemeinheit), il s’efforce de
cerner au plus près la manière dont la généralité est exprimée dans les
propositions mathématiques. Comme à son habitude, il n’hésite pas à employer
une comparaison pour détailler sa pensée : « Voir quelque chose dans
quelque chose, c’est comme voir une physionomie dans un signe ». Il
s’efforce particulièrement, dans cette dictée (et tout au long de la Grammaire
philosophique) de montrer que la façon de voir est toujours exprimée au
moyen de règles grammaticales. Cela peut rappeler le genre de conseils donnés
par les professeurs aux étudiants de mathématiques : écrire le terme
général d’une suite $u_n = n ; u_{n+1} = n^2 $ n’est pas
suffisant car l’on indique pas que la variable n parcourt l’entièreté
des entiers naturels (on ne spécifie pas ses conditions d’application). Il en
va de même pour la série des entiers naturels (1, 2, 3, …) : l’essentiel
est dans le signe « … ». Le signe de la série des nombres peut aussi
bien être « 1, 2, 3, … », « 1, 2, 3, 4… », mais la règle
reste la même : « La généralité réside précisément en ceci que la
règle indique quelques exemples de la série des nombres avec des points et dit
alors : et ainsi de suite » (Ibid.).
Ce genre de réponse, typiquement witgensteinienne, peut
paraître insatisfaisante. C’est pourtant, semble-t-il, la conclusion à laquelle
arrive Wittgenstein dans la Grammaire philosophique :
« Mais nous pouvons nous demander : comment se fait-il que
quelqu'un qui applique maintenant la règle générale à un autre nombre suive
toujours cette règle ? Comment se fait-il qu'aucune règle supplémentaire n'ait
été nécessaire pour lui permettre d'appliquer la règle générale à ce cas, bien
que ce cas n'ait pas été mentionné dans la règle générale? Nous sommes donc
perplexes, car nous ne parvenons pas à franchir l'abîme qui sépare les nombres
individuels de la proposition générale. » (GP, p. 282-283)
Cela suggère bien la
désorientation intellectuelle que pose ce genre de problèmes. En effet,
jusqu’ici, il a surtout été question de caractériser la généralité des règles
(qui réside dans les conditions d’usage de celles-ci), et beaucoup moins du suivi
de celles-ci. Pour Wittgenstein, on pourrait dire qu’on ne peut pas en demander
plus aux mathématiques que ce qu’on a déjà fait : la généralité est une
première question, et l’applicabilité de la règle en est une autre.
II.
La généralité d’une règle
réside-t-elle dans l’étendue des cas possibles qu’elle autorise ?
Wittgenstein
répondrait assurément que le « domaine » des applications de la règle
ne consiste absolument pas en une réalité objective déjà constituée (ce qui
permettrait de résoudre le problème à la manière de Frege, à savoir
« qu’une ligne construite était, en un sens, déjà là » (GP, p. 281),
c’est-à-dire que les futurs nombres de la série des entiers sont des entités
objectives). Il ajoute juste ensuite que « la difficulté
ici est de lutter contre l'idée que la possibilité est une sorte de réalité
obscure ».
Il est en fait question ici du
platonisme de Frege (la position qui pose l'existence d’un
« troisième règne » qui contiendrait toutes les significations
possibles, et plus particulièrement pour notre problème, un espace ou domaine qui
contiendrait les applications possibles de la règle) et du « constructivisme »
de Wittgenstein. Il serait trop long de s’attarder sur la différence entre la
philosophie de Wittgenstein et l’intuitionnisme. Par constructivisme, on peut
comprendre l’idée que la proposition mathématique, par exemple « Tout
entier pair s’écrit sous la forme d’un quotient de nombres rationnels, avec le
dénominateur non nul », ne fait qu’indiquer un complexe plus large,
la démonstration. Il est à peu près certain qu’on ne pourra pas trouver un
passage dans lequel Wittgenstein défend ou semble défendre une position qui
consiste à dire que les propositions mathématiques décrivent un état de fait
objectif (comme avec des propositions empiriques). Des déclarations comme
« On ne peut pas désigner un calcul comme étant la preuve d’une
proposition » (GP, VI, 33, intitulé « Jusqu'où une preuve récursive
mérite-t-elle le nom de "preuve" ? Dans quelle mesure une démarche
selon le paradigme A est justifiée par la preuve de B ? ») invitent
clairement à approfondir ce genre de remarques.
Wittgenstein
a révisé la conception de la généralité présente dans le Tractatus :
« Bien sûr, l’explication de $(\exists x).\phi(x)$ comme une somme
logique et de $(x).\phi(x)$ comme un produit logique est indéfendable » (GP,
p. 268). Pour rappel, par exemple, on peut écrire $\forall x,\ \varphi(x)\ =\ \prod_{p} x_p$ et le voir comme autant de réalisations
possibles de la propriété $\varphi∶\varphi a.\ \varphi b.\ \varphi c,\ etc. $ . La thèse rejetée dans les années 30 est
celle qui consiste à dire que les termes du produit ou de la somme (dans le cas
d’une quantification existentielle) peuvent être énumérés, comme lorsque si
l’on demande à quelqu’un de nous apporter une plante, celui-ci procède par une
sorte de disjonction de cas parmi toutes les plantes possibles. Wittgenstein
rejette fermement cette conception de la proposition générale, au profit d’une
« grammaire » de la proposition : « J'ai dit :
« avant toute expérience, il était possible de savoir et d'affirmer dans
la grammaire que (∃x).fx
découle de fa". Mais il aurait fallu dire : "(∃x).fx suit de fa' n'est
pas une proposition (proposition empirique) de la langue à laquelle ‘(x).fx' et
'fa' appartiennent ; c'est une règle établie dans leur grammaire » (Ibid.,
p. 279). Cela aide à comprendre ce qu’il veut montrer lorsqu’il est question
d’une preuve par récurrence : la notion de « suivre de » est
essentiellement grammaticale, et surtout, c’est une règle, et non une
possibilité déjà établie avant le raisonnement.
Plus tard dans la Grammaire
philosophique, Wittgenstein discute précisément la preuve par récurrence,
en l’occurrence de
$ \forall(a,\ b)\in\mathbb{N},\ \ a+(b+c)\ =\ (a+b)+c $
Le complexe B est la
preuve par récurrence donnée par Skolem
telle qu’écrite dans son article :
$(B) \quad \begin{align*}
a + (b + 1) &= (a + b) + 1 \\
a + (b + (c + 1)) &= a + ((b + c) + 1) = (a + (b + c)) + 1 \\
(a + b) + (c + 1) &= ((a + b) + c) + 1
\end{align*}$
Wittgenstein
propose cette preuve, passablement plus longue, et seulement pour
$(R) \quad a + (b+1) = (a + b) + 1 $
Mais de toute façon ce n'est pas l'important. En (I) il ré-écrit a preuve de Skolem, alors qu'en (II), (III) et (IV) il prouve R avec trois autres règles basiques de calcul sur les entiers (commutativité et distributivité).
(I) $\left.
\begin{array}{l}
a + (b + (c + 1)) \overset{R}{=} a + ((b + c) + 1) \overset{R}{=} (a + (b + c)) + 1 \\
(a + b) + (c + 1) \overset{R}{=} ((a + b) + c) + 1 \\
\end{array}
\right\}
\quad
\begin{array}{r}
a + (b+c)=(a+b) + c
\end{array}$
(II) $\left.
\begin{aligned}
(a + 1) + 1 &= (a + 1) + 1 \\
1 + (a + 1) &= (1 + a) + 1 \\
\end{aligned}
\right\} \quad a + 1 = 1 + a$
(III) $\left.
\begin{aligned}
a + (b + 1) &\overset{R}{=} (a + b) + 1 \\
(b+1) + a &\overset{R}{=} (b + (a + 1)) \\
&\overset{R}{=} (b+a) + 1 \\
\end{aligned}
\right\} \quad a + b = b + a$
(IV) $\left.
\begin{aligned}
a.(b+(c+1)) &\overset{R}{=} a.((b+c) + 1) \overset{M}{=} a(b+c) + a \\
a.b + (a.(c+1)) &\overset{M}{=} (a.b) + (a.c + a) = (a.b + a.c) + a \\
\end{aligned}
\right\} \quad a(b+c) = ab + ac$
NB : $ a.b = ab $ bien sûr, et $ M $ semble simplement consister à remplacer 1 par un $a$ quelconque (comme Skolem le fait).
Il fonde sa
réflexion sur le complexe B. L’objectif qu’il poursuit en particulier dans ces
pages, comme le titre l’indique, est de se demander dans quelle mesure une
preuve par récurrence est une preuve. Il s’attache à montrer que le plus
important, dans une preuve par récurrence, comme on ne peut pas vérifier qu’un théorème est valide pour
tous les nombres naturels, le critère le plus fiable est celui de la preuve
effective :
« Le
concept de généralité (et de récursivité) utilisé dans ces preuves n'a pas plus
de généralité que ce qui peut être lu immédiatement dans les preuves »
(GP, p. 418)
Et :
« L'étape est justifiée si
l'on a réellement prouvé un théorème valable pour tous les nombres" - Mais
dans quel cas cela se serait-il produit ? Comment appelle-t-on une preuve qu'un
théorème est valable pour tous les nombres cardinaux ? Comment savoir si un
théorème est réellement valable pour tous les nombres cardinaux, puisqu'on ne
peut pas le tester ? Votre seul critère est la preuve elle-même » (Ibid., p. 422)
On pourrait dire que (II) (III) et (IV) ne sont que des preuves sans rapport avec la bonne preuve (celle de Skolem, en (I)). Mais ce que je trouve malin est que (II), (III) et (IV) sont juste une autre manière de prouver R ! Bien sûr, chaque manière de prouver R dépend de la règle implicite qui est utilisée (commutativité, distributivité). Skolem, lui, utilise simplement l'hypothèse de récurrence elle-même et vérifie son hérédité. Notamment, en (III), Wittgenstein utilise la commutativité pour prouver (R). En fait, peut-être trouverez vous cela fumeux. On trouve cela fumeux car comme Wittgenstein le dit, il est difficile de "voir autour du calcul" (see round the calculus). De même, il est difficile de se repérer car en vertu de quelle règle l'hérédité est-elle satisfaisante ? C'est sur ce point qu'il veut nous faire réfléchir.
M. Marion
relie ces réflexions à un passage des Remarques philosophiques :
« Si c’est une preuve, la preuve par induction serait une preuve de
généralité, et non la preuve d’une certaine propriété pour tous les nombres »
(§ 168). Cela permet de cerner encore mieux la conception de Wittgenstein parmi
les options platonistes et constructivistes. Ce qui peut être conclu de cela
est que, d’une part, la preuve par récurrence possède un statut assez
particulier au sein des « règles » mathématiques (car elle fait
elle-même appel à des règles implicites sur les entiers) et, d’autre part, elle
ne prouve rien sur les nombres entiers. Elle exprime plutôt le
comportement des entiers naturels lorsqu’ils sont calculés ou opérés d’une
certaine manière (somme, produit, …), comme des inputs dans une fonction, qui donne un résultat déterminé selon ces derniers. Mais il reste tout à fait juste de continuer à désigner cette forme de
preuve comme une règle qu’il est possible d’utiliser lorsqu’il s’agit de
démontrer une proposition portant sur le domaine des entiers naturels. Pour Wittgenstein, un calcul n'est PAS une preuve : c'est la leçon qu'il voudrait que l'on retienne.
Un des problèmes restants, avec lequel il
faudrait interroger les textes de Wittgenstein et plus largement ce qui touche
à la correspondance de Curry-Howard, véritable « ligne de partage des eaux
dans l’histoire de la logique au vingtième siècle » selon Marion (Ibid.),
est celui du « problème de la spécification » (J.-L. Krivine) :
trouver le « comportement commun » de toute preuve d’un théorème. Ou
pour citer Wittgenstein : « Comment la preuve peut-elle produire la même généralisation (generalisation)
que les essais précédents ont rendu probable ? » (GP, p. 361).
III.
Le platonisme quant aux
règles est-il toujours soutenable ?
Dans
un dernier temps, nous voudrions examiner les raisons de soutenir que les cas
possibles d’application des règles sont préexistants à l’usage de la règle.
Assurément, il est possible de défendre le fait que les règles mathématiques
sont différentes des règles pratiques, la différence majeure étant qu’il
est beaucoup plus simple « d’improviser » sur une règle pratique que
sur une règle mathématique : je peux décider de ne pas traverser la rue
exactement sur le passage piéton lorsque le feu est vert et quand même
respecter la règle « traverser lorsque le feu est vert », alors qu’il
est difficile de suivre « à moitié » la règle de récurrence. Il faut
aller au bout, en quelque sorte.
Dans les deux lettres sur
l’arithmétique de Hermann Schubert,
Frege écrit :
« [Les postulats
d'Euclide] ne sont à proprement parler rien d’autre que des axiomes qui énoncent qu'il y a des constructions —
points, lignes, surfaces —
constituées d’une certaine manière. C’est ainsi que la proposition
qui demande que l'on trace une ligne droite d’un point quelconque à un
autre dit qu’il y a, pour deux points pris de façon quelconque, une
ligne droite qui les joint. Lorsque nous traçons une ligne, nous dirigeons
notre attention sur elle, qui est à proprement parler déjà là. La possibilité
objective de tracer une ligne est à proprement parler la même chose que
l'existence objective de cette ligne. »
Ainsi, les mathématiques
semblent être le domaine du « possible » par excellence : si
l’on arrive à prouver une proposition si abstraite que le théorème de Fermat
200 ans plus tard, c’est bien que la preuve fût possible, et qu’elle existe
objectivement. Tout le problème réside dans le sens de « objectivement » :
est-ce la preuve, ou la nature même de la conjecture de Fermat qui lui
confèrent cette objectivité ?
« La conception intensionnelle (...) est que ou bien on a
une démonstration qu’il existe trois 7 dans p, ou bien on a
une démonstration qu’il ne peut y avoir trois 7 dans p.
Il semble y avoir encore une troisième possibilité, à savoir qu’on n’ait pas de
démonstration ni dans un sens ni dans l’autre. Lorsque Brouwer dit que la loi
du tiers exclu n’est pas toujours valide, il adopte le point de vue
intensionnel » (Wittgenstein’s Lectures at Cambridge, 1932-1935, p. 196)
Bouveresse remarque à
juste titre que la conséquence de la position intensionnelle est qu’il y aurait
alors des propositions mathématiques qui ne prendraient sens que lorsqu’elles
sont démontrées vraies ou fausses (ce qui est problématique). Le platonisme et
l’intuitionnisme semblent tout deux supposer une généralité donnée de droit
avec les démonstrations : celle-ci règlerait les dissensus
possibles quant à la proposition considérée. Il serait ici tentant (et utile)
d’ajouter la position de Wittgenstein, ce qui permettrait d’exposer une autre
thèse possible, mais comme l’écrit Bouveresse :
« Wittgenstein lui-même a éprouvé
manifestement des difficultés sérieuses
à expliquer clairement ce que l’on peut vouloir dire lorsqu'on
dit que la démonstration crée un nouveau concept ou un
nouveau paradigme » (p. 74). Mais, à nos yeux, celui-ci rejetterait avant
tout l’idée que la démonstration est un concept univoque, dans le sens où
celle-ci fixerait notre réaction face à celle-ci une fois pour toutes :
« C’est un fait que la démonstration ne nous laisse aucun choix réel et
que nous ne choisissons pas ; mais il n’y a pas de différence philosophiquement
exploitable entre le fait que nous devions accepter le résultat obtenu, si nous
voulons respecter la signification des termes impliqués dans la démonstration,
et le fait que nous considérions comme impossible de le rejeter sans nous
rendre coupables d’un oubli ou d’une infidélité à l'égard de la signification
que nous avons donnée aux termes en question » (Ibid., p. 79). Pour
cela, il faudrait travailler plus explicitement sur le concept de démonstration
et si celui-ci est vague ou non (comme cela semble être le cas à cette étape de
la réflexion).
Nous
avons auparavant indiqué que les règles mathématiques se distinguent des règles
ordinaires, mais on peut constater que dans certains cas, les propositions
mathématiques ressemblent aux propositions ordinaires : «
Les cas dans lesquels une question mathématique est semblable à une question
ordinaire sont ceux dans lesquels nous avons une méthode générale pour y
répondre » (WLC, p. 199). Il semble tout à fait correct de dire que « La
question mathématique ressemble à la question ordinaire, lorsque nous disposons
d’une méthode de vérification qu’il s’agit simplement d’appliquer à un cas
particulier, par exemple d’un algorithme qui fournit la réponse à tous les
problèmes d’une certaine catégorie. Elle s’en distingue en revanche
complètement lorsque nous sommes à la recherche d’une méthode de décision, qui
ne déterminera pas seulement, lorsque nous l’aurons trouvée, la réponse
désirée, mais également le sens réel de la question elle-même. »
Ainsi, à partir du moment où a effectivement lieu une recherche de
quelque chose de nouveau, il est clair que les domaines de l’ordinaire et du
mathématique se séparent. En mathématiques, en quelque sorte, lorsque l’on
cherche une méthode pour décider de la vérité d’un énoncé, tout est possible,
dans la mesure de notre intelligence et imagination, afin de déterminer la
vérité de ce que l’on cherche (encore reste-t-il que les démarches de
démonstration seront fortement différentes selon que l’on définisse ou non la vérité
mathématique comme la dérivation selon des règles syntaxiques). La
distinction entre complétude déductive et complétude sémantique depuis Gödel en
est la raison.
Selon
Bouveresse, on peut ranger le platoniste et l’intuitionniste du même côté, dans
le sens où le second « continue à raisonner, lui aussi, en fonction d’une
suite qui contient les questions et les réponses, mais d’une manière telle que
les questions ne seront pas nécessairement posées et les réponses pas
nécessairement trouvées » (Ibid., p. 134). Dans la mesure où les
règles mathématiques sont des propositions mathématiques, le raisonnement
s’applique aussi aux règles : il est possible de se demander si la méthode
de « suivi » d’une règle doit être déterminée d’une manière
uniquement « possibiliste » (platonisme, intuitionnisme), ou non.
Cela suggère de nombreuses possibilités d’études : les règles de syntaxe
et ce qu’elles autorisent, les règles de déduction, ou encore la manière de
conceptualiser les règles de transformation ou de substitution. En ce sens,
étudier le platonisme de Gödel, qui, rappelons-le, a finalement fini par
rejeter l’existence de propositions mathématiques absolument indécidables,
serait également une dernière voie à emprunter pour clarifier ce large débat
concernant le platonisme, ou réalisme mathématique.
Bibliographie :
BOUVERESSE,
Jacques, Le pays des possibles : Wittgenstein, les mathématiques et le monde
réel, Éditions de Minuit, 1988.
BOUVERESSE, Jacques, Les vagues du langage : le
« paradoxe de Wittgenstein » ou comment peut-on suivre une règle ?,
Seuil, 2022.
FREGE, Gottlob, Zwei Schriften Zur Arithmetik, Georg
Olms Verlag, 1999.
« Interactive models of computation and program
behaviour | Société Mathématique de France », Tome 27, 2009.
KRIVINE, Jean-Louis, « Typed lambda-calculus in
classical Zermelo-Frænkel set theory », Archive for Mathematical Logic,
vol. 40 / 3, avril 2001, p. 189‑205.
MARION, Mathieu et OKADA, Mitsuhiro, « Wittgenstein et
le lien entre la signification d'un énoncé mathématique et sa preuve », Philosophiques,
vol. 39 / 1, Société de Philosophie du Québec, 2012,
p. 101‑124.
SKOLEM, Thoralf, Begründung der elementaren arithmetik
durch die rekurrierende denkweise ohne anwendung scheinbarer veränderichen mit
unendlichem ausdehnungsbereich, 1923, 38 p.
WITTGENSTEIN, Ludwig, Philosophical Grammar, éd. Rush
Rhees, Blackwell, 1969.
WITTGENSTEIN, Ludwig, SOULEZ, Antonia et BAKER, Gordon P., Dictées
de Wittgenstein à Friedrich Waismann et pour Moritz Schlick, éds. Antonia
Soulez et Gordon P. Baker, Presses Universitaires de France, 1997.
