86] Logique et calcul © Pour la Science - n° 384 - Octobre 200986] Logique et calcul86] Logique et calcul86] Logique et calcul

L ’ar t ic le de septembre 2009soumettait aux lecteurs un pro-blème de chapeaux. Sa solu-t ion va nous préc ipiter dans

une sorte de folie mathématique, dont lagravité n’a sans doute pas encore été plei-nement mesurée aujourd’hui.

L’énigme de départ est la suivante.Une assemblée infinie de joueurs J(1),

J(2), J(3), ..., J(n), ... participe à un jeu avecdes chapeaux qui peuvent avoir l’une des

couleurs C(1), C(2), C(3), ..., C(n), ... (il y aune infinité de couleurs possibles).

Après une phase de discussion pendantlaquelle les joueurs peuvent convenir d’unestratégie à appliquer, les joueurs n’échan-gent plus aucune information et l’arbitredépose sur la tête de chaque joueur un cha-peau coloré choisi par la méthode qu’il veut.Une couleur peut être utilisée plusieurs fois,ou pas du tout. Chaque joueur voit tous leschapeaux sauf le sien et tente de deviner

la couleur du chapeau qu’il porte. Les joueursdonnent leurs réponses simultanément.

(a)Les joueurs peuvent-ils convenir d’unestratégie assurant, quelle que soit la distri-bution de chapeaux, qu’au moins l’un d’euxindique la couleur exacte de son chapeau ?

(b) Les joueurs peuvent-ils convenird’une stratégie qui assure, quelle que soitla distribution de chapeaux, que tous lesjoueurs sauf un nombre fini d’entre eux indi-quent la couleur exacte de leur chapeau ?

Une folie mathématiqueQu’on puisse démontrer que (presque) tout est prévisible est inquiétant,et devrait faire douter de certains axiomes qui, sous des dehors innocents,produisent de graves absurdités.Jean-Paul DELAHAYE

REGARDS

LOGIQUE & CALCUL

mathématiques

1. Seuls un nombre fini de porteurs se trompent !

Une infinité de personnes portent des chapeaux colorés. Chacune voitla couleur des chapeaux des autres, mais n’a aucun moyen de voir

la couleur du sien. Sans que les participants puissent communiquer,une procédure décrite dans le texte permet à presque tous (sauf unnombre fini d’entre eux) de deviner la couleur de leur chapeau. En défi-nissant, comme il est d’usage, la probabilité de deviner la bonne cou-

leur de son chapeau par 1 moins le quotient des cas défavorables (ennombre fini) par le nombre de cas favorables (en nombre infini), alorscette probabilité est de 1 : les individus ont chacun la « certitude » dedeviner la couleur de leur propre chapeau. Toutefois, pour que cette pro-cédure soit applicable, il faut accepter l’axiome du choix qui, encoreune fois, est la source de grandes difficultés.

pls_384_p086092_delahaye.xp2 7/09/09 17:56 Page 86

© Pour la Science - n° 384 - Octobre 2009 Logique et calcul [87

R e g a r d s

La réponse est oui pour (b) et doncaussi pour (a).

Ceux qui ont cherché à résoudre leproblème seront sans doute assez étonnés,car répondre positivement à la question (a)semble dé jà impossible. De plus, on vavoir que l’idée de la solution amène d’autressituations totalement absurdes qui signi-fient en gros que presque tout est prévi-sible. Des généralisations de l’idée utiliséeont d’ailleurs conduit Christopher Hardin etAlan Taylor à des théorèmes particulière-ment troublants sur l’induction scientifique.Ces résultats purement mathématiques ontdéjà attiré l’attention de plusieurs philo-sophes qui y voient un défi pour la philo-sophie des sciences.

Un nombre finid’erreurs au plusDémontrons que la réponse à (b) est oui.Lors de la phase de concertation, les joueursc lassent toutes les d istr ibut ions pos-sibles en paquets. Deux distributions dechapeaux sont mises dans un même paquetsi el les coïncident pour toutes les cou-

leurs des chapeaux des joueurs, sauf pourun nombre fini d’entre eux. Si, par exemple,la distribution A de chapeaux et la distribu-tion B sont identiques sauf pour les joueurs1, 2, 6 et 10, elles sont mises dans le mêmepaque t . Les joueurs chois issent a lors,d’un commun accord, une d istr ibut ionemblématique dans chaque paquet.

Lors du jeu, un joueur, voyant les cha-peaux des autres joueurs, sait à quel paquetappartient la distribution choisie par l’arbitre.Il lui manque juste la couleur de son chapeau,ce qui ne l’empêche pas de reconnaître lepaquet auquel appartient la distribution.

La stratégie de jeu, dont les joueursconviennent avant que l’arbitre pose les cha-peaux, est que chaque joueur, après avoirrepéré le paquet auquel appartient la distri-bution choisie par l’arbitre, considérera la dis-tribution emblématique qui a été sélectionnéedans ce paquet et fera le pari que la couleurde son chapeau est celle que cette distribu-tion emblématique lui attribue. En opérantainsi, un nombre fini de joueurs, au plus, setrompent, car la distribution A choisie par l’ar-bitre ne diffère de la distribution embléma-tique R (que chacun prend comme repère

pour formuler son pari) que par un nombrefini d’attributions de couleurs. Seuls les joueurs– en nombre fini – correspondant à ces dif-férences entre A et R se trompent.

Aussi étonnante qu’elle para isse, laméthode fonctionne ! Les habitués de lathéorie des ensembles auront reconnul’utilisation de l’axiome du choix pour défi-nir la stratégie de l’assemblée des joueurs.Expliquons cet axiome et son statut mathé-matique.

L’axiome du choix dans sa forme la plussimple affirme l’évidence suivante : si unensemble d’ensembles non vides et deuxà deux disjoints est fixé, par exemple E = {{0,1, 2, 3, ...} , {a, b} , {P, Q, R} } , alors il existeau moins un ensemble C ayant un élémentcommun avec chaque ensemble de E, ici,par exemple, C = {276, a, R} . L’ensemble Cest obtenu en choisissant un élément danschaque ensemble de E, d’où le nom del’axiome.

Dans notre démonstration, l’assembléeconsidère l’ensemble E des paquets (chaquepaquet est non vide et deux paquets diffé-rents sont disjoints) et choisit une distri-bution emblématique dans chaque paquet.

Logique et calcul [87Logique et calcul [87Logique et calcul [87

L ’axiome du choix est l’affirmation que lors-qu’un ensemble E d’ensembles non vides dis-

joints deux à deux est donné, on peut composerau moins un (en fait beaucoup) ensemble C enchoisissant un élément dans chaque ensemblede l’ensemble E d’ensembles.

Exemple d’ensemble d’ensembles finis :

E = {{1,2,3}, {10,11,12,13}, {100,101}, {1000,1001, 1002, 1003, 1004}}. Ensemble de choix :C = {2, 13, 100, 1003}.

Exemple d’ensemble d’ensembles infinis : E = {{2, 4, 8, 16,...}, {3, 9, 27,...}, {5, 25, 125,...},...}.E est composé de l’ensemble des puissancesde 2, de l’ensemble des puissances de 3, et ainsi

de sui te pour tous les nombres premiers.Ensemble de choix : C = {32, 27, 5, 49, 121,...}.Lorsqu’un ensemble d’ensembles est défini,l’axiome du choix (qui n’est vraiment indis-pensable que dans les cas infinis) fournit doncune méthode pour disposer d’un « représen-tant » dans chaque ensemble.

2 . Paquets et choix de représentants

pls_384_p086092_delahaye.xp2 7/09/09 17:56 Page 87

88] Logique et calcul © Pour la Science - n° 384 - Octobre 2009

R e g a r d s

L’existence de ce choix systématique d’unedistribution « repère » dans chaque paquetest la clef de la solution, laquelle repose doncsur une utilisation de l’axiome du choix.

Cet axiome du choix a connu une his-toire mouvementée. Formulé par Ernst Zer-melo en 1904, il avait en fait été utilisé avantcette date par de nombreux mathémati-ciens sans qu’ils en aient conscience tantil est naturel et semble bénin. Ce fut notam-ment le cas du mathématicien frança isÉmile Borel qui, pourtant, quand la contro-verse se développa, fit partie des mathé-ma t ic iens qu i propos èrent de re je terl’axiome du choix. Cet axiome joue un rôlecentral dans la démonstration de nombreuxthéorèmes dont cer ta ins très s implescomme celui qui affirme que la taille de deuxensembles – leur cardinal – est toujourscomparable (soit les cardinaux sont égaux,soit l’un des deux est plus grand que l’autre).

De plus, Kurt Gödel et Paul Cohen ontdémontré que l’axiome du choix est indé-pendant des autres axiomes de la théoriehabituelle des ensembles (notée ZF pourZermelo-Fraenkel). Cela signifie que si ZFn’est pas contrad ictoire , a lors ZF + AC(ZF auquel on ajoute l’axiome du choix) nel ’est pas non plus, e t que ZF+non AC(ZF auquel on ajoute la négation de l’axiomedu choix) ne l’est pas plus.

La grande utilité de l’axiome du choix,l’évidence de son énoncé et le résultat d’in-

dépendance ont conduit la plupar t desmathématiciens à l’accepter. Quand onrecherche de nouveaux axiomes pour ZF(voir cette rubrique en août 2008), on le faitle plus souvent en considérant ZF + AC quiaujourd’hui est, de facto, la base axioma-tique standard des mathématiques.

La multiplicationdes sphèresPlusieurs paradoxes résultent de l’utilisa-tion de l’axiome du choix dont le plus éton-nant est le paradoxe de Banach-Tarski. Eneffet, l’axiome du choix permet de démontrerqu’il existe un découpage d’une sphère derayon 1 en cinq morceaux disjoints, qui, dépla-cés dans l’espace et bien agencés, donnentdeux sphères de rayon 1.

Ce résultat de dédoublement miracu-leux n’est pas considéré comme un véri-table paradoxe mathématique, car i l neconduit à aucune contradiction. Le fait queles morceaux utilisés pour décomposer lasphère soient extrêmement compliquéset ne possèdent pas de volume au sens dela théorie de la mesure conduit à juger quele résultat n’est pas opposé à l’intuition, quine peut appréhender que des morceaux d’es-pace mesurables. Les mathématiciens consi-dèrent que le découpage de Banach-Tarskiexiste bel et bien, mais qu’il ne concerneni la géométrie habituelle ni la physique et

donc que nous ne devons pas nous en éton-ner. Selon ce point de vue, le théorème deBanach-Tarsk i ne reme t pas en causel’axiome du choix.

Cependant, certains mathématiciensinsistent sur l’idée qu’un système (ZF + AC)dans lequel on peut démontrer que quelquechose existe (par exemple le découpageé trange de la sphère) sans pouvoir enproposer de construction entièrement pré-cise (le théorème de Banach-Tarski dit « ilexiste ....» et ne construit pas vraiment ledécoupage) n’est pas satisfaisant. C’estbien la situation où nous nous trouvonsquand on utilise l’axiome du choix et il amême été démontré que, dans certainess ituat ions (dont ce l le du théorème deBanach-Tarski), les objets dont il permet deprouver l’existence ne peuvent pas êtreconstru i ts en ut i l isant seu lement lesaxiomes de ZF.

Une position moins tranchée que l’ac-ceptat ion ou le refus est dé fendue pardivers mathématiciens, dont Horst Herr-lich qui y a récemment consacré un livre.Cette position, qu’on pourrait nommer lepragmatisme ensembliste, défend qu’ilfaut s’occuper de l’axiome du choix et explo-rer deux sciences mathématiques, cellequi l’adopte comme principe et l’uti l isesans retenue, et celle qui tente de voir cequ’on peut faire sans lui ou même en adop-tant des axiomes qui le contredisent. Ce

« C’est le grand et ancien problème del’existence qui est au cœur de la contro-verse autour de l’axiome du choix » expli-quait Waclau Sierpinski (1882-1969),portrait à gauche.

L’axiome du choix, formulé par ErnstZermelo, énonce une affirmation d’exis-tence sans donner un moyen effectif deconstruire l’objet (ou au moins un exempled’objet) correspondant. Dans certainessituations, il est indispensable si l’onveut disposer d’un ensemble de choix. Lesmathématiciens intuitionnistes et construc-tivistes pensent qu’un résultat d’existencepure n’a de sens que s’il est accompagnéde méthodes précises de construction des

objets dont l’existence est affirmée : ilsrejettent donc l’axiome du choix.

Cependant, l’évidence intuitive deson énoncé de base, la démonstrationque l’ajouter ne peut introduire de contra-diction dans la théorie des ensembles(si elle n’en contient pas déjà sans lui)et la grande utilité dans de nombreuxdomaines des mathématiques abstraitesde l’axiome du choix font qu’aujourd’huiil est largement accepté.

D ’import ants résult a ts ut ilisentl’axiome du choix. Par exemple : (1) uneréunion dénombrable d ’ensemblesdénombrables est dénombrable ; (2) sideux ensembles A et B sont donnés, soit

on peut les mettre en bijection l’un avecl’autre, soit l’un a un cardinal strictementplus petit que l’autre (cet énoncé non seu-lement résulte de l’axiome du choix, maisest , en fait , équivalent à l’axiome duchoix) ; (3) il existe des ensembles de !non mesurables et des ensembles du plannon mesurables (c’est-à-dire n’ayant pasd’aire).

En revanche, on a démontré que toutrésultat d’arithmétique pure (ne faisant inter-venir que des nombres entiers (par exemple,il existe une infinité de nombres premiers,P!NP, etc.) s’il est démontrable dans ZF+ACest aussi démontrable dans ZF, c’est-à-diresans qu’il faille utiliser l’axiome du choix.

3. L'existence mathématique

pls_384_p086092_delahaye.xp2 7/09/09 17:56 Page 88

© Pour la Science - n° 384 - Octobre 2009 Logique et calcul [89

R e g a r d s

qui vient d’être mis en avant par les géné-ralisations de la méthode utilisée pour lasolution de notre problème de chapeauxsera un argument important pour le campdesopposants à l’axiome du choix (peunombreux aujourd’hui) et surtout pour lespragmatistes à la Herrlich.

Revenons à notre démonstration et aurôle particulier que l’axiome du choix y joue.

Dans l’article du mois dernier, on avaitnoté que certains problèmes de chapeauxdont l’énoncé était parfaitement symétrique(chaque joueur est dans une pos it ionéquivalente à celle des autres) ne se résol-vaient que grâce à une rupture de symétrieopérée par la stratégie gagnante. Ici, uneanalyse du même type est possible. La stra-tégie adoptée par l’assemblée rompt lasymétrie entre les joueurs parce qu’il faut,les numéroter.

Rupture de symétrieSurtout, elle rompt une autre symétrie entredistributions de chapeaux d’un même paquet :la distribution emblématique du paquet auraitpu être n’importe quelle autre, car toutes lesdistributions d’un même paquet sont com-binatoirement équivalentes. La distributionparticulière choisie (par utilisation de l’axiomedu choix) est essentielle, car elle permet àtous les joueurs de se coordonner (essayezd’éviter d’y avoir recours, vous échouerez !).Sans axiome du choix, il semble que cette

inévitable rupture de symétrie est impossibleà créer et donc que la coordination des joueursne peut se faire.

Pour circuler sur une route sans risquerd’accident, les automobilistes se coordon-nent et décident de tous rouler à droite(en France et presque partout en Europe).Cette rupture de symétrie est arbitraire,mais elle est indispensable. Dans l’universdes ensembles infinis, le problème des cha-peaux nous place dans une situation dumême type : il faut opérer une rupture desymétrie entre les distributions d’un mêmepaquet, et il faut opérer cette rupture pourchaque paquet. La théorie habituelle desensembles (ZF) manque de moyens pourcasser de telles symétries multiples et infi-nies et l’axiome du choix y tient donc un rôledécisif : sans lui, la symétrie des donnéesinterdit toute coordination.

Envisageons les généralisations du pro-blème des chapeaux infinis. La plus simpleconsiste à ne pas se limiter à un ensembleinfini dénombrable de joueurs ou à un infinidénombrable de couleurs. L’idée fonctionneparfaitement et laisse perplexe quand on yréfléchit. Considérons par exemple le cas d’uncontinuum de joueurs (un joueur pour chaquenombre réel) et d’un continuum de cou-leurs (une couleur possible pour chaquenombre réel). Bien qu’il soit plus difficile dedeviner sa couleur (désignée par un nombreréel quelconque), la stratégie des paquetspermet à nouveau à tous les joueurs, sauf un

nombre fini d’entre eux au plus, de devinerexactement la couleur de leur chapeau.

Fou, non ? Pourtant... la situation vaencore empirer.

Un seul joueurLa variante en ligne du problème nous rap-proche du problème de l’induction. El lesemble due à Yuval Gabay et Michael O’Con-nor qui la présentèrent en 2004 alors qu’ilsn’étaient qu’étudiants à l’Université de Cor-nell à Ithaca aux États-Unis.

Cette fois, les joueurs sont rangés lesuns derrière les autres de la façon sui-vante. Tous les joueurs sont tournés vers lagauche. Le joueur J(1) n’a personne derrièrelui et voit tous les autres chapeaux. Le joueurJ(2) juste devant J(1) voit tous les chapeauxJ(3), J(4)... Le joueur J(3), juste devant J(2),voit tous les chapeaux J(4), J(5), ... Etc.

La même stratégie et le même raison-nement que précédemment fonctionnentparfaitement dans cette nouvelle disposi-tion du jeu. Les joueurs devinent tous la cou-leur de leur chapeau, sauf un nombre finid’entre eux, quelle que soit la distributionde chapeaux choisie par l’arbitre et, bien quema intenant moins de chapeaux soientvisibles par chacun.

Cette disposition suggère une inter-prétation temporelle. Le chapeau du joueur nva maintenant représenter l’état du mondeà l’instant – n. Les différents paramètres

L a notion de bon ordre est importante si l’on veut com-prendre l’axiome du choix et les versions continues des

paradoxes de la prédiction. Voici quelques informations.Un bon ordre sur un ensemble E est une rela t ion

d’ordre telle que toute partie non vide F de E possède un pluspetit élément. L’ordre naturel sur les entiers positifs " = {0,1, 2, ...} est un bon ordre, car tout ensemble de nombresentiers possède un plus petit élément (autrement dit, dansun ensemble d’entiers même infini, il y a toujours un entierplus petit que tous les autres).

L’ordre na turel sur l’ensemble des entiers rela tifs# = {..., –2, – 1, 0, 1, 2, ...} n’est pas un bon ordre, car # lui-même n’a pas de plus petit élément. Si, en revanche, on défi-nit sur # l’ordre (artificiel) suivant : 0, 1, 2, ... n ... –1, –2, –3..., alors # est bien ordonné.

L’axiome du choix est équivalent (en utilisant les axiomesde la théorie usuelle des ensembles ZF) à l’affirmation quetout ensemble peut être (comme nous venons de le fairepour #) muni d’un bon ordre (la démonstration qui date de1904 est l’œuvre de Zermelo, (portrait à droite). Cette affir-mation est nommée principe du bon ordre.

Contrairement à l’axiome du choix qui est jugé évident,le principe du bon ordre est jugé contraire à l’intuition. Celaest dû en particulier à l’impossibilité de définir précisémentun bon ordre sur l’ensemble ! des nombres réels : l’axiomedu choix permet de démontrer qu’un tel bon ordre existe,mais toute tentative pour expliciter un tel bon ordre échoueet l’on sait même démontrer en utilisant les outils de lathéorie des modèles que toute tentative n’utilisant que ZFéchouera à définir précisément un bon ordre sur !.

4. L'impossible bon ordre sur !!

pls_384_p086092_delahaye.xp2 7/09/09 17:56 Page 89

pls_384_p086092_delahaye.xp2 7/09/09 17:56 Page 90

© Pour la Science - n° 384 - Octobre 2009 Logique et calcul [91

R e g a r d s

caractérisant cet état du monde sont syn-thétisés dans une seule variable, un entierou un nombre réel, représentant la cou-leur du chapeau. Le fait que le joueur n voittous les chapeaux situés à sa gauche se tra-duit ma intenant sous la forme : l’uniquejoueur (que nous appelons le joueur tem-porel) à l’instant – n a connaissance de toutle passé du monde qui est synthé t isédans les valeurs du paramètre aux instants(–n – 1), (–n – 2), (–n – 3), ... Cette infor-mation sur le passé lui étant donnée, il tentede deviner l’état présent du monde dont il

n’a pas connaissance (la couleur de sonchapeau à l’instant –n).

La stratégie décrite donne un résultat sur-prenant : avec un temps discret, l’observa-teur ayant connaissance du passé du mondepeut prédire l’état du monde, en ne se trom-pant qu’au plus un nombre fini de fois.

Celui qui décide dans quel état se trouvele monde n’est soumis à aucune contrainte :les états possibles du monde peuvent chan-ger du tout au tout d’une seconde à lasuivante, sans qu’aucun lien logique ne lesrelie ; ils sont arbitraires. Pourtant, pour

notre joueur temporel disposant de l’axiomedu choix, presque tout est prévisible !

Si l’évolution de l’univers était continue,ou était le résultat d’un ensemble de loisbien précises et déterministes, on com-prendrait que la connaissance du passé per-mette la déduction de l’état présent. Ce n’estpas le cas ici, mais grâce à (ou « à causede ») l’axiome du choix, une prédictionpresque parfaite de l’évolution d’un universtotalement arbitraire est possible.

Si les états du monde sont simplementdes pile ou face, le joueur temporel réussit

C omment survivre – mathématiquement – à cette folie, assimilable àla lecture d’une boule de cristal, qui semble nous dire que d'un point

de vue mathématique, la prédiction est toujours possible... et qu’il n’estmême pas nécessaire d'identifier des structures intelligibles dans le monde,ni même la moindre régularité dans la succession des états du passé ?

Plusieurs stratégies de défense sont envisageables pour retrouverle sommeil. Nous en présentons une petite liste sans chercher à trancherla question qui semble exiger de délicates précautions et qui, à n'en pasdouter, suscitera de nombreux commentaires.

! Renoncer à l'infini ou au moins à certains de ses usages. Il est bienclair que le problème provient de l'usage de l'infini. Si le passé ne s'étendpas au-delà d'un certain instant initial (que les cosmologistes nommentBig Bang) alors le raisonnement ne peut plus se dérouler dans sa versiondiscrète. Cependant, dans ses versions continues, le paradoxe persiste sion accepte l'idée d'un temps modélisé par des intervalles bornés de nombresréels, et donc il faudrait renoncer aussi à ce type de représentation pourle temps. Cela serait quand même payer très cher un paradoxe logique,et de toutes les façons, aujourd'hui en physique, nul ne dispose demoyen de se passer de l'infini ; cette solution n'est donc pas envisa-geable, il faut être moins violent.

! Renoncer à la théorie des ensembles ou aux mathématiques nonconstructives. Cela réglerait la question des paradoxes de la prédictionque nous venons d'évoquer, mais là encore ce n'est pas une solutionsérieusement envisageable, car, d’une part , il y plusieurs types demathématiques – il faudrait donc s'accorder pour en favoriser une – etsurtout elles introduisent des complications un peu partout, ce que per-sonne n'est prêt aujourd'hui à accepter. À nouveau, une solution rece-vable par la communauté scientifique exige moins de brutalité.

! Renoncer seulement à l'axiome du choix. En allant voirde plus près les mathématiques qui s'appuient sur des axiomesconcurrents et en les considérant comme seules « vraiesmathématiques », nous pourrions éviter la folie des pré-dictions du joueur temporel. Bien que beaucoup plus modé-rée, cette solution reste lourde et peu de mathématiciens– et encore moins de physiciens – accepteraient del'adopter. Une réponse au paradoxe s'appuyant plutôt surce qui est implicitement supposé du joueur temporel (ou de l'as-

semblée des joueurs) serait peut-être en mesure d'éviter les remises en causefondamentales qui viennent d'être énumérées.

! Arguer que nous attribuons des capacités déraisonnables au joueurtemporel. Les paradoxes s'appuient sur deux hypothèses assez difficilesà soutenir. (a) D'abord, il y a l'hypothèse que le joueur temporel a connais-sance de tout le passé (ou, dans le cas continu, au moins d'un intervallecomplet du passé), ce qui exige de lui une capacité d'observation sur-naturelle et même s'il en disposait représenterait une quantité d'infor-mations infinie à mémoriser, incompatible avec les capacités cognitiveslimitées (finies) qui sont les nôtres. (b) Avant que l'histoire ne com-mence, le joueur temporel doit fixer une distribution dans chaquepaquet – ou faire quelque chose du même degré de difficulté dans le casdes démonstrations pour le temps continu – or il y a une infinité nondénombrable de tels paquets, ce qui présuppose donc non seulement unemémoire infinie du joueur, mais une mémoire non limitée à l'infini dénom-brable, chose qu'on a encore plus de mal à imaginer sérieusement.

Trois autres pistes au moins sont encore possibles. Nous les livronssans entrer dans les détails.

! Arguer que les ensembles d'erreurs dans nos paradoxes sont tels,que ces erreurs rendent sans intérêt les prédictions du joueur temporel.

! Arguer que les états possibles du monde que nous exigeons demodéliser comme élément d'un ensemble fixé ne sont pas réductibles ainsi.

! Évoquer la relativité générale ou la mécanique quantique pourcontester la façon dont l'histoire du joueur temporel considère le tempset le problème de la prédiction.

Ces extraordinaires nouveaux paradoxes montrent que la théorie habi-tuelle des ensembles est un outil général, commode, mais parfois dérai-

sonnable pour représenter le monde et notre situation dans le monde.Il faut se méfier des représentations mathématiques qui uti-

lisent sans retenue l'infini non constructif, dont l'axiomedu choix n'est qu'un aspect . Bien évidemment , cesparadoxes sont contournables et, au fond, ils n'ont peut-être que peu à voir avec l’induction pratiquée dans lessciences de la nature qui se fonde sur l'hypothèse que

l'univers est régi par des lois qu'il faut identifier, et qui,si nous réussissons, conduisent à voir un peu en avant

dans le futur... sans qu'il y ait miracle !

5. Comment retomber sur ses pieds ?

pls_384_p086092_delahaye.xp2 7/09/09 17:56 Page 91

92] Logique et calcul © Pour la Science - n° 384 - Octobre 2009

R e g a r d s

ce qui semble une folie : il prévoit (en ne setrompant presque jamais) le résultat de lapièce avant qu’elle ne soit tombée, cela parcequ’il exploite les coups précédents, qui pour-tant, en cas de tirages indépendants, n’in-fluent en rien sur le résultat du tirage qu’ilanticipe. Folle situation...

Temps continuCh. Hardin e t A. Taylor ont démontré en2008 un résultat plus troublant encore quiconcerne un temps continu, plus conformeà la réalité de notre univers.

On imagine comme précédemment quele monde est décrit par une fonction f(t),où maintenant t est un nombre réel quel-conque désignant le temps, et f(t) un élé-ment d’un ensemble f ixé EPM, les é tatspossibles du monde. À l’instant t0, le joueurtemporel dispose de la connaissance de f(t)pour tous les t < t0, et il propose une valeurf(t0) qui est sa prédiction pour l’état dumonde en t0. Connaissant tout le passé jus-qu’à l’instant t0, il tente de deviner l’état dumonde réel à l’instant t0.

L’utilisation de l’axiome du choix conduitmaintenant à la conclusion suivante : il existeune méthode de prédiction qui assure aujoueur temporel de toujours deviner f(t), saufsi t appartient à un ensemble E (l’ensembledes erreurs) qui est (a) dénombrable, (b) demesure nulle, et (c) nulle part dense.

Précisons le sens de ces trois qualifica-tifs qui, chacun à leur façon, expriment quel’ensemble des instants où le joueur tempo-rel se trompe est infinitésimal comparé à l’en-semble des instants où il devine correctementl’état du monde.

(a) Un ensemble est dénombrable si onpeut le mettre en correspondance un à un (ondit aussi bijective) avec l’ensemble desentiers N. Comme l’ensemble des nombresréels n’est pas dénombrable (il constitue uninfini plus gros), cela signifie que l’ensembledes instants où le joueur se trompe est infi-niment petit comparé à l’ensemble des ins-tants t où le joueur temporel produit uneprédiction exacte.

(b) Un ensemble E est de mesure nullesi pour tout E strictement positif (aussipetit que l’on veut) il est possible de trou-

ver des intervalles (en quantité finie ouin f in ie dénombrable ) dont la réun ionrecouvre E, et dont la somme des longueursest inférieure à !. À nouveau, un ensemblede mesure nulle est un ensemble infini-ment petit comparé à ! tout entier : il n’apas d’épaisseur.

(c) Un ensemble E est nulle part dense siles points qui sont des limites de pointsde E, sont tous séparés (entre deux tels points,il y a toujours un point qui n’est pas dans E).Certains ensembles comme l’ensemble desnombres rationnels sont dénombrables et demesure nulle, mais ne sont pas nulle partdenses, cette troisième propriété renforceles deux premières et confirme que l’ensembledes instants où le joueur se trompe est vrai-ment infime.

Voir le futur!En affinant leurs méthodes, Ch. Hardin etA. Taylor ont encore aggravé leur résultat :

– d’une part, ils ne supposent plus quele joueur temporel connaît tout le passé, maisseulement le passé récent ; précisément, ilssupposent que le joueur temporel n’a connais-sance de la fonction f que sur un intervalle delongueur finie situé avant t0 ;

– d’autre part, ils exigent que le joueurtemporel prédise non seulement ce qui sepasse en t0, mais tout ce qui se produit surun petit intervalle à partir de t0 ; en clair, lejoueur temporel doit deviner le présent et unpeu du futur.

Le résultat persiste : moyennant l’utili-sation de l’axiome du choix, le joueur tempo-rel dispose d’une méthode de prédiction dontl’ensemble d’erreur est comme précédem-ment : (a) dénombrable ; (b) de mesure nulle ;(c) nulle part dense.

Ce résultat final n’est-il pas dément ?L’axiome du choix permet, sauf de manièrenégligeable, de prédire une tranche du futur,en n’utilisant qu’une tranche finie du passéet cela même si l’univers n’est qu’une suitetotalement désordonnée d’états se succé-dant sans la moindre règle.

Il est évident que connaître le passé estinutile dans un univers aléatoire sans aucuneloi ! Pourtant ici c’est utile, et cela permet deconnaître presque parfaitement le futur ! !

" BIBLIOGRAPHIEChristopher Hardin et Alan Taylor,Limit-like predictability fordiscontinuous functions,Proceedings of the AmericanMathematical Society,137-9, 3123–3128, 2009.

Christopher Hardin et Alan Taylor,An introduction to infinite hatsproblems, The MathematicalIntelligencer, 30-4, 2-6, 2008.

Christopher Hardin et Alan Taylor,A peculiar connection betweenthe axiom of choice andpredicting the Future, AmericanMathematical Monthly 115, 91-96,février 2008.

Alexander Paseau, JustifyingInduction Mathematically :Strategies and Functions, Logique& Analyse 203, 263-269, 2008.

Alexander George, A Proof ofInduction ? Philosophers’ Imprint,7, 1–5, mars 2007.

Horst Herrlich, Axiom of Choice,Springer-Verlag, Berlin, 2006.

Jean-Paul DELAHAYEest professeur à l’Universitéde Lille et chercheurau Laboratoire d’informatiquefondamentale de Lille (LIFL).

L ’ A U T E U R

pls_384_p086092_delahaye.xp2 7/09/09 17:56 Page 92