無限ホテルのパラドックス
こんにちは。
今回は、無限ホテルのパラドックスについて紹介します！
無限ホテルのパラドックスとは
無限に客室があるホテルがすべて客で埋まっていて満室でも新たに来た人を泊められるというものです。
たとえば、無限の客室があって満室のときに一人客が来て泊まりたいと言った場合、どうすれば泊めてあげられるでしょうか？
普通に考えて満室なんだから泊まれるわけないじゃん？と思いますよね？
でもこうすれば泊まれます。
１号室の客を２号室に、２号室の客を３号室に、・・・ｎ号室の客を（ｎ＋１）号室に移動させれば１号室が空くので泊まれます。
これは無限に部屋があるのでできます。
数学的な解説はあとでします。
次に無限ホテルに無限の客が来た場合はどうでしょう？
いやいやこれはさすがに無理でしょう。と思いますよね？
でもこうすればいいのです。
１号室の客を２号室に、２号室の客を４号室に、・・・ｎ号室の客を２ｎ号室に移動させれば
奇数号室はすべて空室となるので無限の客を泊めることができます（当然奇数は無限に存在します）。
これを数学的に考えてみましょう。
まず、最初の例で考えます。最初の例では、初めの無限と１人泊めた状態の無限は同じだと言っています。
もう少し数学的に言うと、この２つの無限の間には全単射が存在するので濃度が等しいといえます。
全単射とか濃度とか聞いたことがない用語が出てきたので解説していきます。
全射、単射、全単射とは
まずこれらの定義の前に写像について定義します。
定義 写像
集合Xの各元xに集合Yの１つの元ｙを対応させる規則をXからYへの写像といいｆ：Ｘ→Ｙと表します。
写像ｆ：Ｘ→Ｙによってa∈Xがb∈Yに対応するときbをｆによる像といいb=ｆ(a)と表します。
次に全射の定義をします。
定義 全射
写像ｆ：X→Yが全射とは任意にy∈Yを取ったときにx∈Xが存在してy=ｆ(x)が成り立つときに言います。
次は単射の定義です。
定義 単射
写像ｆ：X→Yが単射とはｆ(x1)=(x2)のときx1=x2が成り立つときに言います。
対偶を取ると、x1≠x2のときにｆ(x1)≠ｆ(x2)ということになります。
つまり違う元は違う元に写されるということです。
最後に全単射の定義をします。
定義 全単射
ｆが全射かつ単射のときｆは全単射であると言います。
ではこの全射、単射、全単射とさきほどの無限ホテルのパラドックス、何の関係があるのでしょうか？
全射、単射、全単射について図で考えてみます
まずは全射から
・→・
・→・
・→・
・
・
図ではこういうことになります。
つまりどんなyを取ってもxが存在してればいいのでXの集合の方には対応していない元があっても問題ありません。
Yの方にすべて対応がついていれば問題ないということです。
次は単射について
単射とはこういう状況です。
・→・
・→・
・→・
・
・
x∈Xに対して違ったyが対応していれば問題ないのでこうなります。
Xの元すべてにYの元が対応しているので、Yの元の中に対応しない元があっても大丈夫です。
そして全単射とはこういう状況です。
・→・
・→・
・→・
・→・
・→・
すべてのx∈Xにy∈Yが対応している状況です。
ではそれぞれの図でXとYにある元の個数を考えてみましょう。
全射の場合
全射の場合は、Xの元が5個、Yの元が3個となり
一般にXの元の個数を|X|で表すと|X|≧|Y|となります。
つまりXの元の個数がYの元の個数以上であるということです。
単射の場合
単射の場合はXの元が3個、Yの元が5個となって|X|≦|Y|となります。
つまりYの元の個数がXの元の個数以上であるということです。
全単射の場合
全単射の場合は、X、Yとも5個の元からなっているので|X|=|Y|となります。
つまりXの元の個数とYの元の個数が同じであるということです。
つまりXとYの間に全単射が存在⇔XとYの濃度は等しいとなります。
用語 |X|をXの濃度といいます。
それでは例で考えてみましょう。
最初の例で満室の無限ホテルに１人来た場合、１号室の客を２号室に、２号室の客を３号室に・・・といいましたが、どのような対応が行われているのでしょうか？
これはｆ：ｎ→ｎ＋１という対応がついていることがわかります。
このｆが全単射となるので最初の状態と１人客が増えた状態で人数（濃度）は同じと言っているのです。
おいおい、ちょっと待って。
１人増えてるのに同じってどういうこと？
そうなんです、ここが無限の扱いの難しいところであり、面白いところでもあるのです。
無限は数ではなく状態を表すので無限に１足した程度では無限という状態は変わらないのです。
ちなみに無限にも階層があって、自然数の濃度と正の偶数の濃度は同じですが、自然数の濃度と実数の濃度を比べると
実数の濃度の方が圧倒的に大きいです。
では１人増えても同じということを証明していきます。
さきほどの全単射の概念を思い出しましょう。
全単射が存在すれば濃度は同じでしたね？
ｆ：ｘ→ｘ＋１について考える。ｆは全単射である。
（証明）
全射であること
y=ｆ（ｘ）=ｘ＋１とする。ただしxは自然数です。
このときy=x+1⇔x=y-1となりこのxに対し
ｆ（x）=ｆ（y-1）=（y-1）+1=y（y≧2）
となるのでｆは全射となります。
単射であること
ｆ（x1）=ｆ（x2）とします。
つまりx1+1=x2+1となります。
このときx1=x2であることは容易にわかるので単射となります。
つまりｆは全単射となるので１人泊められることがわかります。
この説明ではよくわからない人のためによく出している例があります。
それは玉入れの数え方です。
小学校などで赤組と白組にわかれて玉入れをしたときどうやって勝ち負けを決めたか覚えてますか？
実は赤が１と言って玉を出し、白も１と言って出す、赤が２と言って出し、白も・・・
これを繰り返していき出せなくなった方が負け（もう出せる玉がない）ということです。
これの何が数学と関係しているの？とお思いですよね？でもこれこそが全単射（1対1対応）の例なんです。
つまり先ほどの無限の例だと赤玉に対して白玉を永遠に出すことができる場合、つまりxに対しyが対応していてそれが全単射である
場合は、永遠に対応がつけられるので濃度は同じとなるのです！
今度は無限人泊まりに来た場合を考えてみましょう。
無限人泊まりに来た場合は1号室の客は2号室に、2号室の客は4号室に・・・
つまりｆ：ｘ→２ｘとなります。
これが全単射であることを示してみましょう。
全射性について
y=ｆ（x）=2ｘとおく。このときx=y/2（2≧y）となります。
このxに対してｆ（x）=ｆ（y/2）=2・y/2=yとなるので全射となります。
単射性について
ｆ（x1）=ｆ（x2）とする。つまり2×1=2×2とします。
このとき両辺を2で割ってx1=x2が成立します。
よってｆは単射となります。
以上よりｆは全単射となり、無限ホテルにさらに無限人泊められることが示せました。
いかがだったでしょうか？
無限ホテルのパラドックスについて少しは理解できましたでしょうか？
そもそも無限にある部屋が満室ってどういう状況だよって思いますし
満室なのに泊まれるとか言われてもなおさら意味不明ですよね。
今回はそんな直観に反する無限のお話でした。
今回は以上になります。ありがとうございました！
参考文献
[1]無限について－無限に関するパラドックス（２）
