David Madore's WebLog: Edward Nelson prétend montrer que les mathématiques sont inconsistantes

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

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

(mardi)

Edward Nelson prétend montrer que les mathématiques sont inconsistantes

On me signale cette esquisse d'une démonstration (dont la version complète formerait un gros bouquin), par Edward Nelson (qui est pourtant un matheux relativement renommé, pas un fou dans sa cave), du fait que les mathématiques usuelles, et en fait déjà l'arithmétique de Peano, serait contradictoire.

L'idée serait une sorte de variante du paradoxe bien connu de l'« examen surprise » :

Un prof annonce à ses élèves qu'ils auront un examen au cours de la semaine qui vient (lundi à vendredi) et qu'ils ne pourront pas savoir avant le jour même quel sera le jour de l'examen ; les élèves raisonnent alors que l'examen ne peut pas être le vendredi puisque sinon le jeudi soir ils sauraient que ce ne peut être que le lendemain, et du coup le vendredi est exclu donc l'examen ne peut avoir lieu que du lundi au jeudi, mais les élèves peuvent alors répéter le même raisonnement pour exclure le jeudi, et ainsi de suite, et du coup l'examen ne peut pas avoir lieu du tout ; pourtant, lorsque le mercredi l'examen a lieu, il est effectivement une surprise.

On peut gloser cent mille ans sur ce paradoxe, je ne vais pas le faire parce que ça m'énerve particulièrement (voyez l'article Wikipédia à ce sujet), mais la résolution n'est pas particulièrement compliquée : si on appelle T0 l'axiome il y aura un examen cette semaine et Ti+1 l'axiome (T0 et) on ne peut pas conclure sur la base de Ti quel jour l'examen aura lieu avant qu'il ait lieu, alors T1 implique que l'examen n'a pas lieu vendredi, T2 implique qu'il n'a pas lieu jeudi non plus, T4 implique que l'examen a forcément lieu le lundi, et T5 est contradictoire. Si l'examen a lieu le mercredi, c'est que T3 était faux, voilà tout : si on interprète l'énoncé du prof comme T défini comme (T0 et) on ne peut pas conclure sur la base de T quel jour l'examen aura lieu avant qu'il ait lieu, c'est contradictoire et faux, ce qui n'empêche que T2 peut être vrai, ce qui présente déjà un certain élément de surprise. Bref, je trouve que ce paradoxe n'est pas spécialement intéressant. Mais je veux surtout faire remarquer que ce paradoxe appelle naturellement à faire appel à différentes théories, de plus en plus complexes, dans lesquelles on sait (ou on peut conclure) des choses.

L'erreur technique de Nelson (parce que comme Randall Munroe je n'ai pas le moindre doute qu'il y en ait une, et je ferais bien de prendre son conseil et d'ouvrir les paris au lieu d'essaier d'expliquer les choses) est facile à trouver : même si je n'ai pas envie d'essayer de comprendre exactement ce qu'il prend comme théories faibles de l'arithmétique, il est clair que le qu'il considère en haut de la page 4 (de l'esquisse signalée au début de cette entrée) dépend de la complexité (de Kolmogorov) de la théorie T. Or page 5 il considère des preuves qui increase in rank and level (de nouveau, je n'ai pas envie de savoir exactement ce qu'il entend par là), donc dans des théories T dont la complexité varie, alors qu'il prétend garder fixe. Perdu.

Du moins c'était ma réaction immédiate en lisant son esquisse, et comme je vois ici que Terence Tao est arrivé à la même conclusion, je suis raisonnablement confiant que c'est bien là le problème (au moins dans la façon dont Nelson explique les choses). Les mathématiques sont sauves (et nous avec) !

Mais même si j'ai envie d'ironiser en disant que c'est un peu inquiétant qu'un membre de la National Academy of Science puisse prétendre des choses aussi sottes, il y a un certain intérêt à essayer de comprendre ce que croit en fait Nelson, parce que ce n'est pas idiot (même si quand il pense que l'arithmétique de Peano est contradictoire, je suis totalement et complètement convaincu qu'il se trompe), et c'est une question qui est revenue à diverses reprises sur ce blog. Il ne prétend pas que les mathématiques réellement pratiquées sont contradictoires (et encore moins que 0=1), seulement que tous les systèmes dans lesquels on les fait habituellement sont contradictoires, parce que le principe de récurrence est faux et contradictoire. (Et il pense pouvoir reformuler beaucoup de résultats mathématiques dans un système plus faible qui lui convient, ce qui est en soi intéressant, par exemple du point de vue des mathématiques à rebours, même si on ne croit pas une seule seconde que ZF soit contradictoire.)

Peut-être que pour comprendre sa thèse je peux inviter mon lecteur à lire un texte de vulgarisation sur l'infini que j'avais écrit il y a quelques années, où je commence par expliquer le principe de récurrence sous la forme : 0 est un nombre fini, si n est un nombre fini alors n+1 est aussi un nombre fini (et les entiers naturels sont exactement ce qui s'obtient de cette manière, cf. ce que je racontais récemment sur les ordinaux) ; de ça, je prétends conclure que 1000, mais aussi 101000 ou 10↑10↑10↑10↑⋯↑1000 (avec 1000 élévations à la puissance), ou encore d'autres choses beaucoup plus grandes, sont des nombres finis. Faux, me rétorquerait Nelson : la seule façon dont je pourrais montrer que 101000 est un nombre fini, c'est par une démonstration qui commencerait par 0 est fini, donc 1 est fini, donc 2 est fini, donc 3 est fini, donc 4 est fini… et qui terminerait 101000 par donc 101000 est fini. Or si on met en doute le fait que 101000 soit fini, cette démonstration ne vaut que si elle est écrite complètement, ce qui est manifestement impossible, et je ne peux pas agiter des mains en disant oui, je pourrais le faire en principe, mais c'est très long alors il n'en est pas question : la question est justement de savoir si on pourrait le faire en principe, et si je ne le fais pas, mon raisonnement est circulaire. (Le problème est sérieux, puisque si on permet des longueurs non-standard, il est connu et certain qu'il existe des démonstrations de contradiction dans les mathématiques, mais ces démonstrations ne sont justement pas de longueurs finie, ce ne sont pas du tout des démonstrations, donc tout repose crucialement sur la question de la finitude.)

Maintenant, dans l'arithmétique de Peano, il n'y a aucun problème : si x et y sont des entiers naturels, alors xy existe (=est fini, a bien un sens, est un entier naturel). Mais c'est justement ça que Nelson met en doute : dans les théories faibles de l'arithmétique qu'il considère (je n'ai pas regardé les détails, mais ce genre de choses est assez habituel, voyez par exemple la partie C de ce livre), la fonction exponentielle n'est pas forcément totale : il n'y a pas de raison que xy existe si x et y sont des entiers naturels. Du coup, il faudrait effectivement une démonstration démesurément longue pour montrer que 101000 est un nombre fini ; et ces théories faibles ont un intérêt certain en algorithmique (à cause d'un rapport profond entre leurs théorèmes et différentes hiérarchies de complexité).

Maintenant, je ne sais pas si Nelson croit vraiment que le nombre 101000 n'existe pas ([ajout : en fait, probablement pas, parce que la fonction de multiplication, elle, est bien totale, et on peut construire 101000 en multipliant 1000 fois par 10, ce qui constitue une démonstration assez courte pour être écrite] ; mais il le croit sans doute pour le nombre 10↑10↑10↑10↑⋯↑1000 avec 1000 élévations à la puissance). Cela ne signifie pas qu'il existerait un plus grand entier naturel : tout le monde est d'accord que si n est un entier naturel, alors n+1 en est un, juste qu'on n'atteindrait jamais des nombres comme ce que je prétends avoir écrit ; c'est une opinion provocatrice, que je ne partage pas du tout parce que je suis religieusement platoniste, mais qu'il est difficile de disqualifier, parce qu'il est vrai qu'il faut pour éviter des démonstrations ridiculement longues (et peut-être, justement, prétendra Nelson, infiniment longues !) des axiomes strictement plus forts que ce qu'il admet, et dont il peut tout à fait croire qu'ils sont contradictoires (même si, en l'occurrence, il s'est trompé).

Et c'est un problème philosophique que je considère comme assez sérieux, de savoir si vraiment ces nombres ridiculement grands existent, et comment, et dans quelle mesure et pourquoi on a besoin qu'ils existent, et si les mathématiques peuvent s'en passer. Si on pense qu'ils existent (ce qui est mon cas), la difficulté est d'éviter le côté religieux du paradis platoniste. À l'inverse, si on pense qu'ils n'existent pas (ce qui est le cas de Nelson et, je crois, dans une certaine mesure, d'au moins un lecteur de ce blog), la difficulté est d'expliquer pourquoi ils ne causent pas de contradiction (s'ils n'en causent pas, c'est une forme d'existence au moins potentielle : pourquoi des choses inexistantes auraient-elles des conséquences tangibles comme la non-contradiction de Peano ou de ZFC ?), ou sinon, de trouver cette contradiction (comme Nelson semble déterminé à faire). Les paris sont ouverts !

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

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