濃度のお話

前の「ヒルベルトの無限ホテルのパラドックス」の話の時に、集合の濃度の話をしたんですが、よく考えると等しいモノの例しか出さずに、等しくないものの例については何も言ってなかった事を思い出しました。 それじゃあ濃度の存在意義が分かりづらいので、今回は、濃度が等しい例を1つ、濃度が等しくない例を2つ話します。
（話すつもりでしたが長くなるので今回は濃度が等しい例のみになりました）

注：今回は無限ホテルのに比べるとガッツリ数学やります。

---

濃度が等しい例については前もやりましたが、
それとは別の例をあげてみます。
自然数全体の集合と、
自然数の5つの組全てを集めた集合（[1.2.3.4.5]とか、[2.64.1.4.7]とか、[5.4.3.2.1]とか）
という2つの集合の濃度は等しいでしょうか？
つまり、このふたつの集合の間に、1体1対応が作れるのでしょうか？
答えはyesです。

まずは、自然数の集合（Nとします）と、自然数の2つの組全ての集合（N^2と書きます）の濃度が等しいことを見てみましょう。
では、N^2の要素それぞれに対して、対応するNの要素を決めていきましょう。（これはN^2からNへの写像を定義している。と言い換えできます）
ここでは、[i, j]という自然数の組に対して、
対応するNの要素、つまり自然数を、
i＋（（i+j-1）（i+j-2）/2）というふうに対応させます。これが、

b)異なる要素の対応は違う対応
c)全ての自然数に対して、N^2のある要素の対応になっている

を満たすことを示せばいいですね。（aの、N×Nの要素には全て何かが対応している、というのは明らか）

bから示します。つまり、a,bという組と、(c.d)という組が異なるものとして、対応先が違うことを示せばOKです。

（a+b＝c+dの時）
この時、(a+b-2) (a+b-1)/2＝ (c+d-2) (c+d-1)/2
ですね。
ここで、
もしa＝cなら、b＝dもついてくるので、問題なし。

a≠cなら、それぞれの対応先である、
a＋(a+b-2) (a+b-1)/2とc＋(c+d-2) (c+d-1)/2は異なることになりますね。

これで、a＋b＝c＋dの時はbが成り立ちます。

（a＋b≠c＋dの時）
a＋b＜c＋dの時に示せば、2つの組のうち、和が大きい方をc,dに代入すればいいので証明には十分です。
a＋b＜c＋dとします。
b、cは自然数ですから、
a,b の対応先
＝a＋(a+b-2) (a+b-1)/2
≦a＋b-1＋(a+b-2) (a+b-1)/2
＝【2(a+b-1)＋(a+b-2) (a+b-1)】/2
＝(a＋b)(a＋b−1）/2
＝（a＋b+1-1）（a＋b＋1-2）/2

a＋b＜c＋dで、a＋bとc＋dは自然数だから、
a＋b＋1≦c＋dであるから、

（a＋b+1-1）（a＋b＋1-2）/2
≦（c＋d-1）（c＋d-2）/2
< c＋（c＋d-1）（c＋d-2）/2＝c, dの対応先
長い式変形でしたが、これでa, bの対応先＜c,dの対応先、つまりはa, bの対応先≠c,dの対応先が言えました。
これでb）は示せましたね。
次にcを示しますが、こちらは簡単です。
示すのは、自然数nを自由に取ってきた時に、nが対応先となる自然数の組i, jが存在することです。
自然数nに対して、
（m-2)(m-1）/2 ≦n <((m+1)-2）((m+1)-1)/2
を満たすmが必ず存在します。（m＝3の時左の式は1を取り、mが大きくなると、単調にいくらでも大きくなるから）
そのmを用いて、i＝n-（m-2)(m-1）/2
j＝m-iとすると、iとjは自然数になります。
（iが自然数なのはは明らかだし、jも、iを定義した式で置き換えるとわかる）
このiとjを使えば、i, jの対応先はnになります。

少し長かったですが、これでこの対応がb,cを満たすことがわかったので、NとN^2の濃度が等しいことがわかりました。

実は、これによって、どんな大きな自然数mに対しても、Nと、自然数のm個の組の集合（N^mと書く）は同じ濃度である、つまり1体1対応があることが示せます。
ということで示してみましょう。

数学的帰納法で示します。NがN自身と濃度が等しいのは自明だし、さっきNとN×Nの濃度が等しいことは示しました。
では、ここでNとN^k（自然数のk個の組の集合）の濃度が等しいと仮定しましょう。つまり、N^kの要素から、Nへの1体1対応が存在するということです。これで示したいのは、N^k+1とNの濃度が等しいことです。
少し遠回りですが、まずは、N^k＋1とN^2の濃度が等しいことを示しましょう。

やることは変わらず対応を決めることです。
自然数のk+1個の組を自由に取ってきます。
そして、この組の中で、1番目からk番目までの自然数と、残りのk+1番目に分けます。
ふたつに分けたグループ分けで、それぞれに自然数の1体1対応をつければいいですね。

1番目からk番目までの自然数の組の対応先に対しては、仮定「N^kからNへの1体1対応が存在する」より、その対応を使って、その対応先である自然数Aを取ります。

k+1番目の自然数に対しては、そのままその自然数を対応先として取ります。
最終的に対応先は、（A、k＋1番目の数）となります。

このようにN^k+1からN^2への対応をとると、これはb,cを満たします（考えてみよう）

ここで、NとN^2は濃度が等しいですから、N^2からNへの1体1対応が存在します。
なので、N^k+1からNへの対応を、

｢N^k+1からN^2への対応先｣のN^2からNへの対応先

としましょう。
つまり、あるk＋1個の自然数の組を持ってくると、それに1体1で対応する2組の自然数があって、その2組の自然数に対して1体1に対応する1つの自然数があるから、それを新しい対応の対応先にしよう、ということです。

このように対応を定めると、この対応はb,cを満たします。
2つの異なる｢k+1個の自然数の組｣を持ってきた時、それに1体1対応する2組の自然数はお互いに異なるものになります。
なので、その2組の自然数が1体1対応する先も異なるものになります。よってbが成り立ちます。

どんな自然数aに対しても、対応先がその自然数aであるような2組の自然数が存在します。その2組の自然数に対しても、それが対応先になるようなk＋1個の自然数の組が存在します。そしてそのk＋1個の自然数の組のNへの対応先はaとなります。
これでcも示せたので、NとN^k＋1の濃度は等しいことがわかりました。

数学的帰納法より、どんな自然数mに対しても、
自然数の集合と、m個の自然数の組全体の集合の間に1体1対応が作れることがわかりました。

---

最初にこれを証明した時は、頭では納得していても不思議な気持ちが残っていました。
こういう時のような変な感覚が好きで僕は数学をやっているのかもしれません。

本当は今回で濃度の違う集合の話もしたかったですが、ここからその話をしだすと、5000文字行きそうな勢いなので、次に回します。
読んでくださった方がいたらありがとうございました！