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 !