ヒルベルトの無限ホテルのパラドックス

ヒルベルトの無限ホテルのパラドックスとは、無限集合の非直観的な性質を説明する思考実験である。無限個の客室があるホテルは「満室」でも新たな客を泊めることができ、その手順を無限に繰り返せることを示す。論理的・数学的に正しいが、直観に反するという意味でのパラドックスである。ヒルベルトのグランドホテルのパラドックス、ヒルベルトホテルとも。1924年にダフィット・ヒルベルトが論文「Über das Unendliche」で導入し、1947年のジョージ・ガモフの著書「1、2、3…無限大」によって広まったKraghGamow。

簡単のため、以下の記述では無限とは可算無限を意味するものとする。しかし選択公理を仮定すれば、任意の無限集合は可算無限集合を部分集合にもつため、非可算無限の場合でも少し議論を修正するだけでよい。

1. パラドックスの内容
------------

無限個の客室があり、「満室」である仮想的なホテルを考える。客室数が有限の場合、「満室であること」と「新たに来た客を泊められないこと」は同値だが、無限ホテルではそうはならない。

1.1. 有限人の新たな客
-------------

1人の客が来てホテルに宿泊を希望したとする。そこで1号室の客を2号室に、2号室の客を3号室に、//n//}}号室の客を}}号室に移動させる。すると1号室は空室になり、1人の客を泊めることができる。この手順を繰り返すことで、任意の有限人の新たな客の部屋を作れる。

1.2. 無限人の新たな客
-------------

また、//無限人//の新たな客を泊めることも可能である。1号室の客を2号室に、2号室の客を4号室に、//n//}}号室の客を2//n//}}号室に移動させれば、すべての奇数号室が新たな客に解放される。

1.3. それぞれ無限人の客を乗せた無限台のバス
------------------------

いくつかの方法で、それぞれ無限人の乗客を乗せた無限台のバスの団体客を泊めることが可能である。ほとんどの方法はバスの座席が番号付けされていることを仮定する。一般にこの問題を解くには任意の対関数が使える。それぞれの方法で、乗客の座席番号を//n//}}、乗っているバスの号車番号を//c//}}とすると、//n//}}と//c//}}が対関数の2つの引数になる。

1.3.1. 素数冪を用いる方法
----------------

//i//}}号室の客を2sup号室に移動させて奇数号室を空け、1号車の団体客を3sup号室に、2号車の団体客を5sup号室に、一般に//c//}}号車の団体客を、//c//}}番目の奇素数を//p//}}として、//p//sup号室に泊める。この方法ではいくつかの客室が空室になる。具体的には15や847などのすべての素数冪でない奇数号室は誰も泊まっていない状態になる。

1.3.2. 素因数分解を用いる方法
------------------

座席//s//}}、号車//c//}}の乗客を2sup号室に泊める。すべての正の整数は一意的に素因数分解できるので、すべての客が部屋に入り、同じ部屋に2人入らないことがわかる。たとえば2592  号室の客は、4号車の5番目の席に座っていた乗客である。素数冪を用いる方法と同様に、この方法ではいくつかの客室が空室になる。

この方法は無限の夜に、無限の入り口に…などの問題に簡単に拡張できる 。

1.3.3. Interleaving method
--------------------------

それぞれの乗客について、十進法などの任意の位取り記数法で表した//n//}}と//c//}}の桁数を比較し、桁数が異なる場合、同じ桁数になるまで桁数の少ない方の先頭のゼロを付け加える。そして[号車番号の1桁目]-[座席番号の1桁目]-[号車番号の2桁目]-[座席番号の2桁目]-…と各桁の数字をinterleaveして部屋番号を生成する。元のホテルの1729号室の客は、01070209号室に移動する。789号車の1234番目の座席の乗客は01728394号室に入る。

素数冪を用いる方法とは異なり、この方法は客室を完全に埋め、interleaving processを逆にすることで、元の号車と座席を復元することができる。まず部屋番号が奇数桁の場合、先頭に0を追加する。すると号車番号は奇数桁目の数字からなり、座席番号は偶数桁目の数字からなる。もちろん元の符号化の方法は任意であり、一貫して適用する限り、2つの数字の役割を逆にすることができる。

1.3.4. 三角数を用いる方法
----------------

元のホテルの客をsup号室に泊める。これですべての客室が重複なく埋まる。

この対関数は、ホテルを1部屋分の奥行きがある無限に高いピラミッドとして構造化することでイメージできる。ピラミッドの最上段に1号室があり、次の段に2号室と3号室があり、以下同様に続く。右端の客室の集合からなる列が三角数号室に対応する。それらの客室が埋まると、空になった部屋は元の形と厳密に等しいピラミッドの形になる。よって、この手順を各無限集合ごとに繰り返すことができる。これを1台ずつ行うには無限のステップ数が必要になるが、事前の計算式を用いることで、手順の中で自分のバスの順番が来た時点で乗客は自分の部屋が何番に「なる」か決定でき、ただちにそこに行くことができるようになる。

1.3.5. 任意の列挙方法
--------------

とする。は可算なので//S//}}は可算であり、その要素//s//subを列挙することができる。ここで1=//s//subとし、//a//}}号車の//b//}}番目の乗客を//n//}}号室に割り当てる。これで全員を客室に割り当てる関数ができ、なおかつ、この割り当てはどの客室ももらさない。

1.4. さらなる無限の階層
--------------

ホテルが海に隣接していて、無限隻のカーフェリーが来て、それぞれ無限台のバスが積み込まれており、それぞれ無限人の乗客が乗っているとする。これは3「段階」の無限を含む状況であり、これまでの方法の拡張で解くことができる。

素因数分解を用いる方法は、無限の階層が増えるごとに新たな素数を追加することで適用できる。

素数冪を用いる方法は、さらなる素数の冪乗をとることで適用でき、結果として小さな入力でも非常に大きな部屋番号になる。たとえば、2番目の座席-3番目のバス-2番目のフェリーに該当する乗客の部屋番号は、1=5supとなり、17,763,568,394,002,504,646,778,106,689,453,125号室に行くことになる。

interleaving methodでは、2つではなく3つのinterleaveされた「strands」を用いる。番地2-3-2の乗客は232号室に行き、番地4935-198-82217の乗客は008,402,912,391,587号室に行くことになる。

任意の階層数の無限人の客が来る可能性を想定して、ホテルは何人の客が後に来ても移動する必要がないような部屋を割り当てたいと思うかもしれない。一つの解決策は、各来客者の番地を二進数に変換し、1を各階層の開始地点のセパレータとして使用し、0を並べて階層内の番号を表現することである。たとえば番地2-5-1-3-1の客は、10010000010100010号室に行くことになる。

この手順の追加ステップとして、番号の各節から0を1つ削除することができる。この例では客の部屋は101000011001号室となる。これによりすべての部屋が想定される客によって埋まることが保証される。もし無限人の客の集合が来ない場合は、2の冪の番号の部屋のみが使用される。

1.4.1. 無限に入れ子になった階層
-------------------

無限人の客が有限回入れ子になっている場合は部屋を作れるが、各階層の客が有限人だったとしても無限回入れ子になっている場合は常にそうとは限らない。

2. 考察
-----

ヒルベルトのパラドックスは擬似パラドックスである。直観に反するが真であると証明される結論を導く。文 「すべての部屋に客がいる」と「これ以上客を泊められない」は、部屋が無限にある場合は同値ではない。

最初はこの状態は非直観的に思えるかもしれないが、「無限のものの集まり」と「有限のものの集まり」の性質はまったく異なる。ヒルベルトの無限ホテルのパラドックスは、カントールの超限数の理論を用いて理解することができる。複数の部屋がある現実のホテルでは、奇数番号の部屋数は部屋の総数より明らかに少ないが、ヒルベルトいうところの無限ホテルでは、奇数番号の部屋数は部屋の総「数」より少なくない。数学用語でいうと、奇数番号の部屋全体を含む部分集合の濃度は、すべての部屋の集合の濃度と等しい。実際、無限集合は等しい濃度の真部分集合をもつ集合として特徴づけられる。可算集合の場合、その濃度はであるRucker。

言い換えれば、任意の可算無限集合//S//}}について、//S//}}が自然数全体を真部分集合として含んでいたとしても、//S//}}を自然数全体の集合に写像する全単射が存在するということである。たとえば、有理数全体の集合は、真部分集合として自然数全体を含むが、有理数全体は可算なので自然数全体の集合より大きくない。

3. フィクションでの言及
-------------

BBC Learning Zoneでは、1996年の単発の教育ドキュメンタリードラマ「[1]」を繰り返し放送した。若い女性客フィオナ・ナイトの目を通して見たホテルを舞台にしている。この番組は視聴者に無限の概念について教育することを目的としたものだった。
数学者・SF作家ルーディ・ラッカーの小説『ホワイト・ライト 』には、ヒルベルトのパラドックスを元にしたホテルが登場し、物語の主人公がゲオルク・カントールに出会う場面がある。
スティーヴン・バクスターのSF小説『トランセンデント』には、ホテルではなく宇宙船の戦士を用いるように修正されたパラドックスに基づく説明で、無限の性質についての簡単な議論がある。
ジェフリー・A・ランディスのネビュラ賞受賞短編小説「ディラック海のさざなみ」では、無限に満たされたディラックの海がなお粒子を受け入れることができる理由の説明としてヒルベルトホテルを使用している。
ペーター・ホゥの小説「スミラの雪の感覚」では、表題のヒロインはホテルの支配人と客が、遅れてきた者が自分の部屋とプライバシーを確保できるようにわざわざ手間をかけるのは立派なことだと思案している。
イーヴァル・エクランドの児童向け小説『The Cat in Numberland』では、「ミスター・ヒルベルト」と彼の妻がすべての整数のために無限ホテルを経営している。物語は有理数に対する三角数を用いる方法を使って進んでいく。
ウィル・ワイルズの小説『時間のないホテル』では無限に大きいモーテルを題材にしてるが、悪役の名前は「ヒルベルト」である。
レジナルド・ヒルの小説『異人館』では登場人物・サムがヒルベルトホテルのパラドックスに言及している。
ナウム・ヤコブレヴィチ・ヴィレンキンの短編小説『不思議なホテル』では、ヒルベルトの無限ホテルが無限人の新たな主人が来たときに再編される方法を示している。
ジョン・ロデリック とケン・ジェニングスはオムニバス・ポッドキャストの中の配信「[2]」でこのホテルについて議論した。
アラン・ムーアとケヴィン・オニールの漫画『リーグ・オブ・エクストラオーディナリー・ジェントルメン』シリーズの第四篇「テンペスト」には、インフィニティと呼ばれる悪役が登場する。物語では悪役がヒルベルトのパラドックスを元にしたホテルに行くことが示唆されている。ゲオルク・カントールについても言及されている。
倉多江美のマンガ『一万十秒物語』には無限ホテルをテーマにした短篇がある。

4. 脚注
-----

5. 参考文献
-------

6. 関連項目
-------

パラドックス#パラドックスの一覧
バナッハ＝タルスキーのパラドックス
鳩の巣原理

7. 外部リンク
--------

[3] - 集合論研究者・渕野昌による文書。ヒルベルトホテルについて触れられている。
[4] - ジェフ・デコフスキーによるTED-Edレッスン。