David Madore's WebLog: Le Docteur No fait deviner des nombres

Le Docteur No, célèbre[#] pour capturer des mathématiciens et les soumettre à diverses énigmes (précédemment sur ce blog : ici, là, là, là, là et peut-être là) est de retour ! Cette fois-ci il n'a capturé que deux mathématiciens, que nous allons appeler Alice et Bob, mais cela ne l'empêche pas de s'amuser à leur proposer une énigme particulièrement cruelle.

[#] Honnêtement, je ne me rappelle même plus si c'est moi qui ai commencé à appeler Docteur No (comme dans le film de James Bond) le grand méchant de ces énigmes ou si je tiens ça d'ailleurs.

Comme ça fait longtemps que nous n'avons pas eu affaire au Docteur No, je commence par une version jouet de l'énigme, histoire de s'échauffer :

Énigme facile : Le Docteur No a capturé deux mathématiciens, Alice et Bob. Après avoir permis à ceux-ci de se concerter sur leur stratégie, il va les soumettre à son épreuve dont il leur communique les termes. Il communiquera deux entiers naturels de son choix à Alice. Alice choisira un et un seul de ces nombres et ce nombre sera transmis à Bob (qui est l'allié d'Alice). Le but de Bob est de deviner le nombre qu'il n'aura pas reçu : pour ça, il aura droit de proposer un nombre fini quelconque d'essais ; autrement dit, il doit proposer au Docteur No un ensemble fini d'entiers naturels (on peut supposer, cela ne change rien, que le nombre transmis par Alice est aussi mis dedans). Si les nombres initialement choisis par le Docteur No sont dans cet ensemble proposé par Bob, alors les mathématiciens seront libérés ; dans le cas contraire, le Docteur No les tuera avec des tortures particulièrement raffinées.

Comment Alice et Bob font-ils pour être certains d'être libérés ?

La réponse est facile, mais je recommande de prendre le temps de résoudre ce problème avant de passer à la suite (cliquez ici pour la faire apparaître), ne serait-ce que pour vérifier qu'on a bien compris la nature du problème. La réponse est la suivante : Alice communique à Bob le plus grand des nombres qu'elle a reçus, et Bob, recevant ce nombre x, propose l'ensemble (fini) de tous les entiers naturels entre 0 et x ; comme x est le plus grand, l'autre nombre est forcément dans cet ensemble.

Il va de soi que cette solution fonctionne encore si, au lieu que les nombres proposés par le Docteur No soient des entiers naturels, ce sont des entiers relatifs ou des rationnels, car il suffit de coder ceux-ci par des entiers naturels (mais attention, dans la construction ci-dessus, on n'utilisera plus le plus grand nombre, mais le nombre ayant le plus grand code). Mais qu'en est-il pour des nombres réels ?

Contre-énigme : Le Docteur No a capturé deux mathématiciens, Alice et Bob. Il envisage de les soumettre à l'épreuve suivante. Après leur avoir permis de se concerter sur leur stratégie, il communiquerait deux réels de son choix à Alice. Alice devrait choisir un et un seul de ces nombres et ce nombre serait transmis à Bob (qui est l'allié d'Alice). Le but de Bob serait de deviner le nombre qu'il n'aura pas reçu : pour ça, il aurait droit de proposer un nombre fini quelconque d'essais ; autrement dit, il devrait proposer au Docteur No un ensemble fini de réels (on peut supposer, cela ne change rien, que le nombre transmis par Alice est aussi mis dedans). Si les nombres initialement choisis par le Docteur No sont dans cet ensemble proposé par Bob, alors les mathématiciens seraient libérés ; dans le cas contraire, le Docteur No les tuerait avec des tortures particulièrement raffinées.

Pourquoi le Docteur No, dont le code de l'honneur exige qu'il y ait toujours un moyen de résoudre les épreuves qu'il propose, décide-t-il de ne pas proposer cette épreuve ?

C'est que l'épreuve en question serait impossible : cliquez ici pour voir la preuve. En effet, supposons par l'absurde qu'Alice et Bob aient une stratégie, et considérons la réunion Z de toutes les réponses que ferait Bob si Alice lui transmet un entier naturel (y compris les entiers naturels eux-mêmes) : ce Z est dénombrable (comme réunion dénombrable d'ensembles finis), donc il existe un réel qui n'est pas dedans ; soit donc x un réel qui n'est pas dans Z. Maintenant, si y est un entier naturel quelconque, alors si le Docteur No propose {x,y} à Alice, elle doit forcément transmettre x à Bob, car (sinon) en réponse à y celui-ci répondrait avec une partie finie de Z, qui ne contient donc pas x, et ce serait un échec. Donc la réponse de Bob si Alice lui transmet x doit contenir y, et ce, quel que soit l'entier naturel y. Or aucun ensemble fini ne peut contenir tous les entiers naturels, ce qui est une contradiction.

Le Docteur No doit donc rendre son énigme un peu plus facile. Voici comment il envisage de le faire :

Énigme sur les réels : Le Docteur No a capturé deux mathématiciens, Alice et Bob. Il envisage de les soumettre à l'épreuve suivante. Après leur avoir permis de se concerter sur leur stratégie, il communiquerait trois réels de son choix à Alice. Alice devrait choisir deux de ces nombres et ces nombres seraient transmis (dans un ordre non spécifié) à Bob (qui est l'allié d'Alice). Le but de Bob serait de deviner le nombre qu'il n'aura pas reçu : pour ça, il aurait droit de proposer un nombre fini quelconque d'essais ; autrement dit, il devrait proposer au Docteur No un ensemble fini de réels (on peut supposer, cela ne change rien, que les nombres transmis par Alice sont aussi mis dedans). Si les nombres initialement choisis par le Docteur No sont dans cet ensemble proposé par Bob, alors les mathématiciens seraient libérés ; dans le cas contraire, le Docteur No les tuerait avec des tortures particulièrement raffinées.

Le Docteur No est perplexe quant à la difficulté de cette épreuve et demande conseil à Georg Cantor (qui est emprisonné dans son donjon). Que lui répond Cantor ?

(Les mathématiciens qui trouvent que mon énoncé n'est pas super clair peuvent lire la version plus générale ci-dessous et prendre X=ℝ et n=3 et m=2.)

La réponse surprenante est que la résolubilité de cette dernière énigme est indécidable dans la théorie des ensembles usuelle (ZFC, i.e., les axiomes usuels des mathématiques). Plus exactement, cette dernière énigme est résoluble si, et seulement si, l'hypothèse du continu vaut : l'hypothèse du continu est l'affirmation que le cardinal de ℝ vaut ℵ₁, ou, pour le dire autrement, que toute partie de ℝ est soit au plus dénombrable soit en bijection avec ℝ, ou encore, qu'il existe une relation d'ordre total ≼ sur ℝ telle que l'ensemble {t∈ℝ : t≼x} soit au plus dénombrable pour tout x∈ℝ.

La preuve que, si l'hypothèse du continu est vraie alors l'énigme sur les réels a une solution, est assez semblable à la réponse de l'énigme facile, si on utilise la dernière formulation que je viens de donner de l'hypothèse du continu : cliquez ici pour la voir. Alice et Bob choisissent une relation d'ordre ‘≼’ comme je viens de le dire sur ℝ, et, de plus, pour chaque x ils choisissent une bijection entre {t∈ℝ : t≼x} et une partie de ℕ, ce qui permettra d'appliquer la solution de l'énigme facile. Lorsque Docteur No donne trois nombres réels à Alice, elle commence donc par retenir le plus grand pour l'ordre ≼, appelons-le x, puis elle compare les deux autres selon la bijection choisie entre {t∈ℝ : t≼x} et une partie de ℕ, et elle retient celui qui a la plus grande image par cette bijection, appelons-le y. Alice transmet x et y à Bob. Bob, à son tour, trouve le plus grand des deux nombres selon ‘≼’, ce qui lui permet d'identifier x, puis il utilise la bijection, trouve l'image de y par celle-ci, et renvoie (x, y et) tous les éléments ayant une image plus petite que celle de y.

La réciproque est tout à fait analogue à la preuve de l'impossibilité de la contre-énigme : cliquez ici pour la voir. En effet, supposons par l'absurde qu'Alice et Bob aient une stratégie, mais que l'hypothèse du continu soit fausse. Soit Y une partie indénombrable de ℝ qui ait un cardinal strictement plus petit que ℝ. Considérons la réunion Z de toutes les réponses que ferait Bob si Alice lui transmet deux éléments de Y (y compris les éléments de Y eux-mêmes) : ce Z est en bijection avec Y (comme réunion de card(Y)² ensembles finis), donc il existe un réel qui n'est pas dedans ; soit donc x un réel qui n'est pas dans Z. Maintenant, si y,y′ sont deux éléments quelconques de Y, alors si le Docteur No propose {x,y,y′} à Alice, elle doit forcément transmettre x dans sa réponse à Bob, car en réponse à {y,y′} celui-ci répondrait avec une partie finie de Z, qui ne contient donc pas x, et ce serait un échec. Donc en considérant les choix faits par Alice et les réponses faites par Bob aux {x,y,y′} du Docteur No, on voit qu'Alice et Bob ont, en fait, une stratégie qui permet de répondre à l'énigme facile pour des éléments y,y′ de Y (à savoir : imaginer qu'on ajoute x, appliquer leur stratégie sur les réels, et renvoyer les éléments de Y de la réponse). Or on a vu que ceci n'est pas possible si Y est indénombrable.

Bon, évidemment, j'ai écrit mes énigmes de façon assez particulière pour ne pas surcharger cette entrée de notations dès le début, mais la situation générale est la suivante :

Énigme générale : Le Docteur No a capturé deux mathématiciens, Alice et Bob. Après avoir permis à ceux-ci de se concerter sur leur stratégie, il va les soumettre à son épreuve dont il leur communique les termes (y compris les données X,n,m dans ce qui suit). Il communiquera à Alice un ensemble fini S⊆X de cardinal n fixé connu à l'avance d'un ensemble X infini lui aussi fixé connu à l'avance. Alice choisira un sous-ensemble S′⊆S de cardinal m imposé connu à l'avance (où m<n) et cet ensemble S′ sera transmis à Bob (qui est l'allié d'Alice). Le but de Bob est de proposer un ensemble fini S″⊆X tel que S″⊇S. Si le S initialement choisi par le Docteur No est inclus dans cet ensemble S″ proposé par Bob, alors les mathématiciens seront libérés ; dans le cas contraire, le Docteur No les tuera avec des tortures particulièrement raffinées.

À quelle condition sur X,n,m cette épreuve est-elle faisable ?

Autrement dit : pour quels X,n,m (où m<n) existe-t-il des fonctions φ : [X]ⁿ → [X]^m (compression, ou stratégie d'Alice) et η : [X]^m → [X]^<ω (décompression, ou stratégie de Bob), où [X]ⁿ désigne l'ensemble des parties de X ayant n éléments et [X]^<ω celui de toutes les parties finies de X, telles que φ(S) ⊆ S et η(φ(S)) ⊇ S pour tout S ∈ [X]ⁿ ?

Et la réponse est : ceci est possible si et seulement si card(X) ≤ ℵ_m−1. En particulier, pour X=ℝ, le défi où Alice a le droit de transmettre m réels à Bob est résoluble si et seulement si 2^ℵ₀ ≤ ℵ_m−1 (et pour m=2 cette affirmation est exactement l'hypothèse du continu).

La preuve est analogue à ce que j'ai déjà écrit, je ne recommence pas (c'est une récurrence sur m, la généralisation sur n par rapport à n=m+1 n'apportant rien de particulièrement problématique ou intéressant dans l'histoire). Les détails peuvent être trouvés dans l'article Learnability can be undecidable de Shai Ben-David, Pavel Hrubeš &al, paru dans Nature Machine Intelligence (<soupir>) en 2019 (version ouverte ici). J'en ai entendu parler via cette question sur MathOverflow qui pose un problème très fortement lié (mais avec des probas en plus).

Je trouve cette énigme très amusante, d'abord parce que c'est extrêmement surprenant que le k tel que card(X) = ℵ_k (s'il existe) joue un rôle combinatoire comme entier naturel, et d'autre part parce que ça fournit un équivalent de l'hypothèse du continu qu'on peut raconter sans avoir besoin de parler de bijection ou de cardinalité. (Ou encore, on peut s'en servir comme explication de ce que signifie card(X) = ℵ_k : un ensemble a pour cardinal ℵ_k lorsque l'énigme est résoluble lorsque Alice communique k+1 éléments à Bob mais pas résoluble quand elle en communique k.)

Le problème admet plein de généralisations ou d'analogues potentiellement intéressantes. Par exemple le problème combinatoire fini suivant : Docteur No communique à Alice n éléments d'un ensemble X fini à N éléments, Alice en choisit m qui sont transmis à Bob, et Bob doit choisir r éléments de X de telle sorte qu'ils contiennent les n éléments de départ. Autrement dit, à quelle condition sur m≤n≤r et N peut-on trouver des fonctions φ : [X]ⁿ → [X]^m (compression, ou stratégie d'Alice) et η : [X]^m → [X]^r (décompression, ou stratégie de Bob), où X = {0,…,N−1}, telles que φ(S) ⊆ S et η(φ(S)) ⊇ S pour tout S ∈ [X]ⁿ ? Je n'y ai pas réfléchi, mais je suppose que les combinatoriciens savent des choses sur ce genre de problèmes (je crois d'ailleurs avoir rencontré le cas r=n quelque part, et me souvenir que la réponse est assez facile avec le lemme « des mariages » de Hall, qui est d'ailleurs vaguement évocateur des preuves données plus haut).