L'hôtel de Hilbert et le métro transfini.

(d'après un problème posé en 1991 sur sci.math )

Beaucoup de gens (et même des non-mathématiciens) ont entendu parler de l'hôtel de Hilbert, qui possède un nombre infini de chambres (numérotées 0,1,2,...). Un de ses nombreux avantages est de pouvoir accueillir de nouveaux clients, même quand il est plein : il suffit, pour libérer n chambres, de demander (par l'interphone instantané reliant la réception à toutes les chambres) à tous les clients de bien vouloir déménager de leur chambre (celle de numéro p) à la chambre de numéro n+p, ce qui ne provoque même pas d'embouteillage dans les couloirs... En fait, on peut aussi y recevoir une infinité dénombrable de nouveaux clients c₀ , c₁ , ... : on demande au client de la chambre de numéro p d'aller en chambre de numéro 2p, et on met le nouvel arrivant c_n dans la chambre 2n+1.

Le patron de l'hôtel avait jadis voulu s'agrandir, en créant la chaine (franchisée) de Hilbert formée d'une infinité d'hôtels H₀ , H₁ , ..., mais on lui a fait remarquer que c'était inutile: même si tous les hôtels de la chaîne sont pleins, on peut recaser tous leurs occupants dans l'hôtel H originel (et avoir encore une infinité de chambres vides) en envoyant l'occupant de la chambre n de l'hôtel H_p dans la chambre 2ⁿ3^p de H.

En revanche, peu de gens ont entendu parler du métro transfini M. Il relie l'aéroport à l'hôtel de Hilbert (mais continue bien au delà), peut transporter une infinité dénombrable de passagers, et s'arrête à toutes les stations d'une ligne qui en comporte ω₁, le plus petit ordinal non dénombrable (plus précisément, la station 0 est à l'aéroport, la station "Hilbert's Hotel" porte le numéro ω, et le terminus (la station Ω) porte le numéro ω₁; les autres stations sont simplement appelées 1, 2, ..., ω, ω+1, ...).

Pour se familiariser avec M, regardons son fonctionnement un jour très calme, sur les premières stations de son trajet (jusqu'à l'hôtel). À chaque station, un passager descend, puis dix passagers montent. Combien y a-t-il de passagers dans le train quand il arrive à l'hôtel?

Aussi bizarre que cela puisse paraître (puisqu'en arrivant à la station n, le métro contient 9n+1 passagers), la réponse peut être n'importe quel entier fini (y compris 0), ou une infinité: tout dépend du choix du passager descendant à la station n. En effet, en arrivant à la station n, les passagers numérotés de 1 à 10n sont montés, et on peut avoir fait descendre les passagers de 1 à n-1, par exemple; dans ce cas, tous les passagers finiront par descendre avant ω (puisque le passager p, monté à la station p/10 (ou plus précisément celle de numéro "partie entière de (p-1)/10)"), descend à la station p), ce qui prouve que le train est vide en arrivant. Le lecteur se convaincra qu'il est tout aussi facile de garder dans le train autant de passagers qu'on veut, et de faire descendre les autres (par exemple en faisant descendre à la station p le passager numéro 2p, tous les passagers de numéro impair arrivent à l'hôtel).

Étudions à présent ce qui se passe un jour de grande affluence, où à chaque station un passager descend et une infinité dénombrable de nouveaux passagers montent. Là encore, et contrairement à l'intuition, il est parfaitement possible que le métro arrive vide à l'hôtel, en appliquant la même stratégie que pour vider la chaîne de Hilbert (plus précisément, le n^ème passager monté à la station p descend à la station 2ⁿ3^p s'il n'est pas descendu auparavant, et sinon, ou si la station n'est pas de cette forme, on fait descendre un passager arbitraire).

Mais, bien sûr, la ligne continue bien après la station ω. Avec le même comportement (à chaque station un passager descend (s'il en reste) et une infinité dénombrable de nouveaux passagers montent), que se passe-t-il quand on arrive au terminus (et le métro ne risque-t-il pas d'être à cours de place)?

Non seulement le métro peut encore arriver vide, mais en fait, on a l'incroyable résultat suivant : quel que soit l'ordre des descentes, le métro arrive toujours vide! La démonstration en est assez élémentaire, mais très élégante: on va commencer par montrer qu'il n'est pas possible que le métro ne soit jamais vide jusqu'à son arrivée. En effet, si c'était le cas, à toute station de la ligne de numéro x > 0 descendrait un unique passager, monté à la station f(x) < x. La suite d'ordinaux x, f(x), f(f(x)), ... étant décroissante, elle possède un plus petit élément, donc il existe k tel que f^k(x) = 0. Or l'ensemble S₁(a) des x tels que f(x)=a est au plus dénombrable (puisqu'il s'agit des stations où sont éventuellement descendus les passagers montés à la station a), et il en est donc de même de l'ensemble S_k(a) des x tels que f^k(x)=a pour a et k fixés (puisqu'un produit fini d'ensembles dénombrables est dénombrable). Mais alors l'ensemble de tous les x est la réunion des S_k(0) pour k entier, donc dénombrable, ce qui est absurde puisque par définition ω₁ n'est pas dénombrable.

Recommençant le raisonnement à partir d'une station x quelconque, on voit que pour tout x, il existe une station y > x où le métro est vide (en effet, sinon, les y > x seraient contenus dans la réunion de S_k(a) pour a < x+1 et k entier, ce qui est tout aussi absurde). Ainsi, ω₁ est limite d'une suite (transfinie) d'ordinaux où le métro est vide. Or toute limite α d'une telle suite est une station où le métro arrive vide. En effet, si un passager est monté à la station x < α, il est nécessairement descendu avant y > x appartenant à la suite, puisqu'en y le métro arrive vide.

En résumé, tant que des passagers s'obstineront à descendre avant le terminus, on n'est pas prêt d'avoir besoin de construire un hôtel en Ω (et s'il en monte ne serait-ce qu'un de temps en temps, il faudra en revanche prévoir un métro plus grand). Cela dit, il convient quand même de faire remarquer un léger manque de réalisme physique dans toute cette histoire : tout ordinal dénombrable peut être atteint en un temps fini (parce que tout ordinal dénombrable est isomorphe (pour l'ordre) à un sous-ensemble des rationnels de [0,1]), mais en revanche ω₁ ne peut se plonger dans R, ce qui revient à dire que si le métro s'arrête un temps non nul à chaque station, il peut atteindre toute station avant le terminus, mais jamais celui-ci (les amateurs de topologie auront reconnu que le trajet du métro est la (demi) Longue Ligne, un ensemble localement isomorphe à R, mais beaucoup plus long... ).

Pour conclure, il faut remarquer que le résultat précédent ne peut guère être amélioré : si on range les passagers montés à l'aéroport dans le bon ordre (dénombrable) α et qu'on fait descendre le passager numéro x à la station x, le métro ne sera pas vide avant la station α (mais il est possible ensuite de le trouver vide en arrivant à la station α+ω); d'autre part, le problème vient entièrement des ordinaux limites: si la règle est qu'on fait descendre un passager seulement aux stations ayant une station immédiatement précédente, il est facile de remplir indéfiniment le métro (en ne faisant descendre qu'un des passagers montés juste avant).