David Madore's WebLog: Comment un mathématicien ouvre une infinité de boîtes

Peut-on avoir une stratégie calculable ?

Supposons un instant que nos mathématiciens soient, en fait, des informaticiens : ils ne peuvent calculer que les fonctions calculables effectivement par une machine de Turing ; plus exactement, il doit exister une machine de Turing T qui, quand on l'exécute en lui fournissant un entier naturel n et un oracle u (dont elle peut interroger librement les valeurs mais seulement celles qui sont au moins égales à n+1) doit terminer et renvoyer φ(u)(n). (On souligne qu'une machine de Turing ne peut évidemment, au cours de son exécution, interroger qu'un nombre fini de valeurs de l'oracle.) Or, dans ces conditions, les informaticiens ne peuvent pas être certains d'être libérés : en effet, si le Docteur No a connaissance[#] de la machine de Turing T qui sera utilisée par les informaticiens, il peut lancer l'exécution de T sur le nombre n₀=0 en fixant arbitrairement la valeur de u(k) lorsque la machine T interroge l'oracle en k (forcément différent de 0 par hypothèse), puis choisir une couleur de chapeau u(0) pour l'informaticien 0 qui soit différente de la valeur retournée par T pour ce calcul (qui se fait en temps fini puisque T est censée toujours terminer) ; puis il lance l'exécution de T sur le premier nombre n₁ pour lequel la valeur de u n'a pas encore été fixée, et de nouveau, à chaque fois que la machine T interroge l'oracle sur une valeur non encore déterminée de u, elle est fixée arbitrairement, et à la fin u(n₁) est choisi différent du nombre renvoyé par T. Et ainsi de suite : alors les informaticiens n₀, n₁, n₂, etc., se tromperont tous, donc le Docteur No aura réussi son plan diabolique.

On voit même, d'ailleurs, que dans l'opération, le Docteur No peut lui-même être un informaticien, car j'ai présenté un programme effectif qui calcule la fonction u de couleur à donner aux chapeaux (pour mettre en défaut des informaticiens qui utiliseraient une machine de Turing T connue). Par ailleurs, je n'ai essentiellement rien utilisé sur les machines de Turing, donc ceci vaut encore si on les remplace par des machines plus puissantes, par exemple si les informaticiens et le Docteur No disposent d'un oracle de l'arrêt des machines de Turing (elles-mêmes sans oracle), ou de même pour tout degré de Turing : si on demande aux fonctions φ et u d'être arithmétiques (= définissables dans l'arithmétique de Peano, c'est-à-dire exactement appartenant au degré de Turing 0^(ω)), on a donc la même conclusion (à ce stade-là, ce ne sont plus vraiment des informaticiens, ce sont plutôt des mathématiciens finitistes).

[#] Là, normalement, quelqu'un va protester que je n'ai pas mis dans mes hypothèses que le Docteur No connaît la stratégie des informaticiens ! Mais je cherche à prouver que les informaticiens n'ont pas de stratégie leur permettant d'être libérés à coup sûr : or s'ils en avaient une, utilisant la machine de Turing T, elle devrait fonctionner même si le Docteur No connaissait cette machine T — il peut, après tout, très bien avoir vu juste par hasard.

En revanche, si les informaticiens disposent d'un oracle de l'arrêt des machines de Turing et que le Docteur No n'en dispose pas (ou plus généralement si les mathématiciens ont un saut de Turing d'avance sur le Docteur No), alors les informaticiens ont de nouveau l'avantage. En effet, l'informaticien numéro i va considérer les i premières machines de Turing et, pour chaque couple de deux (T,T′) parmi elles, en utilisant l'oracle dont il dispose, déterminer s'il existe un j>i telles qu'elles calculent une valeur différente en j (ou au contraire si elles calculent systématiquement la même valeur en tout j>i) ; il fixe alors N>i suffisant pour garantir que si deux machines (T,T′) parmi les i premières calculent toujours les mêmes valeurs pour les j entre i+1 et N, alors elles calculent les mêmes valeurs pour tout j>i. En observant la couleur des chapeaux numérotés par j entre i+1 et N, il élimine les machines de Turing qui ne calculent pas des valeurs conformes à ces observations : si T est la première qui s'y conforme, alors il prédit pour son propre chapeau la couleur renvoyée par T (appliquée au nombre i). Dans ces conditions, si le Docteur No calcule les couleurs des chapeaux en utilisant une machine de Turing, et si T_k (la machine de Turing numérotée k) est la première qui calcule les couleurs des chapeaux ainsi choisis à partir d'un certain rang fini (disons n₀), alors les informaticiens portant un numéro supérieur au max de k et de n₀ vont tous répondre juste puisqu'ils utiliseront justement cette machine T_k pour déterminer la couleur de leur chapeau.

[Correction (2014-06-22T02:25+02:00) : l'argument en question utilise deux niveaux d'oracle d'arrêt (pour décider si une fonction partielle récursive est totale, ou si deux fonctions partielles récursives prennent les mêmes valeurs à partir d'un certain rang, il faut avoir accès au degré de Turing 0″ et pas juste 0′). Voici une modification de la stratégie qui, je crois, doit marcher avec le seul oracle de l'arrêt. Soit f une fonction strictement croissante fixée qui croît plus vite que toute fonction calculable (il n'est pas difficile de fabriquer ça avec l'oracle de l'arrêt, par exemple la fonction « castor affairé »). L'informaticien numéro i va considérer les i premières machines de Turing, va calculer les valeurs prises par chacune d'elle sur les entrées comprises entre i+1 et f(i) (ceci demande l'oracle de l'arrêt pour savoir si les calculs terminent effectivement), va comparer les valeurs calculées avec les observations des chapeaux, et va retenir le plus petit indice pour lequel la machine prévoit les bonnes couleurs : il annonce alors la valeur renvoyée sur l'entrée i de la machine en question. Dans ces conditions, si le Docteur No calcule les couleurs des chapeaux en utilisant une machine de Turing, et si T:=T_k (la machine de Turing numérotée k) est la première qui calcule les couleurs des chapeaux ainsi choisis à partir d'un certain rang fini, alors pour toute machine T′ d'indice plus petit que k et calculant une fonction totale, comme il y a une infinité de différences entre T et T′ et que la fonction qui à n associe l'indice de la différence suivante est calculable, la fonction f la domine, donc au bout d'un certain rang les informaticiens calculent bien la couleur de leur chapeau avec T, et ils ont raison.]

Doit-on utiliser l'axiome du choix ?

Maintenant que les informaticiens qui n'ont pas d'oracle dans leur poche se sont fait impitoyablement trucider par le Docteur No, reprenons des mathématiciens.

Une stratégie φ:{0,1}^ℕ→{0,1}^ℕ des mathématiciens leur permettant de passer l'épreuve du cruel Docteur No est, on l'a dit, une fonction φ telle que pour u une suite quelconque φ(u) et u coïncident à partir d'un certain rang, et que si u et v coïncident à partir d'un rang n alors φ(u) et φ(v) coïncident à partir du rang n−1. Maintenant, imaginons qu'on à partir d'une suite u on itère la fonction φ (ou, si on veut, chaque mathématicien remplace son chapeau par celui qu'il croit avoir en fonction des mathématiciens devant lui — mais seul un nombre fini d'entre eux change de chapeau en ce faisant puisque la stratégie était bonne — et on itère le processus) : on voit facilement qu'on tombe ainsi en un nombre fini d'étapes sur un point fixe, que je vais appeler φ_∞(u), lequel coïncide toujours avec u à partir d'un certain rang, et que si u et v coïncident à partir d'un certain rang, alors φ_∞(u) et φ_∞(v) sont exactement égales. Or en fait, la fonction φ_∞ convient tout aussi bien que la fonction φ (elle vérifie les propriétés supposées de cette dernière), donc rechercher une stratégie pour les mathématiciens revient exactement à chercher une telle fonction φ_∞ : il s'agit d'une section (un choix de représentants) pour la relation d'équivalence « coïncider à partir d'un certain rang », appelons-la ∼, sur les suites.

Visiblement le choix d'un élément dans chaque classe d'équivalence pour ∼ fait appel à l'axiome du choix. Évidemment, ça ne prouve pas qu'on ne puisse pas faire autrement : je vais donc esquisser une démonstration du fait qu'on ne peut pas démontrer l'existence de cette section dans ZF (s'il est consistant…) en l'absence de l'axiome du choix. Autrement dit, je veux montrer qu'il existe un modèle N de ZF dans lequel la surjection canonique 2^ω↠2^ω/∼ n'admet pas de section. Comme c'est un peu fastidieux (et plus fastidieux encore vu qu'il s'agit d'écrire ça en HTML, qui sera sans doute illisible pour tout le monde faute de polices Unicode assez complètes), et vu qu'environ 0.42 lecteurs vont lire le zblurgh qui suit (ceux qui peuvent le comprendre peuvent probablement l'inventer eux-mêmes), je vais être un peu elliptique. Mais il y a à la fin des choses que je ne sais pas démontrer concernant l'axiome du choix dépendant : voir plus bas.

On appelle (dans un modèle M de ZFC) P l'ensemble partiellement ordonné formé des fonctions définies sur un sous-ensemble fini de ω₁×ω et à valeurs dans 2={0,1}, partiellement ordonné par l'inclusion réciproque (q≤p, i.e., q est plus fort que p, lorsque q prolonge p), et on appelle B l'algèbre de Boole complété de P, c'est-à-dire l'algèbre de Boole (complète) des ouverts réguliers sur l'espace topologique 2^ω₁×ω (muni de la topologie produit). Soit D un ultrafiltre B-générique (ou son nom canonique dans le modèle M^B à valeurs dans B) : autrement dit, M[D] est le modèle qui ajoute ℵ₁ réels génériques que je vais appeler x_α (je vais expliquer plus loin pourquoi j'en utilise ℵ₁ et pas simplement ℵ₀). Pour chaque α∈ω₁, soit x_α:ω→{0,1} la réunion des p(α,·) pour p dans D ; soit c_α la classe de x_α modulo ∼.

Soit G ≅ ∏_α∈ω1 ⨁_i∈ω (ℤ/2ℤ) le groupe (commutatif) des automorphismes σ_X de P (ou de B) où X⊆ω₁×ω parcourt les ensembles tels que chaque X∩({α}×ω) (pour α∈ω₁) soit fini, où σ_X agit sur p∈P en échangeant (entre 0 et 1) la valeur de p sur les couples (α,i) appartenant à X (et sur lesquels p est défini) : concrètement, G est donc constitué des automorphismes de P qui changent la valeur des p∈P(α,i) en un nombre fini de i pour chaque α. Soit F le filtre (normal) de sous-groupes de G engendré par les Fix(E) avec E⊆ω₁ dénombrable, où par Fix(E) on désigne l'ensemble des σ_X pour lesquels X⊆E×ω. Soit N le modèle symétrique associé à la situation, c'est-à-dire le modèle formé des éléments de M[D] qui ont un nom hériditairement symétrique (i.e., fixé par un Fix(E)). Manifestement, chaque x_α est dans N, ainsi que chaque c_α : mais même la fonction α↦c_α elle-même est dans N (puisqu'elle — ou plutôt son nom évident — est fixée par tout σ_X). En revanche, il est assez clair, et on va le justifier dans un instant, que la fonction α↦x_α, elle, n'est pas dans N (c'est une fonction de choix pour α↦c_α). Ce N est un modèle de ZF ; on veut prouver que la fonction α↦c_α n'a pas de fonction de choix (et en particulier 2^ω↠2^ω/∼ n'a pas de section).

Supposons donc pour cela que h:ω₁→2^ω soit une fonction de choix pour α↦c_α (ici comme ailleurs, par ω₁ on entend ω₁^M, i.e., le ω₁ du modèle initial — il se trouve qu'il est égal à ω₁^M[D], et donc ω₁^N, parce que P vérifie la condition de chaîne dénombrable, mais il me semble qu'on n'en aura pas besoin). On appelle aussi abusivement h un nom symétrique pour cette fonction ; mettons qu'il soit fixé par Fix(E) avec E dénombrable. Soit p dans D qui force (⊩) h à être une fonction ω₁→2^ω telle que h(α)∈c_α pour tout α∈ω₁. Soit γ supérieur à chaque élément de E. Soit q≤p et n₀∈ω tel que q ⊩ si i≥n alors h(γ,i)=x_γ(i). Soit k≥n et tel que k soit supérieur à i pour tout (γ,i) dans le domaine de q. Soit π=σ_{(γ,k)}. Alors π(q) et q sont égaux : alors (comme π(h)=h tandis que q ⊩ π(x_γ)(k)=1−x_γ(k)), on a q ⊩ h(γ,k)=1−h(γ,k), une contradiction.

Ce qui précède montre qu'en l'absence de l'axiome du choix, on ne peut pas prouver que 2^ℕ↠2^ℕ/∼ a une section. Mais ce qui me chagrine fort, c'est que je n'arrive pas à tordre le cou à l'axiome du choix dépendant (abrégé en DC ci-après) : j'étais parti pour construire un modèle qui vérifie l'axiome du choix dépendant (c'est pour cette raison que j'ai rédigé avec ω₁ et pas ω : comme l'axiome du choix dépendant implique l'axiome du choix dénombrable, on ne va pas arriver à avoir DC et à éviter d'avoir une fonction de choix pour les classes d'un nombre dénombrable de suites génériques), et j'ai lamentablement échoué. Dans le modèle que je viens de décrire, je ne sais pas si DC est vérifié, car bien que le filtre F permette de fixer un ensemble E dénombrable de α∈ω₁, pour construire une suite de choix dépendants à partir d'une relation, j'aurais besoin de borner inférieurement une suite de conditions de forcing, et ce n'est visiblement pas possible ; ou alors je remplace P par l'ensemble, plus fin, des fonctions partielles à domaine au plus dénombrable dans ω₁×ω (toujours à valeurs dans 2, évidemment), le reste étant inchangé : dans ce cas il est facile de voir que DC est vérifié dans le modèle symétrique, mais je ne sais plus montrer que α↦c_α n'a pas de fonction de choix, car la phrase tel que k soit supérieur à i pour tout (γ,i) dans le domaine de q dans la démonstration ci-dessus n'est plus juste (en gros, le problème est que les réels x_α sont beaucoup moins génériques avec cette condition de forcing plus fine — d'ailleurs, un nombre dénombrable d'entre eux peut très bien être dans M — du coup, on ne peut rien conclure avec un seul x_α, et je n'arrive pas à en exploiter une infinité non dénombrable à la fois). Pourtant, je reste complètement persuadé que DC ne suffit pas à démontrer l'existence d'une section ; mais j'ai passé deux jours à m'y arracher les cheveux et à essayer toutes sortes de variantes sur mes conditions de forcing, en vain, alors je dois être vraiment mauvais sur ce coup, et je vais demander de l'aide à des gens plus savants que moi. Si par hasard un lecteur sait comment faire, qu'il m'explique.