David Madore's WebLog: Pourquoi l'univers constructible de Gödel est important mathématiquement et philosophiquement

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

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

(mardi)

Pourquoi l'univers constructible de Gödel est important mathématiquement et philosophiquement

[J'ai écrit ce texte par tout petits bouts sur plusieurs mois. J'espère que le processus fragmenté de son écriture ne le rend pas trop brouillon !]

Introduction

De façon inexplicable, quand j'ai listé certains des objets mathématiques qui me fascinent, j'ai oublié de citer l'univers constructible de Gödel : la lecture de l'article Wikipédia à son sujet ne parlera sans doute pas beaucoup au profane, mais je voudrais rattraper mon oubli en essayant d'expliquer un peu de quoi il s'agit, parce que cet objet me semble non seulement fondamental et extrêmement élégant, mais même, dans un certain sens, on peut dire qu'il donne un sens à toutes les mathématiques (avec néanmoins une question philosophique fondamentale : est-ce vraiment le sens que nous voulons ou devrions leur donner ? c'est-à-dire, veut-on ou doit-on accepter l'axiome de constructibilité qui affirme que cet univers constructible est l'univers mathématique ?).

Si on me donne dix secondes pour dire un peu de quoi il s'agit à quelqu'un qui ne connaît rien aux mathématiques, je pense que je tenterais de résumer l'axiome de constructibilité à ce slogan philosophique dont, malheureusement, le côté percutant enlève beaucoup à la précision :

Il n'existe pas de vrai hasard.

Si, en revanche, je dois expliquer de quoi il s'agit à quelqu'un qui connaît un peu les mathématiques, je dirai la chose suivante : l'axiome de constructibilité généralise — et non seulement implique, mais même explique — deux postulats célèbres de la théorie des ensembles que sont l'axiome du choix et l'hypothèse (généralisée) du continu. L'axiome de constructibilité rend explicites et « naturels » des objets dont l'axiome du choix ne fait que postuler l'existence, et il apporte suffisamment d'information sur les parties de ℕ pour démontrer et éclairer l'hypothèse du continu (et plus généralement sur les parties de n'importe quel ensemble pour l'hypothèse généralisée du continu). L'axiome de constructibilité ordonne (et « déroule ») tout l'univers mathématiques selon les ordinaux et permet donc de répondre à un nombre étonnant de questions combinatoires autrement indécidables, dont la véracité de l'axiome du choix et de l'hypothèse du continu ne sont que deux exemples : ce qui ne veut pas dire, cependant, que nous devions forcément accepter ces réponses comme correctes.

Plan de cette entrée :

Y a-t-il des suites aléatoires ?

Tout ceci est quand même vraiment trop approximativement résumé pour être sérieux. Essayons d'être un peu moins fumeux. Pour ça, je m'intéresse[#] aux suites infinies de 0 et de 1 (ce qu'avec une terminologie un peu surannée on appellera le continu), c'est-à-dire des choses comme :

0011010100010100010100010000010100000100010100010000010000010100000100010100000100010000010000000100010100010100010000000000000100010000010100000000010100000100

En l'occurrence, l'exemple particulier qui figure ci-dessus est généré d'après une règle simple : le k-ième chiffre de la suite (en comptant les rangs à partir de k=0) est un 1 lorsque le nombre k est premier et 0 sinon ; on peut donc, si on veut, identifier cette suite à l'ensemble {2,3,5,7,11,13,…} des nombres premiers (des rangs dans la suite où le chiffre est un 1). Et si vous avez un JavaScript qui marche sur votre navigateur — et si je n'ai pas trop planté mon code — les termes sont générés à la volée par un petit programme pour donner une illusion d'infini. Ce genre de suites, dont les termes peuvent se calculer par un programme informatique (ou plutôt par son idéalisation mathématique, la machine de Turing) sont appelées calculables [au sens de Church-Turing] (ou récursives, mais ce n'est pas une très bonne terminologie ; j'en ai déjà parlé). Manifestement, ce genre de choses est tout sauf aléatoire (on peut ergoter que le langage de programmation peut inclure une fonction random(), mais comme les machines de Turing ne sont pas censées avoir de « vrai » générateur aléatoire, il ne s'agira que de générateur pseudo-aléatoire[#2] et, en fait, déterministe).

Mais tout ce qui est « déterministe » (dans un sens que je laisse vague pour l'instant) n'est pas pour autant calculable au sens de Church-Turing (i.e., il se peut que quelque chose soit parfaitement déterministe mais qu'on ait besoin d'un modèle de calcul plus puissant que la machine de Turing pour expliciter ce déterminisme). L'exemple classique d'une suite (ou d'un ensemble d'entiers naturels, cela revient essentiellement au même) qui n'est pas calculable, c'est le problème de l'arrêt, c'est-à-dire la suite dont le k-ième terme vaut 1 lorsque le k-ième programme (dans une numérotation standard de tous les programmes possibles) s'arrête et 0 sinon. L'argument revient plus ou moins à appliquer l'argument diagonal de Cantor sur la liste de toutes les suites calculables pour dire qu'on peut forcément produire une suite qui n'est pas calculable. Toujours est-il qu'on a une suite qui est parfaitement bien définie, et en aucun cas « aléatoire » et qui n'est pas calculable par une machine de Turing.

Si on préfère, on peut utiliser l'écriture binaire de la constante de Chaitin, ou probabilité qu'une machine de Turing aléatoire s'arrête : c'est essentiellement la même chose que le problème de l'arrêt « comprimé » ; la suite des décimales du nombre de Chaitin est plus « dense » que celle du problème de l'arrêt au sens où connaître k chiffres de l'une revient essentiellement à en connaître 2k de l'autre, mais du point de vue du degré de Turing elles reviennent au même (si une machine de Turing a à sa disposition un « oracle » qui calcule l'une de ces suites, elle peut s'en servir pour calculer l'autre — on dit qu'elles sont Turing-équivalentes).

Si la machine de Turing ne peut pas calculer la suite du problème de l'arrêt (ou celle du nombre de Chaitin), rien ne nous empêche d'imaginer une machine plus puissante — toujours une idéalisation mathématique — qui en soit capable : il suffit par exemple d'imaginer une machine de Turing qui dispose d'un « oracle » capable de répondre magiquement à la question quel est le k-ième nombre sur la suite du problème de l'arrêt ? (bref, pour que le problème devienne calculable pour cette machine plus puissante il suffit de lui en donner artificiellement la réponse !). On aura reconnu là l'opération appelée saut de Turing. Cette machine plus puissante reste parfaitement déterministe, et les suites qu'elle peut calculer ne sont en rien aléatoires : elle n'est pas capable de résoudre son propre problème de l'arrêt, pas plus que la machine de Turing n'était capable de résoudre le sien. On peut donc définir une machine encore plus puissante, et ainsi de suite.

Mes lecteurs fidèles auront reconnu dans les mots ainsi de suite la formule magique qui invoque les ordinaux aussi sûrement que il était une fois commence le conte de fée : le saut de Turing peut s'itérer à travers les ordinaux, c'est-à-dire qu'on peut définir des « machines » de plus en plus puissantes (et des suites qu'elles sont capables de calculer de plus en plus nombreuses) en parcourant les ordinaux. Je ne compte pas entrer dans les détails, ma présentation est trop désespérément vague pour cela, et ils ne sont pas évidents : d'autant que plus on veut aller loin dans les ordinaux plus la chose devient subtile[#3].

Mais disons juste la chose suivante : on a une hiérarchie de suites de plus en plus difficiles à calculer, indicée par un certain ordinal (le ω₁ constructible, qui si on croit à l'axiome de constructibilité coïncide avec le « vrai » ω₁), mais qui sont toutes définies de façon complètement déterministe. Ces suites s'appellent les suites constructibles (ou les parties constructibles de l'ensemble ℕ des entiers naturels ; ou les nombres réels constructibles, si on convient d'identifier un nombre réel à son écriture binaire — ce qui n'a vraiment pas d'importance ici). Ces suites sont tout sauf aléatoires : même s'il faut des machines transfinies, machines démesurément plus puissantes que la machine de Turing, pour calculer les éléments lointains de la hiérarchie, elles sont toutes « calculables » dans un sens monstrueusement généralisé, et donc certainement pas « aléatoires ».

La question philosophique fondamentale est donc : toutes les suites de 0 et de 1 sont-elles « calculables » dans ce sens très général (i.e., constructibles) ? ou existe-t-il au contraire des suites « aléatoires » qui ne suivent aucune règle ? (à commencer, bien sûr, par se demander si la question a vraiment un sens).

La présentation que j'ai donnée n'est pas celle qu'on en fait généralement (je vais y revenir), mais en tout cas, l'univers constructible de Gödel (noté L) est une hiérarchie de ce genre, non seulement pour les suites de 0 et de 1 (qui sont les premiers objets pour lesquels elle est intéressante) mais pour l'univers de tous les ensembles, c'est-à-dire, finalement, de tous les objets mathématiques. L'axiome de constructibilité, pour sa part, affirme que, effectivement, tous les ensembles sont ainsi fabriqués (on le note V=L, où V désigne la classe de tous les ensembles et L celle des ensembles constructibles). Le mot axiome n'est sans doute pas très bon, parce que cet axiome ne fait pas partie des postulats mathématiques usuels (ZFC) : on ferait donc sans doute mieux de parler d'hypothèse de constructibilité, mais le terme est standard.

L'axiome de constructibilité n'est ni réfutable ni démontrable (c'est-à-dire, est indécidable) dans le cadre usuel (ZFC) de la théorie des ensembles ; déjà la question de savoir si toutes les suites de 0 et de 1 sont constructibles est indécidable dans ce cadre. Selon l'inclinaison philosophique qu'on a, on peut se dire que c'est vrai, faux, mystérieux, ou juste une question de définition de ce qu'on appelle un « ensemble ». Ce qui est sûr, c'est que l'axiome de constructibilité ne fait pas partie des mathématiques standard (contrairement, disons, à l'axiome du choix) mais qu'il peut être y être ajouté sans risquer de créer une contradiction qui n'existerait pas déjà.

Philosophiquement, la position selon laquelle toute suite de 0 et de 1 obéit à une « règle » de calcul, même très générale, peut sembler difficile à tenir (elle semble poser une restriction artificielle sur ce qu'on appelle un « ensemble » ou une « suite »). Mais on peut voir les choses différemment et défendre l'idée que l'aléatoire n'est qu'une illusion d'absence de règle lorsqu'on ne parvient pas à voir la régularité : qu'une suite n'apparaît comme aléatoire que parce qu'on n'est pas allé assez loin dans le saut de Turing, qu'on a « coupé les ordinaux » de l'univers constructible pour donner l'illusion que certains ensembles n'y sont pas (c'est alors l'existence de l'aléatoire qui constitue une restriction ; et, de fait, sans rentrer dans les détails, on sait que ce genre de construction est possible : une suite constructible située très loin dans la hiérarchie constructible peut apparaître comme aléatoire si on la voit depuis un niveau limité).

En fait, la raison pour laquelle les théoriciens des ensembles n'aiment pas l'axiome de constructibilité est plutôt qu'elle interdit l'existence des « grands » grands cardinaux (les cardinaux mesurables étant les plus importants d'entre eux), ce qui semble également constituer une restriction sur ce qu'est un « ensemble » ; mais là aussi on peut faire des arguments pour défendre le fait que l'axiome de constructibilité n'est pas, en fait, restrictif (voir par exemple cet article de philosophie des maths qui expose assez bien les choses).

Considérations mathématiques

Indépendamment de ces considérations philosophiques qui paraîtront peut-être fumeuses, l'axiome de constructibilité n'est pas sans intérêt mathématique.

Conséquences classiques

Pour commencer, il démontre l'axiome du choix. Il fait mieux que l'impliquer : il explique et explicite l'axiome du choix. L'axiome du choix, par exemple, a comme conséquence qu'il est possible de mettre un bon ordre sur l'ensemble des réels (ou des suites infinies de 0 et de 1) : l'axiome de constructibilité en explicite un — puisqu'il construit les suites de 0 et de 1 selon une hiérarchie naturellement bien-ordonnée, c'est clair sur la présentation que j'en ai faite. Mieux, l'axiome de constructibilité permet de définir un bon-ordre tout à fait explicite sur l'univers de tous les ensembles (le bon ordre canonique de L), ou, ce qui revient au même, de le mettre en correspondance explicite avec les ordinaux. En particulier, tout ce qui est non-constructif à cause de l'axiome du choix redevient constructif et explicite[#4] si on suppose l'axiome de constructibilité.

L'axiome de constructibilité implique également l'hypothèse du continu : de nouveau, la manière dont la hiérarchie constructible énumère les suites de 0 et de 1 fournit (si on suppose l'axiome de constructibilité) une bijection explicite entre l'ordinal ω₁ et les suites infinies de 0 et de 1. En fait, l'axiome de constructibilité implique l'hypothèse généralisée du continu.

Philosophiquement, on pourrait objecter que c'est une « mauvaise » explication : c'est-à-dire, que l'univers constructible croit que 2ℵ₀=ℵ₁ parce qu'il ne crée que le strict minimum de nombres réels, et s'arrête ensuite ; mais de nouveau, on peut avancer le contre-argument que si certains modèles de la théorie des ensembles ont beaucoup plus de réels que de réels constructibles c'est en fait qu'on a « limité la taille » de ω₁, ce qui coupe la construction de l'univers constructible.

Mais je veux souligner que ce fait — que l'axiome de constructibilité implique l'hypothèse du continu — est nettement plus subtil que pour l'axiome du choix : il ne s'agit pas juste d'obtenir une bijection des réels avec un ordinal mais de s'assurer que cet ordinal vaut ω₁ (et pas plus). L'argument repose sur un fait crucial et extrêmement puissant concernant l'univers constructible, le lemme de condensation de Gödel : il est difficile d'expliquer précisément de quoi il s'agit sans devenir assez technique, mais de façon extrêmement grossière, disons qu'il affirme que si on prend certains ensembles dans la hiérarchie constructible qui « font semblant » d'être un certain niveau de la hiérarchie — techniquement, en sont un sous-modèle élémentaire —, alors il s'agit automatiquement d'un niveau de la hiérarchie (à isomorphisme près et même, dans certaines conditions, exactement). Et la raison pour laquelle ceci implique l'hypothèse du continu, c'est que pour « faire semblant » il n'y a pas besoin de beaucoup d'ensembles, d'après des théorèmes classiques un nombre dénombrable d'ensembles suffit, ce qui assure que tout nombre réel constructible apparaît dans la hiérarchie constructible à un niveau dénombrable, donc avant l'ordinal ω₁.

C'est ainsi que Gödel a prouvé en 1938 la consistance relative à ZF de l'axiome du choix et de l'hypothèse généralisée du continu (ainsi que de quelques autres conséquences de l'axiome de constructibilité en théorie descriptive des ensembles) : puisque ces faits, ainsi que tous les axiomes de ZF, sont valables dans l'univers constructible (on dit qu'il s'agit d'un modèle intérieur), il ne peut pas y en avoir de réfutation à partir de ces axiomes (à moins que ZF lui-même soit contradictoire).

Un « jeu de miroirs »

Mais l'intérêt mathématique de l'axiome de constructibilité va bien au-delà de ses deux conséquences disparates que sont l'axiome du choix et de l'hypothèse du continu : l'univers constructible est une structure à la structure riche et élégante, ce qui permet de donner énormément de conséquences combinatoires, et de démontrer des faits mathématiques généraux qui ne sont pas décidables dans ZFC seul.

Essayons d'en dire un peu plus sur cette structure riche et élégante. L'univers constructible se « fabrique » par étapes, indicées par les ordinaux. (Les détails précis de ces étapes ne sont pas forcément très importants : j'ai choisi d'esquisser une construction avec le saut de Turing, puisque je me limitais aux suites de 0 et de 1, mais la construction standard consiste plutôt à prendre « toutes les parties de ce qu'on a fabriqué à l'étape précédente qui soient définissables par une formule du premier ordre », et il y a encore d'autres variations ; même s'il est possible que ce qui s'obtient à l'étape 42 dans une construction s'obtienne à l'étape ω·42 dans une autre, ce n'est pas très grave, pour des ordinaux suffisamment « clos » toutes les constructions coïncideront.) Si on appelle Lα les ensembles obtenus jusqu'à l'étape α, pour certains ordinaux α, ce niveau Lα va « ressembler » de diverses manières à l'univers de tous les ensembles (constructibles) et se comporter comme un « univers en miniature ».

Par exemple, pour certains ordinaux, dits admissibles, l'ensemble Lα vérifiera un nombre non-négligeable des axiomes de la théorie des ensembles, i.e., un fragment de ZFC, fragment qui porte le nom de Kripke-Platek (KP en abrégé) : ces ordinaux admissibles portent une théorie de la calculabilité qui ressemble en beaucoup de points à la théorie classique de Church-Turing (sur ω) ; en considérant des fragments plus importants on obtient toutes sortes de conditions plus fortes sur les ordinaux (ordinaux nonprojectibles, ordinaux de gap, etc.). Un type subtilement différent de conditions consiste à demander que Lα non pas vérifie tel ou tel fragment des axiomes de la théorie des ensembles, mais plutôt « ressemble structuralement » (techniquement : soit un 1-sous-modèle-élémentaire, ou variations autour de ce thème) à la classe L de tous les ensembles admissibles, ou bien à un autre niveau Lβ de la hiérarchie : on obtient ainsi toutes sortes de déclinaison autour des ordinaux dits stables.

Bref, l'univers constructible ressemble par certains côtés à un « jeu de miroirs », où certains différents niveaux de la construction se reflètent les uns les autres, ou imitent l'univers tout entier. Une incarnation (ou peut-être, le point de départ) de cette idée est le lemme de condensation de Gödel que j'ai déjà mentionné. Le point culminant en est la version plus sophistiquée développée par Jensen dans les années '70 sous le nom de structure fine de L, et dont je ne peux malheureusement pas dire grand-chose[#5] au niveau de flou artistique où je me cantonne.

À cause de ce « jeu de miroirs », l'univers constructible vérifie un certain nombre de principes combinatoires (c'est-à-dire que ce sont, comme l'axiome du choix ou l'hypothèse du continu, des conséquences de l'axiome de constructibilité) que ZFC seul ne démontre pas, et qui donnent aux ensembles constructibles une structure beaucoup plus riche que les ensembles tout seuls. Pour donner une idée, voici un des principes les plus faciles à énoncer, l'hypothèse de Kurepa, qui (sous l'hypothèse de consistance d'un cardinal inaccessible) est indémontrable dans ZFC, et qui découle de ZFC+(V=L) :

Il existe un ensemble F de ℵ₂ parties de ω₁ tel que pour chaque α<ω₁ l'ensemble des Xα avec X parcourant F soit dénombrable.

(Autrement dit, F a ℵ₂ éléments, mais si on les « coupe » aux ordinaux <α, pour n'importe quel α<ω₁ fixé, il n'y en a plus que ℵ₀ différents.)

Ce n'est peut-être pas extrêmement parlant (ni, à vrai dire, extrêmement intéressant), mais ceci donne un exemple du genre d'énoncés combinatoires indécidables dans ZFC et que l'axiome de constructibilité tranche, et la construction a la vertu de ne pas être trop compliquée : on peut prendre pour F l'ensemble des parties X de ω₁ telles que pour tout α<ω₁ l'ensemble Xα appartienne à Lf(α), où f(α) désigne le plus petit ordinal admissible >α qui « voit » que α est dénombrable (c'est-à-dire que Lf(α) vérifie d'une part le fragment Kripke-Platek de la théorie des ensembles et d'autre part contient une injection de α dans ω)[#6].

Quelques conséquences mathématiques

Maintenant, le matheux non spécialiste de la théorie des ensembles s'intéressera fort peu aux questions d'ordinaux, et notamment, trouvera l'hypothèse de Kurepa énoncée ci-dessus totalement insipide : il voudra peut-être savoir s'il existe des principes plus proprement mathématiques (i.e., non ensemblistes) qui découleraient de ZFC+(V=L) mais pas de ZFC seul. On n'en connaît pas énormément, mais voici au moins quelques exemples (je donne des énoncés qui sont vrais dans l'univers constructibles) :

  • (Le problème de Whitehead.) Si M est un groupe abélien tel que Ext¹(M,ℤ)=0 (c'est-à-dire : un groupe abélien tel que toute suite exacte courte 0→ℤ→EM→0 soit scindée, i.e., E≅ℤ⊕M par les flèches données), alors M est libre (i.e., isomorphe à une somme directe de copies de ℤ).
  • (Le problème de Suslin.) Il existe une « droite de Suslin », c'est-à-dire un ensemble totalement ordonné, dense, sans extrémités, dans lequel toute famille d'intervalles deux à deux disjoints est au plus dénombrable, et qu'on peut supposer complet, et qui n'admet cependant pas de partie dénombrable dense (c'est-à-dire, avec l'hypothèse de complétude : qui n'est pas isomorphe à ℝ).
  • Tout espace topologique localement séparable (=« first countable » : tout point a un système fondamental de voisinages qui soit dénombrable), séparé et normal (=deux fermés disjoints ont des voisinages disjoints) est séparé en famille (=pour toute famille fermée discrète de points de l'espace on peut trouver une famille de voisinages deux à deux disjoints de ces points).
  • Il n'existe pas de mesure dénombrablement additive définie sur toutes les parties de ℝ et qui prolonge la mesure de Lebesgue.
  • Il existe une partie de ℝ qui est le complémentaire de la projection d'un borélien de ℝ² (on dit que c'est un Π¹₁ gras ou co-analytique), qui est indénombrable, et qui ne contient pas de fermé non vide sans point isolé (autrement dit, elle n'a pas la propriété de l'ensemble parfait). Dans le même esprit : il existe une partie de ℝ qui est la projection du complémentaire dans ℝ² de la projection d'un borélien de ℝ³ (on dit que c'est un Σ¹₂ gras) et qui n'est pas Lebesgue-mesurable. [Pour mettre ces énoncés dans le contexte, la projection sur ℝ d'un borélien de ℝ², appelé ensemble Σ¹₁ gras ou suslinien ou encore analytique, est toujours Lebesgue-mesurable et a toujours la propriété de l'ensemble parfait : c'est un théorème de ZFC qui ne fait pas appel à la constructibilité.]

Pour en savoir plus

Pour ceux qui voudraient en savoir plus, je renvoie à deux livres du même Keith Devlin. L'un s'appelle Constructibility, et il est disponible en ligne : il décrit très clairement le fonctionnement de l'univers constructible, à partir de prérequis très bas (le premier chapitre rappelle ce qu'il faut savoir de théorie des ensembles et le second définit précisément l'univers constructible), pour en exposer les principes combinatoires standards, et des choses plus sophistiquées comme la structure fine et les morasses. L'autre livre s'appelle The Axiom of Constructibility: A Guide for the Mathematician : comme son nom l'indique, il s'adresse aux matheux qui ne sont pas théoriciens des ensembles, et tente d'expliquer comment « utiliser » l'axiome de constructibilité (un peu comme on utiliserait l'axiome du choix) sans rentrer dans trop de technicité ; on y trouvera notamment la preuve de la plupart des conséquences mathématiques mentionnées ci-dessus (à partir de principes combinatoires du genre ).


[#] Élaborons un peu :

Pour reprendre un de mes dadas, le socle de toutes les mathématiques, ce sont les entiers naturels (0, 1, 2, 3, 4, etc.), ou plutôt ce qui peut être « codé » avec eux, c'est-à-dire les structures finies (par exemple les nombres rationnels ou algébriques, les graphes finis, les groupes finis, les chaînes finies de caractères sur un alphabet fini fixé, les suites finies d'entiers, ce genre de choses). Un point de vue philosophique que j'ai souvent exposé ici (pour ne pas dire rabâché) est que ces choses-là existent vraiment dans une sorte de paradis platonique ; je ne veux pas revenir là-dessus (voir notamment ici et sur ce que j'ai déjà dit à ce sujet). Sans admettre forcément cette position, convenons au moins qu'on comprend plus ou moins les entiers naturels et qu'on sait ce que c'est.

Après les structures finies, il faut se tourner vers les structures infinies, et « ce qu'elles sont ». Les plus simples possibles, ce sont par exemple les ensembles d'entiers naturels (=parties de ℕ), ou, ce qui revient quasiment au même, les suites infinies de 0 et de 1 (=fonctions ℕ→{0,1}), ou encore les nombres réels (les suites d'entiers naturels, et même les suites de nombres réels reviennent encore toutes plus ou moins au même en ce qu'on peut « coder » toutes ces choses-là par des suites de 0 et de 1) ; pour prendre un terme un peu vieillot, on peut aussi dire : le continu (qu'on définit comme un des objets précédents, disons les suites de 0 et de 1).

Une des questions centrales que doit se poser la philosophie des mathématiques est donc ceci : quelles sont (toutes) les suites infinies de 0 et de 1 ? Écrite comme ça, la question semble évidemment dénuée de sens : toutes les suites de 0 et de 1, ce sont juste toutes les suites possibles dont tous les termes sont des 0 et des 1 ; pourtant, une des questions les plus basiques qu'on peut se poser sur les suites de 0 et de 1 (le continu, donc) est : combien y en a-t-il ?, et si on peut dire à coup sûr qu'il y en a strictement plus que des entiers naturels, une réponse plus précise était un plus célèbres problèmes des des mathématiques (placé en premier dans la fameuse liste historique dressée par Hilbert en 1900), l'hypothèse du Continu, dont on sait maintenant qu'il est indécidable dans le cadre usuel de la théorie des ensembles ; l'axiome de constructibilité apportera sa réponse à ce problème particulier, et en un certain sens à la question philosophique ci-dessus.

[#2] Si on croit à certaines formes de la thèse de Church-Turing, rien de ce qui est physiquement réalisable dans cet univers n'est réellement aléatoire, parce que tout est toujours calculable au sens de Church-Turing. Mais la question est, à vrai dire, assez épineuse : voir notamment ici ce que j'écrivais sur le déterminisme de la physique quantique.

[#3] L'itération du saut de Turing jusqu'à l'ordinal dit de Church-Kleene, c'est-à-dire le plus petit ordinal qu'une machine de Turing ne peut pas décrire, est assez standard — cela s'appelle la théorie hyperarithmétique — et ne pose pas de difficulté majeure, je crois que c'est Kleene qui l'a décrite dans les années '50, peut-être simultanément avec Davis et Mostowski. Vers 1968, Putnam et plusieurs de ses étudiants ont poussé jusqu'à l'ordinal dit « de l'analyse ramifiée ». Et ce n'est qu'à la fin des années '70 qu'un certain Harold Hodes, en poursuivant sur les travaux de Jokusch et Stephen Simpson, a complètement décrit l'itération transfinie du saut de Turing aussi loin que la hiérarchie constructible le permet, c'est-à-dire jusqu'au ω₁ constructible, et a détaillé exactement le lien avec cette hiérarchie. Ce qui ne veut pas dire que, pour le niveau de généralité où je me place, on ne puisse pas considérer ce lien comme connu depuis bien plus longtemps.

[#4] Un exemple assez célèbre de conséquence de l'axiome du choix est le paradoxe de Banach-Tarski, selon lequel il est possible de couper une boule en un nombre fini de morceaux, déplacer ces morceaux et les réassembler pour former deux boules (ou une boule plus grosse). L'axiome de constructibilité rend cette construction explicite : plus exactement, on peut expliciter un tel découpage de la « boule constructible » — c'est-à-dire les points de la boule dont l'écriture binaire des coordonnées sont des suites constructibles — et l'axiome de constructibilité affirme que cette boule constructible est bien la « vraie » boule (mais si on n'y croit pas, on dira juste : ah, on a obtenu une décomposition paradoxale explicite d'un tout petit morceau de la boule, ça n'a rien d'impressionnant).

[#5] Il y a aussi que parmi les différents résultats de Jensen, je ne suis pas sûr de ce qui mérite d'être considéré comme le plus important. Entre autres choses, Jensen montre qu'il existe des « codes maîtres » (ou « codes standards ») pour les niveaux de la hiérarchie constructible, qui jouent un peu le rôle d'une généralisation du problème de l'arrêt pour les machines de Turing (ils « représentent » en quelque sorte les parties Σ₁, et plus généralement on peut en fabriquer pour les parties Σr), et ces codes maîtres sont assez naturels pour être préservés par des arguments de condensation.

[#6] J'esquisse la démonstration (même si, en la rédigeant, je me rends compte qu'elle est plus délicate que je pensais) :

Le fait que, avec cette construction, l'ensemble des Xα avec X parcourant F soit dénombrable est clair (ils appartiennent à Lf(α), qui est dénombrable car f(α) l'est). La chose plus délicate est que F ait pour cardinal ℵ₂.

L'idée de la preuve est la suivante. Si F est énumérable en une séquence (Xα) indicée par ω₁, tant qu'à faire on peut utiliser le bon ordre canonique sur L pour prendre la première énumération pour ce bon ordre (ce qui la rend canonique). On va alors utiliser un argument diagonal pour construire un Y qui appartient à F mais qui n'est pas un des Xα. L'idée évidente serait de considérer l'ensemble Y des α<ω₁ tels que αXα, mais on ne voit pas comment conclure que ce Y appartiendrait à F. À la place, on définit Y comme l'ensemble des αν tels que ανXναν est une séquence croissante continue, indicée par ω₁, qui doit encore être définie. L'argument diagonal montre que Y n'est pas un des Xν. Pour montrer que YF (et donc une contradiction), il s'agit de montrer que YαLf(α) quel que soit α. On peut évidemment supposer que α=αη, et, quitte à faire la différence avec un ensemble fini, on peut supposer que η est un ordinal limite. Le point-clé est de trouver la séquence αν de façon que (αν)ν et (Xνα)ν soient tous deux dans Lf(α) (ce qui montrera que Yα l'est en utilisant quelques constructions dans Kripke-Platek).

Il reste donc à choisir αν. C'est là qu'intervient le « jeu de miroirs » : on va définir des Nν qui imitent un bout assez gros de la hiérarchie constructible, disons Lω. Précisément, par induction sur ν, on définit un sous-ensemble Nν de Lω : on définit N0 comme le plus petit sous-modèle élémentaire de Lω (il s'agit, en fait, des éléments de celui-ci qui sont définissables sans paramètres), puis Nν+1 comme le plus petit sous-modèle élémentaire N de Lω tel que Nν∪{Nν} ⊆ N (et pour les ordinaux limites δ, on définit Nδ comme la réunion des Nν pour ν<δ). Ces ensembles sont dénombrables. Par des arguments autour du lemme de condensation, Nν est isomorphe à un Lβν et son intersection avec Lω est (exactement) un Lαν avec αν dénombrable (à savoir l'ordinal qui fait semblant d'être ω₁ dans Lβν) : c'est ce qui définit la séquence αν.

Comme Lβν croit que αν est indénombrable (puisqu'il le voit comme ω₁), alors que Lf(αν) le voit comme dénombrable (par définition de f), on a βν < f(αν). Par ailleurs, F et l'énumération (Xξ)ξ<ω sont définissables dans Lω, donc appartiennent à tous les Nν, et (Xξ)ξ<ω se condense sur (Xξαν)ξ<αν (c'est-à-dire, est envoyé sur cet élément par l'isomorphisme de Nν sur Lβν). Ceci montre que (Xνα)ν appartient bien à Lβη, donc à Lf(α). Pour ce qui est de (αν)ν, il s'agit de se convaincre que la construction des αν peut se mener à l'intérieur de Lf(α) : certes, ω₂ n'a pas de sens dans Lf(α), mais ce n'est pas un problème : βη, lui, y est, or Lβη est isomorphe à Nη et ce dernier est un sous-modèle élémentaire de Lω.

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

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