この記事には参考文献や外部リンクの一覧が含まれていますが、脚注による参照が不十分であるため、情報源が依然不明確です。適切な位置に脚注を追加して、記事の信頼性向上にご協力ください。（2020年12月）
ヒルベルトホテル

ヒルベルトの無限ホテルのパラドックス（ヒルベルトのむげんホテルのパラドックス、英: Hilbert's Infinite Hotel Paradox）とは、無限集合の非直観的な性質を説明する思考実験である。無限個の客室があるホテルは「満室」でも（無限人の）新たな客を泊めることができ、その手順を無限に繰り返せることを示す。論理的・数学的に正しいが、直観に反するという意味でのパラドックス（擬似パラドックス）である。ヒルベルトのグランドホテルのパラドックス（英: Hilbert's paradox of the Grand Hotel）、ヒルベルトホテル（英: Hilbert's Hotel）とも。1924年にダフィット・ヒルベルトが論文「Uber das Unendliche（無限について）」で導入し[1]、1947年のジョージ・ガモフの著書「1、2、3…無限大」によって広まった[2][3]。

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

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

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

また、無限人の新たな客を泊めることも可能である。1号室の客を2号室に、2号室の客を4号室に、n号室の客を2n号室に移動させれば、すべての奇数号室（可算無限個ある）が新たな客に解放される。
それぞれ無限人の客を乗せた無限台のバス詳細は「対関数」を参照

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

i号室の客を2i号室に移動させて奇数号室を空け、1号車の団体客を3n号室に、2号車の団体客を5n号室に、一般にc号車の団体客を、c番目の奇素数をpとして、pn号室に泊める。この方法ではいくつかの客室が空室になる（それがホテルにとって有益かはともかく）。具体的には15や847などのすべての素数冪でない奇数号室は誰も泊まっていない状態になる（よって厳密な議論では、これは来客者数が最初に空けた客室数に等しいかそれより少ないことを示している。正確に合うようにアルゴリズムを修正するよりも、これとは独立に、来客者数が最初に空けた客室数に等しいかそれより多いことを示し、したがってそれらが等しいことを示す方が簡単である）（このアルゴリズムはnとcを入れ替えても成り立つが、どちらかを選んで固定し、一貫して適用しなければならない）。
素因数分解を用いる方法

座席s、号車cの乗客を2s3c号室に泊める（元のホテルの客はc = 0、1号車はc = 1、…とする）。すべての正の整数は一意的に素因数分解できるので（算術の基本定理）、すべての客が部屋に入り、同じ部屋に2人入らないことがわかる。たとえば2592 (2534) 号室の客は、4号車の5番目の席に座っていた乗客である。素数冪を用いる方法と同様に、この方法ではいくつかの客室が空室になる。

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

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

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

元のホテルの客を(n2 + n)/2（すなわちn番目の三角数）号室に移動する。バスの団体客を[(c + n - 1)2 + (c + n - 1)]/2 + n（すなわち(c + n - 1)番目の三角数 + n）号室に泊める。これですべての客室が重複なく埋まる。

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

S := { ( a , b ) ∣ a , b ∈ N } {\displaystyle S:=\{(a,b)\mid a,b\in \mathbb {N} \}} とする。 N {\displaystyle \mathbb {N} } は可算なのでSは可算であり、その要素s1, s2, ...を列挙することができる。ここでsn = (a, b)とし、a号車のb番目の乗客をn号室に割り当てる（元のホテルの客はa = 0とする）。これで全員を客室に割り当てる関数ができ、なおかつ、この割り当てはどの客室ももらさない。
さらなる無限の階層

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

素因数分解を用いる方法は、無限の階層が増えるごとに新たな素数を追加することで適用できる（2s3c5f、フェリーの番号をfとする）。

素数冪を用いる方法は、さらなる素数の冪乗をとることで適用でき、結果として小さな入力でも非常に大きな部屋番号になる。たとえば、2番目の座席-3番目のバス-2番目のフェリー（番地2-3-2）に該当する乗客の部屋番号は、572 = 549（底は2番目の奇素数である5、指数は3番目の奇素数である7の2乗 = 49）となり、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（5つの無限の階層）の客は、10010000010100010（十進数で295458）号室に行くことになる。

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

無限人の客が有限回入れ子になっている場合は部屋を作れるが、各階層の客が有限人だったとしても無限回入れ子になっている場合は常にそうとは限らない（客が3.271260067…のように無理数でコーディングされる場合その集合は非可算になり得る）。
考察

ヒルベルトのパラドックスは擬似パラドックスである。