グランドホテルのヒルベルトのパラドックス

ヒルベルトのグランドホテルのパラドックス （口語：無限ホテルパラドックスまたはヒルベルトのホテル）は、無限集合の直感に反する性質を説明する思考実験です。無限の数の部屋がある満室のホテルは、さらに無限の数のゲストを収容することができ、このプロセスは無限に繰り返される可能性があることが実証されています。このアイデアは、1925年の講義「Über das Unendliche 」でデイヴィッド・ヒルベルトによって紹介され、（ヒルベルト2013、p.730）に再録され、ジョージ・ガモフの1947年の著書One Two Three... Infinityを通じて普及しました。^{[1] [2]}

ヒルベルトは、1、2、3 などと番号が付けられ、上限のない部屋がある架空のホテルを想像します。これは、可算無限数の部屋と呼ばれます。最初はすべての部屋が埋まっていますが、新しい訪問者がやって来て、それぞれが自分の部屋を期待します。通常の有限のホテルでは、すべての部屋が埋まってしまうと、新しいゲストを収容できなくなります。しかし、無限のホテルでは、既存のゲストと新しいゲスト (たとえ無限の数であっても) がそれぞれ自分の部屋を持つことができることが示されています。

ゲストが 1 人増えると、無限数のゲストが同時に部屋を移動する場合でも、ホテルはそのゲストと既存のゲストを収容できます。現在部屋 1 にいるゲストは部屋 2 に移動し、現在部屋 2 にいるゲストは部屋 3 に移動し、以下同様にして、すべてのゲストを現在の部屋nから部屋n +1に移動します。無限ホテルには最後の部屋がないため、すべてのゲストが移動する部屋があります。この後、部屋 1 は空になり、新しいゲストをその部屋に移動できます。この手順を繰り返すことで、有限数の新しいゲストに部屋を作ることができます。一般に、k人のゲストが部屋を探している場合、ホテルは同じ手順を適用して、すべてのゲストを部屋nから部屋n + kに移動できます。

可算無限の数の新しいゲストを収容することも可能です。部屋 1 に宿泊している人を部屋 2 に、部屋 2 に宿泊しているゲストを部屋 4 に、そして一般に、部屋nに宿泊しているゲストを部屋 2 n (2 倍のn ) に移動するだけで、奇数番号の部屋 (可算無限数) がすべて新しいゲストのために空くことになります。

いくつかの異なる方法により、可算無限の乗客を乗せた可算無限のバスを収容することが可能です。ほとんどの方法は、バスの座席がすでに番号付けされていることを前提としています（または可算選択公理を使用します）。一般に、任意のペアリング関数を使用してこの問題を解決できます。これらの各方法について、バスの乗客の座席番号を、バス番号を とし、番号とをペアリング関数の 2 つの引数に入力します。 ${\displaystyle n}$${\displaystyle c}$${\displaystyle n}$${\displaystyle c}$

客室 のゲストを部屋 に送り、最初の車両の乗客を 部屋 に、2 番目の車両の乗客を 部屋 に置きます。一般に、車両番号 には、が奇数の素数である部屋 を使用します。この解決法では、特定の部屋が空のままになります (ホテルにとって有用である場合もそうでない場合もあります)。具体的には、 15 や 847 など、素数の累乗でない数はすべて使用されなくなります。(したがって、厳密に言えば、これは到着数が作成された空室数以下であることを示しています。アルゴリズムを正確に適合するように修正するよりも、独立した手段によって、到着数が空室数以上であり、したがってそれらが等しい であることを示す方が簡単です。) (アルゴリズムは と を入れ替えても同様に機能しますが、どちらを選択した場合でも、全体にわたって均一に適用する必要があります。) ${\displaystyle i}$${\displaystyle 2^{i}}$${\displaystyle 3^{n}}$${\displaystyle 5^{n}}$${\displaystyle c}$${\displaystyle p_{c}^{n}}$${\displaystyle p_{c}}$${\displaystyle c}$${\displaystyle n}$${\displaystyle c}$

特定の座席と車両に座っている各人を部屋に入れることができます(ホテルにすでにいる人の場合はc =0、最初の車両の場合は 1 などと仮定)。すべての数字には一意の素因数分解があるため、すべての人に部屋が割り当てられますが、2 人が同じ部屋になることはありません。たとえば、部屋 2592 ( ) の人は、4 番目の車両の 5 番目の座席に座っていました。素数乗法と同様に、この解決方法では特定の部屋が空のままになります。 ${\displaystyle s}$${\displaystyle c}$${\displaystyle 2^{s}3^{c}}$${\displaystyle 2^{5}3^{4}}$

この方法は、無限の夜、無限の入り口などに簡単に拡張できます。（） ${\displaystyle 2^{s}3^{c}5^{n}7^{e}...}$

各乗客について、 と の長さを、小数点などの位置指定記数法で表記したものと比較します。(各ホテルの宿泊客は、車両番号 0 号車に乗っているとみなします。) どちらかの数字が短い場合は、両方の数字の桁数が同じになるまで、先頭にゼロを追加します。数字を交互に並べて部屋番号を作成します。部屋番号の数字は、[車両番号の最初の桁]-[座席番号の最初の桁]-[車両番号の 2 番目の桁]-[座席番号の 2 番目の桁]-などとなります。部屋番号 1729 のホテル (車両番号 0 号車) の宿泊客は、部屋 01070209 (つまり、部屋 1,070,209) に移動します。車両 789 の座席 1234 の乗客は、部屋 01728394 (つまり、部屋 1,728,394) に移動します。 ${\displaystyle n}$${\displaystyle c}$

素数の累乗による解決法とは異なり、この解決法はホテルを完全に埋め尽くし、インターリーブ プロセスを逆にすることでゲストの元の車両と座席を再構築できます。まず、部屋の数字が奇数の場合は先頭にゼロを追加します。次に、数字を 2 つの数字にインターリーブ解除します。車両番号は奇数桁で構成され、座席番号は偶数桁で構成されます。もちろん、元のエンコードは任意であり、一貫して適用される限り、2 つの数字の役割を逆にすることができます (座席が奇数、車両が偶数)。

すでにホテルに宿泊しているゲストは、部屋 または三角数 番目の部屋に移動します。バスに宿泊しているゲストは、部屋 または三角数プラスに移動します。このようにして、すべての部屋に 1 人のゲストだけが宿泊することになります。 ${\displaystyle (n^{2}+n)/2}$${\displaystyle n}$${\displaystyle ((c+n-1)^{2}+c+n-1)/2+n}$${\displaystyle (c+n-1)}$${\displaystyle n}$

このペアリング機能は、ホテルを 1 部屋の深さで無限に高いピラミッドとして構成することで視覚的に実証できます。ピラミッドの最上段は 1 つの部屋 (部屋 1) で、2 行目は部屋 2 と 3 というように続きます。右端の部屋のセットによって形成される列は、三角の数字に対応します。それらの部屋が (ホテルの再配分された宿泊者によって) 埋まると、残りの空室は元の形とまったく同じピラミッドの形を形成します。したがって、このプロセスを各無限セットに対して繰り返すことができます。各バスでこれを 1 つずつ実行すると、無限の数の手順が必要になりますが、前の式を使用すると、ゲストはプロセスでバスに到着したときに自分の部屋が「どうなるか」を決定し、すぐにそこに行くことができます。

は可算なので可算であり、したがってその要素を列挙することができます。ここで の場合、番目のバスの 番目のゲストを番目の部屋に割り当てます (ホテルにすでにいるゲストを 番目のバスのゲストと見なします)。したがって、各人に部屋を割り当てる関数が得られます。さらに、この割り当てではどの部屋もスキップされません。 ${\displaystyle S:=\{(a,b)\mid a,b\in \mathbb {N} \}}$${\displaystyle S}$${\displaystyle \mathbb {N} }$${\displaystyle s_{1},s_{2},\dots }$${\displaystyle s_{n}=(a,b)}$${\displaystyle b}$${\displaystyle a}$${\displaystyle n}$${\displaystyle 0}$

ホテルが海に隣接していて、無限の数のカーフェリーが到着し、それぞれが無限の数の客車を運び、それぞれが無限の数の乗客を乗せているとします。これは、3 つの「レベル」の無限を伴う状況であり、これまでのソリューションのいずれかを拡張することで解決できます。

素因数分解法は、無限大（ 、フェリー 付き）の追加層ごとに新しい素数を追加することによって適用できます。${\displaystyle 2^{s}3^{c}5^{f}}$${\displaystyle f}$

素数の累乗解法は、素数の累乗をさらに適用することで適用でき、小さな入力でも非常に大きな部屋番号が得られます。たとえば、2 番目のフェリーの 3 番目のバスの 2 番目の座席の乗客 (住所 2-3-2) は、2 番目の奇数の素数 (5) を 49 に累乗します。これは、3 番目の奇数の素数 (7) を座席番号 (2) に累乗した結果です。この部屋番号は、小数点以下 30 桁以上になります。

インターリーブ方式は、2 つのインターリーブされた「ストランド」ではなく、3 つのインターリーブされた「ストランド」で使用できます。アドレスが 2-3-2 の乗客は部屋番号 232 に行き、アドレスが 4935-198-82217 の乗客は部屋番号 #008、402、912、391、587 に行きます (先頭のゼロは削除できます)。

無限のゲストが何層にもわたって滞在する可能性を予想して、ホテルは、その後に何人のゲストが到着しても、ゲストが移動する必要がないように部屋を割り当てたいと考えるかもしれません。 1 つの解決策は、各到着者の住所を2 進数に変換することです。この 2 進数では、各層の先頭で 1 が区切り文字として使用され、特定の層内の番号 (ゲストのバス番号など) は、その数のゼロで表されます。 したがって、以前の住所が 2-5-1-3-1 (5 つの無限層) であるゲストは、部屋 10010000010100010 (10 進数では 295458) に移動します。

このプロセスの追加ステップとして、数字の各セクションからゼロを 1 つ削除することができます。この例では、ゲストの新しい部屋は 101000011001 (10 進数で 2585) です。これにより、すべての部屋に仮想ゲストが宿泊できるようになります。無限のゲストが到着しない場合は、2 の累乗の部屋のみが占有されます。

ヒルベルトのパラドックスは真実のパラドックスです。直感に反する結果が証明可能な真実につながります。「どの部屋にもゲストがいる」と「これ以上のゲストは宿泊できない」という文は、部屋の数が無限にある場合は 同等ではありません。

最初は、この状況は直感に反しているように思えるかもしれません。無限集合の性質は、有限集合の性質とはまったく異なります。ヒルベルトのグランドホテルのパラドックスは、カントールの超限数理論を使って理解できます。つまり、1 つ以上の部屋がある通常の (有限の) ホテルでは、奇数番号の部屋の数は明らかに部屋の総数よりも少なくなります。しかし、ヒルベルトのグランドホテルでは、奇数番号の部屋の数は部屋の総「数」よりも少なくありません。数学的に言えば、奇数番号の部屋を含む部分集合の濃度は、すべての部屋の集合の濃度と同じです。実際、無限集合は、同じ濃度の適切な部分集合を持つ集合として特徴付けられます。可算集合 (自然数と同じ濃度を持つ集合) の場合、この濃度は です。^[3]${\displaystyle \aleph_{0}}$

言い換えると、可算無限集合には自然数が含まれている場合でも、可算無限集合を自然数の集合に写像する全単射関数が存在します。たとえば、有理数集合 (整数の商として表せる数) には自然数が部分集合として含まれていますが、有理数は可算であるため、自然数の集合よりも大きくなることはありません。つまり、自然数から有理数への全単射が存在します。

• パラドックスのリスト – 矛盾しているように見える文のリスト
• バナッハ・タルスキのパラドックス – 幾何定理
• ガリレオのパラドックス – 集合論におけるパラドックス
• 集合論のパラドックス
• 鳩の巣の原理 - アイテムの数がそれを入れる箱の数より多い場合、1つの箱には少なくとも2つのアイテムが入っている必要がある

• ヒルベルト、デイヴィッド (2013)、エヴァルト、ウィリアム、ジーク、ウィルフリート (編)、デイヴィッド・ヒルベルトの算術と論理学の基礎に関する講義 1917-1933、ハイデルベルク: シュプリンガー・フェアラーク、doi :10.1007/978-3-540-69444-1、ISBN 978-3-540-20578-4