Hôtel de Hilbert

Il est facile de savoir si deux ensembles finis ont le même nombre d'éléments : il suffit de compter le nombre d'éléments de chaque ensemble et de comparer! Une autre façon de faire, c'est de mettre en correspondance les éléments de chaque ensemble. Si dans un club de vtt vous voulez savoir s'il y a autant de vélos que de membres, vous donnez à chaque membre un vélo. Si à la fin, chaque membre a un vélo et qu'il ne reste plus de vélos, c'est que le nombre de membres et le nombre de vélos sont identiques. On dit qu'on a construit une bijection entre deux ensembles.

Pour savoir si deux ensembles infinis ont le même nombre d'éléments, on ne peut plus compter, et il faut trouver un moyen de les mettre en correspondance. L'hôtel de Hilbert est une façon imagée d'apparier des ensembles infinis imaginée par le mathématicien allemand David Hilbert afin d'illustrer que certains ensembles infinis ont le même nombre d'éléments

L'hôtel de Hilbert possède une infinité de chambres numérotées par les entiers de $\mathbb N^*$: $1,2,3,\dots$. Ce soir, l'hôtel est plein : chaque chambre est occupée par un client. Mais un nouveau client se présente : comment Mr Hilbert peut-il le loger afin que chaque client ait une chambre et soit seul dans sa chambre? La solution est assez simple : il suffit que chaque client se déplace dans la chambre voisine de la sienne, de sorte que le client qui était dans la chambre 1 occupe ensuite la chambre 2, que celui qui était dans la chambre 2 occupe la chambre 3, etc... Mr. Hilbert peut alors inviter le nouveau client à s'installer dans la chambre 1.

Ce faisant, Hilbert démontre que $\mathbb N^*$ et $\mathbb N$ ont le même nombre d'éléments, si on convient que le nouveau client portait le numéro $0$ avant de s'installer dans la chambre.

Mais maintenant, un problème encore plus difficile se présente à Mr. Hilbert. Un bus de nouveaux clients se présente sur son parking. Bien sûr, ce bus comporte une infinité de clients. Chaque client possède un T-shirt numéroté $1,2,3\dots.$ Comment les installer dans l'hôtel? Après une petite réflexion, Mr. Hilbert trouve la solution : chaque client déjà dans l'hôtel s'installe dans la chambre dont le numéro est égal au double du numéro de la chambre actuellement occupée. Ainsi, le client qui était dans la chambre 1 occupe ensuite la chambre 2, que celui qui était dans la chambre 2 occupe la chambre 4, etc... Maintenant, toutes les chambres portant un numéro impair sont libres et Hilbert peut y installer les nouveaux clients : le client portant le T-shirt numéro 1 s'installe dans la chambre 1, celui portant le T-Shirt numéro 2 dans la chambre 3, et plus généralement celui portant le T-shirt numéro $k$ s'installe dans la chambre $2k-1.$

Cette version du problème montre que la réunion de deux ensembles infinis peut avoir le même nombre d'éléments qu'un seul ensemble infini. Elle illustre aussi qu'il y a le même nombre de nombres entiers naturels que de nombres impairs, puisqu'à chaque client on a pu associer une chambre ayant un numéro impair.

Un autre jour, Hilbert pensait se reposer : son hôtel était vide. Mais voilà que son parking se remplit. Évidemment, comme il s'agit d'un hôtel infini, son parking est aussi infini et c'est une infinité de bus qui se présente sur le parking. Ces bus sont numérotés $1,2,3,\dots.$ Chaque bus comporte une infinité de clients. Chaque client possède un T-shirt portant deux numéros : le premier est celui de leur bus et le second est celui de leur place dans le bus. Comment Mr. Hilbert va-t-il trouver de la place pour chacun?

Le problème est difficile, mais Mr. Hilbert est un malin :

Ainsi, les clients du bus numéroté $k$ commencent à s'installer dans l'hôtel à partir de l'étape $k$, et à chaque étape à partir de l'étape $k$, un nouveau client du bus sera logé. Ainsi, tous les clients auront une chambre.

Le tableau ci-dessus illustre comment les chambres sont attribuées. La première ligne désigne le numéro du bus, la première colonne la place du client dans le bus et à l'intersection de la $i$-ème colonne et de la $j$-ème ligne, on a le numéro de la chambre occupée par le $j$-ème client du $i$-ème bus.

Ce problème de l'hôtel de Hilbert illustre le fait que $\mathbb N^*\times\mathbb N^*$ ont le même nombre d'éléments, puisqu'on peut les mettre en correspondance.

L'hôtel de Hilbert est en fait un hôtel-restaurant. Son menu comporte une infinité de plats bien sûr, ces plats sont numérotés $1,2,3,...$. Chaque client compose un repas infini, en choisissant un premier plat parmi les plats proposés, puis un second plat (éventuellement le même que le premier), etc... L'hôtel est plein et chaque client a composé son repas. Mais voici qu'un nouveau client se présente. C'est un original et il exige de M. Hilbert que son repas soit différent de celui de tous les autres clients! Est-ce que M. Hilbert peut toujours le satisfaire?

Oui, c'est possible! Pour cela, M. Hilbert décide que :

À nouveau, ceci peut s'interpréter en termes de nombre d'éléments d'un ensemble infini. Un repas peut être décrit comme une suite $(u_n)_{n\geq 1}$, où pour chaque $n\geq 1,$ $u_n\in\mathbb N^*$. Notons $E$ l'ensemble (infini) des repas possibles. Alors $E$ ne peut pas être mis en correspondance avec $\mathbb N^*$, sinon il aurait existé une configuration pour laquelle tous les choix de repas possibles auraient été épuisés par les clients de l'hôtel, et il aurait été impossible de trouver un repas différent pour le nouvel arrivant. Ainsi, $E$ et $\mathbb N^*$ n'ont pas le même nombre d'éléments, et on peut même dire que $E$ a plus d'éléments de $\mathbb N^*.$

Ce raisonnement s'appelle le procédé diagonal de Cantor. C'est ainsi que l'on démontre que l'ensemble des nombres réels et l'ensemble des nombres entiers n'ont pas le même nombre d'éléments.