David Madore's WebLog: Platonisme et mathématiques

Une assez longue réflexion en philosophie des mathématiques, que j'ai écrite dans un mail à un ami, et qui me semble suffisamment intéressante pour reproduire ici : il s'agit d'éclaircir un peu la question de savoir quel sens est-ce que ça a de qualifier un énoncé mathématique de vrai ou faux ?, i.e., dans quelle mesure les objets mathématiques existent-ils ? Et notamment : pourquoi est-ce qu'on sera généralement d'accord pour attribuer la valeur de vérité vraie à l'énoncé 252097800623 est un nombre premier mais qu'on sera beaucoup plus sceptique quant au fait que l'hypothèse du continu ait vraiment un sens dans le monde réel ?

[Ajout : on ferait mieux de commencer par lire d'abord cette entrée ultérieure, sans doute beaucoup plus pédagogique.]

On peut établir une hiérarchie dans laquelle s'inscrivent un certain nombre d'énoncés mathématiques (mais pas tous !) en fonction de la complexité de leurs quantificateurs. (Je crois que cette hiérarchie est due, sous une forme ou une autre, à Stephen Kleene et Azriel Lévy, mais je ne sais pas exactement quelles sont les contributions de l'un et de l'autre. Il en existe un certain nombre de variantes, arithmétiques ou ensemblistes : la variante qui suit est clairement du côté arithmétique d'ordre supérieur si on doit la qualifier plus précisément : ce que j'appellerai un énoncé Π_n c'est précisément un énoncé arithmétique Π_n.)

Tout en bas de la hiérarchie, il y a les énoncés et prédicats qu'on peut indifféremment appeler Σ₀, Π₀ ou Δ₀. Il s'agit des affirmations dont tous les quantificateurs portent sur les entiers naturels et sont, de surcroît, bornés, ou gardés, c'est-à-dire sont de la forme il existe un n inférieur à t ou pour tout n inférieur à t avec t un terme en les variables libres à ce point-là (disons que le terme peut faire intervenir l'addition, la multiplication et l'exponentiation des entiers, ou peut-être n'importe quelle fonction primitive récursive, pour ce que je vais dire ce n'est pas important).

Par exemple, l'entier formé par les 10000000000 premières décimales de pi en base 10 est un nombre premier peut s'écrire sous la forme d'un énoncé Δ₀ (modulo un tout petit peu de travail sur les écritures, i.e., l'implémentation d'un algorithme qui calcule pi). L'essentiel est que quand on a affaire à une telle affirmation, on peut la tester, de façon algorithmique, en temps fini, avec terminaison garantie (pour chaque valeur des variables libres, s'il y en a) : pour les connecteurs propositionnels c'est clair, et pour les quantificateurs, comme ils sont bornés, on n'a jamais qu'un nombre fini de cas à tester ; pour la même raison, un énoncé Δ₀ n'est jamais indécidable. Ça c'est ce qui est censé justifier que, philosophiquement, à peu près tout le monde conviendra qu'il y a bien un sens à dire si un tel énoncé est vrai ou faux — il suffit d'essayer. Évidemment, comme les opinions philosophiques des gens sont très variés, il y aura des ultra-finitistes purs et durs pour me dire que d'après eux, non, ça n'a pas de sens de se demander si l'entier formé par les 10↑(10↑(10↑(10↑10))) premières décimales de pi est premier ou non, s'il est complètement inconcevable de tester aussi loin : j'appellerai ces gens des (0,0)-platoniciens (i.e., pas du tout platoniciens) ; les autres sont au moins (0,1)-platoniciens.

Juste au-delà des énoncés (et prédicats) Δ₀, il y a les énoncés (et prédicats) Σ₁ et Π₁. Les premiers sont formés en ajoutant devant un prédicat Δ₀ un quantificateur existentiel portant sur les entiers naturels, alors que les seconds ajoutent un quantificateur universel. En fait, il est assez facile de voir (en utilisant un codage des k-uplets d'entiers par des entiers) qu'on peut se permettre d'ajouter un nombre fini de quantificateurs de même nature pour le même prix. Bien sûr, la négation d'un énoncé Σ₁ est Π₁, donc pour ce qui est de donner une valeur de vérité on peut ne regarder qu'un d'entre eux.

Un énoncé Π₁ peut être réfuté par la donnée d'un contre-exemple ; en revanche, il risque de ne jamais pouvoir être confirmé de façon certaine : en effet, il y a des énoncés Π₁ qui sont indécidables (l'exemple typique étant le système T [le système qui m'intéresse et dans lequel je travaille : Peano, ZFC, que sais-je encore…] est consistant, i.e., il n'existe pas de preuve de Faux dedans, ce qui est un énoncé arithmétique Π₁ comme on s'en convainc facilement, et dont Gödel nous dit qu'il n'est pas démontrable s'il est vrai). En fait, ils sont tous équivalents à un énoncé du type la machine de Turing explicitement donnée par le programme suivant <…> va tourner sans jamais s'arrêter (par exemple une machine de Turing qui cherche une démonstration de 0=1). Pourtant, philosophiquement, on peut être d'accord qu'ils ont une valeur de vérité (dans le vrai monde, je veux dire) sur la base d'une hypothèse de pensée du genre je laisse tourner indéfiniment la machine de Turing, ce qui a un sens, et ça a donc bien un sens de se demander si elle s'arrêtera un jour, ou pas. (Tout le monde ne sera pas d'accord, évidemment.)

Beaucoup d'énoncés mathématiques importants sont arithmétiques Π₁ comme je viens de le décrire : la conjecture de Goldbach, par exemple, ou le théorème de Fermat, ou encore l'hypothèse de Riemann (c'est moins évident pour cette dernière, mais on peut encore la mettre sous cette forme). Un énoncé de la forme telle variété algébrique (définie explicitement sur ℤ) a un point entier/rationnel est Σ₁ (et Matiyasevich a montré, en gros, qu'on peut toujours ramener un énoncé Σ₁ à cette forme dans le cas entier). De façon importante, aussi, tous les énoncés du type telle affirmation est démontrable ou telle affirmation est réfutable sont Σ₁ ; et, du coup, Peano est consistant ou ZFC est consistant sont Π₁ : il est important de souligner que, même si ZFC parle d'ensembles, l'affirmation de sa consistance est un énoncé purement arithmétique, et Π₁ de surcroît. Et par ailleurs on peut aussi souligner que, en parlant d'ensembles, ZFC permet de démontrer des énoncés arithmétiques Π₁ (du style Peano est consistant) que des systèmes plus faibles (Peano, en l'occurrence) ne démontrent pas. Comme beaucoup de mathématiciens seront d'accord que la question de savoir si <truc> est un théorème a un sens, on peut en conclure qu'ils sont au moins d'accord que les énoncés arithmétiques Σ₁ et Π₁ ont une valeur de vérité : on peut donc les qualifier de (0,2)-platoniciens.

Il y a aussi les Δ₁ dans l'histoire : ce sont ceux qui peuvent s'écrire à la fois comme un Π₁ et comme un Σ₁, avec une démonstration de l'équivalence (il faut considérer que cette démonstration fait partie de la donnée de l'énoncé, pour pouvoir le qualifier de Δ₁, parce que sinon il existe une démonstration… ça va rendre le truc Σ₁, ce qui n'est pas bien). De beaucoup de points de vue, on peut considérer qu'un Δ₁ c'est aussi bien qu'un Δ₀ : en tout cas c'est finiment testable, puisqu'on essaie en parallèle de démontrer le Σ₁ et de réfuter le Π₁ et on est sûr que l'un d'entre eux terminera en temps fini.

Un énoncé ou prédicat Π_n+1 en général se forme en ajoutant un quantificateur universel (ou un nombre fini d'entre eux) devant un prédicat Σ_n, et un énoncé ou prédicat Σ_n+1 avec un quantificateur existentiel devant un prédicat Π_n. Tous ces quantificateurs portent toujours sur les entiers, pour l'instant : il s'agit d'affirmations arithmétiques du premier ordre. Bien sûr, un énoncé Δ_n c'est un énoncé qui peut se mettre sous la forme Π_n et Σ_n à la fois ; et je dirai qu'un mathématicien est au moins (0,n+1)-platonicien s'il admet que les énoncés Π_n ont une valeur de vérité bien définie.

Par exemple, un Π₂, il va dire que pour tout x il existe y tel que (une certaine propriété testable de x et de y) : c'est difficile à réfuter (il faut exhiber un x avec une démonstration du fait que pour chaque y ça ne marche pas) et encore plus difficile à prouver ; donc là j'ai encore plus de mal à justifier philosophiquement que ça a bien un sens de dire si c'est vrai ou faux. Néanmoins, si on a concédé que les énoncés Π₁ et Σ₁ sont toujours soit vrais soit faux, on peut encore admettre quelque chose sur les Π₂ (et Σ₂), avec une expérience de pensée du style : je lance une machine qui va tester tous les x et, pour chaque x, examiner tous les y — et à la fin des temps je verrai bien si elle a parcouru tous les x (auquel cas mon énoncé Π₂ est vrai) ou si elle est restée bloquée indéfiniment sur l'un d'entre eux (auquel cas l'énoncé est faux, cet x donnant un contre-exemple pour lequel il n'existe pas de y).

Exemples d'énoncés mathématiques Π₂ : toute suite finie de chiffres se trouve quelque part dans l'écriture décimale de pi ; ou encore : P n'est pas égal à NP (qu'on peut voir sous la forme il n'existe pas un algorithme et une borne polynomiale telle que l'algorithme résolve tout instance de SAT en temps donné par cette borne). Si on convient qu'un tel énoncé a un sens, on est au moins (0,3)-platoniciens (j'ai décalé les indices de 1 pour convenir qu'un (0,0)-platonicien est quelqu'un qui n'admet même pas les énoncés Δ₀). Je pense que beaucoup de mathématiciens seront encore dans ce cas. Quant à l'énoncé il n'existe pas d'algorithme permettant de dire si une variété algébrique (définie sur ℚ) admet ou non un point ℚ-rationnel, il est Π₃ si je ne m'abuse (pour toute algorithme il existe une variété telle que pour tout M l'algorithme ne finit pas en temps M et la variété n'a pas non plus de point de hauteur <M).

Une façon de voir la valeur de vérité d'un énoncé Π_n, c'est de considérer le jeu suivant à deux joueur : Forall cherche à réfuter l'énoncé, et Exists cherche à le confirmer. Le jeu n'a que n coups (c'est un jeu fini), Forall joue en premier en donnant un entier naturel, Exists réplique avec un entier naturel, et ainsi de suite sur n coups ; à la fin, on substitue ces entiers naturels aux n variables alternativement quantifiées par l'énoncé, et si le résultat (qui est finiment testable car Δ₀) est faux, Forall a gagné, sinon c'est Exists. La vérité de l'énoncé est équivalente à l'affirmation que Exists possède une stratégie gagnante, et sa fausseté au fait que Forall en a une. Donc si on admet le principe que tout jeu fini de la sorte a une stratégie gagnante, alors on admet l'idée que tout énoncé arithmétique du premier ordre a une valeur de vérité.

Une autre façon de voir les choses est de dire : si j'ai un Oracle qui me permet de décider si une machine de Turing s'arrête (donc si j'admets la possibilité conceptuelle d'un tel Oracle) alors je peux réfuter un énoncé Π₂ en utilisant cet Oracle dans une machine de Turing ; si j'ai un Oracle, encore plus puissant, qui me permet de décider si une machine de Turing pouvant faire appel au premier Oracle s'arrête, alors je peux réfuter un énoncé Π₃, etc. Si j'admets que tous ces Oracles ont un sens, alors j'admets que tout énoncé arithmétique du premier ordre a une valeur de vérité.

Quelqu'un qui admet que tout énoncé arithmétique du premier ordre (i.e., Π_n pour n'importe quel n) a une valeur de vérité, je vais le qualifier de (1,0)-platonicien (ou (1,1)-platonicien, ma numérotation étant un peu malheureuse). Personnellement je crois être (1,0)-platonicien et je ne suis pas persuadé d'être plus. Mais je vais expliquer ce que ce plus signifie.

Pour ça, il faut passer aux énoncés d'ordre supérieur, c'est-à-dire, admettant des quantificateurs non plus seulement sur les entiers naturels mais aussi sur les parties de ℕ. Je dirai qu'un énoncé est Δ¹₀ s'il est Π_n (=Π⁰_n) ou Σ_n (=Σ⁰_n) pour un certain n ; je dirai qu'un énoncé est Σ¹₁ s'il s'obtient à partir d'un énoncé Δ¹₀ (resp. Π¹₀) par ajout d'un quantificateur existentiel (resp. universel) portant sur les parties de ℕ (ou sur les nombres réels, ou sur les suites d'entiers, ça revient au même). On aura deviné ce qu'est un énoncé Σ¹_n ou Π¹_n en général : quelqu'un qui croît que de tels énoncés sont vrais ou faux sera dit (1,n+1)-platonicien. Tous ces énoncés s'appellent énoncés arithmétiques du second ordre (par opposition à ceux qui n'avaient que des quantifications sur les entiers naturels et qui sont dits arithmétiques du premier ordre).

Exemple d'énoncé mathématique Π¹₃ : si B est un borélien de ℝ, alors le jeu à deux joueurs où chaque joueur choisit tour à tour une décimale d'un réel, et où (au bout d'un temps infini) le premier joueur gagne si le réel ainsi formé appartient à B et l'autre joueur s'il n'y appartient pas, [ce jeu] admet forcément une stratégie gagnante pour un des deux joueurs. (Il s'agit du théorème de détermination borélienne : c'est un théorème de ZFC, par ailleurs difficile. La raison pour laquelle c'est bien un énoncé Π¹₃ c'est qu'on peut coder les boréliens de ℝ comme des suites d'entiers, ainsi que les stratégies gagnantes, ou la suite des coups joués par un des deux joueurs.) Si on remplace borélien par analytique (i.e., image d'un ensemble borélien par une fonction continue, ce qui peut toujours se coder avec des suites d'entiers), alors l'énoncé résulte d'hypothèses de grands cardinaux qui dépassent ZFC (l'existence de x^♯ pour tout réel x). Un (1,4)-platonicien devra penser que cet énoncé est soit vrai soit faux : pour ma part, je commence à être sceptique sur le fait que ça ait vraiment un sens.

Le problème avec les parties de ℕ, c'est qu'on ne sait pas exactement ce qu'elles sont, on ne peut pas les déterminer complètement comme un entier naturel. (Kronecker : Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk.) Je peux certes imaginer de reprendre mon jeu à deux joueur (Forall et Exists) et imaginer que ces joueurs échangent non plus des entiers naturels mais des Oracles qui permettent de savoir si un entier naturel est ou n'est pas dans la partie en question, mais je trouve que ça devient philosophiquement fumeux dans la mesure où chacun doit avoir le droit de poser un nombre infini de questions à n'importe quel Oracle choisi antérieurement, et de se décider en fonction de ça. Or peut-être qu'il y a dans l'univers une certaine limitation sur ce qu'un Oracle peut dire ou sur la façon dont on peut l'interroger, et cette limitation va affecter la notion de vérité pour les énoncés d'ordre supérieur.

En fait, voici un énoncé Σ¹₁, qui est un théorème de ZFC, et qui commence déjà à montrer la subtilité : il existe une partie de ℕ qui code la vérité des énoncés arithmétiques du premier ordre (tel quel ce n'est pas un énoncé mathématique correctement formalisé, mais il le devient si on le code comme ceci : il existe une partie de qui contient les codes de tous les énoncés Δ₀ vrais [ça ça ne pose pas de problème à définir, il y a même une définition Δ₁ uniforme] et aucun code d'un énoncé Δ₀ faux, et elle contient le code d'un énoncé pour tout x <machin> ssi elle contient le code de <machin> avec n remplacé pour x, pour tout n, et pareil pour il existe). On voit qu'admettre la vérité d'un tel énoncé c'est non seulement admettre qu'un énoncé arithmétique du premier ordre a toujours une valeur de vérité bien définie, mais aussi qu'on puisse s'en servir pour former une partie de ℕ : comme la vérité des énoncés arithmétiques du premier ordre n'est certainement pas définissable par un prédicat arithmétique du premier ordre (il n'existe pas de prédicat P arithmétique du premier ordre tel que P(‹Q›) ⇒ Q dès que ‹Q› est le code d'un énoncé Q arithmétique du premier ordre), admettre l'existence d'une telle partie c'est déjà dépasser substantiellement ce que permet l'arithmétique du premier ordre. Maintenant, dans ZFC c'est un théorème (à peu près évident), mais il y a des théories suffisantes pour faire à peu près toutes les maths envisageables et dans lesquelles un tel énoncé est inaccessible. Bref, si je suis (1,0)-platonicien (ce qui est pareil que (1,1), en fait, avec ma convention), je ne suis pas certain d'être (1,2)-platonicien.

Évidemment, on peut aller au-delà et admettre des quantifications sur les parties de parties de ℕ (i.e., les parties de ℝ). Un énoncé Σ²₁ admet un quantificateur existentiel portant sur les parties de parties de ℕ devant n'importe quel énoncé Π¹_n (pour un n quelconque). L'hypothèse du continu, par exemple, est un énoncé Π²₂. Pour ma part, je ne pense pas que ça ait beaucoup de sens de se demander si elle est vraie ou fausse : je pense que c'est plus une question de convention sur ce qu'on veut admettre comme ensembles. (Et on est généralement d'accord que pour les ensembles les plus sympathiques et/ou naturels, l'hypothèse du continu est violemment fausse.) Enfin, il y a des énoncés de ZFC qui ne se laissent pas réécrire comme des énoncés de l'arithmétique d'ordre supérieur (ce que j'ai défini) : par exemple, il existe un cardinal inaccessible ne peut pas se décrire[#] comme Σ^r_n pour aucun r et n.

En revanche, ce qu'il faut souligner, c'est que même s'il faut un niveau de platonisme très élevé pour accepter de discuter de la vérité ou non de il existe un cardinal inaccessible et autres notions exotiques de la théorie des ensembles, en revanche, l'idée qu'un cardinal inaccessible puisse exister, c'est-à-dire soit consistante avec ZFC, ça c'est quelque chose de purement arithmétique, c'est même un énoncé simplement Π⁰₁. Et je suis pour ma part persuadé que c'est vrai : c'est là, d'ailleurs, que ma position philosophique se casse la gueule, parce que si je suis prêt à admettre qu'un cardinal inaccessible puisse exister mais pas que ça ait un sens de se demander s'il existe, on se demande un peu d'où je tire la conviction qu'il puisse exister (ce n'est pas un théorème de ZFC si ZFC est consistant, donc la croyance en une telle chose ne peut venir que d'une idée de grands cardinaux, quelque part). Du coup je ne sais pas bien ce que je crois.

En fait, j'ai l'impression que les théoriciens des ensembles sont souvent beaucoup plus platoniciens que les autres mathématiciens (ils avouent souvent publiquement être persuadés que l'hypothèse du continu est fausse, qu'un cardinal mesurable ou supercompact existe, etc.). Je pense que c'est lié au fait que les autres matheux peuvent tout à fait travailler sans avoir besoin de considérer de tels énoncés, alors que si on veut faire de la théorie des ensembles il est un peu malheureux de se dire qu'on ne manipule que des symboles qui ne veulent rien dire… Peut-être que les théoriciens des ensembles ont accès à un paradis platonicien plus vaste que le reste des matheux ? (Hilbert : Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können.)

[#] Ça c'est dans la hiérarchie arithmétique (d'ordre supérieur), que j'ai décrite, bien sûr : parce que comme énoncé ensembliste, il existe un cardinal inaccessible est quelque chose comme Σ₂.