集合の基数（濃度）について

直前のエントリで「写像と単射と全射と全単射について - IIJIMASの日記」写像と特別な写像について説明しました。
特に、全単射（1対1対応）の存在は強力な性質で、AとBの間に1つでも全単射が存在すると有限集合の場合要素数が同じということがわかってしまいます。
無限集合で要素数を考えると「無限大」しかなさそうですが、自然数は無限でも順番に数えてゆくことができますが、有理数や実数はどんな2数の間にも数があり順番に数えることができなそうです、実は無限にも大小関係がありそうです。
全単射を利用して基数（濃度）という個数を拡張した概念を定義します。
ある集合Aとある集合Bの間に全単射が存在するときに、Aの基数とBの基数（濃度）は等しいと定義します。有限集合の場合は個数とします。集合Aに対する基数を#Aで表します。
特に、自然数全体の集合の基数を $\aleph_0$ （アレフ・ゼロ）という記号で表します。自然数全体の集合 {1, 2, 3, ・・・} は記号 $\mathbb{N}$ で表しますので# $\mathbb{N}$ = $\aleph_0$ です。
無限集合では面白いことに、部分集合が全体と同じ濃度を持っていても不思議ではありません。
事実、自然数全体と正の偶数全体には全単射(n → 2n)があります。明らかに正の偶数全体は自然数の部分集合です。しかし、基数は同じなのです。
さらに驚いたことに整数全体 $\mathbb{Z}$ ={・・・, -2, -1, 0, 1, 2, ・・・}も自然数 $\mathbb{N}$ ={1, 2, 3, ・・・}と同じ基数なのです。たとえば、写像fを $\mathbb{Z}$ の要素zについて、z<=0の時は f(z) = 2|z| ∈ $\mathbb{N}$ 、z>0の時はf(z) = 2z - 1 ∈ $\mathbb{N}$ と定義すれば、全単射になります。
面白いことに、自然数の２つ組(n, m)の全体 $\mathbb{N}^2$ を考えても、 $\mathbb{N}$ と基数は変わりません。たとえば、写像 $f: \mathbb{N}^2 \large\right \mathbb{N}$ を $f(n,m) = \frac{(n + m - 1)(n + m - 2)}{2}+m$ と定めます。逆写像 $g: \mathbb{N} \large\right \mathbb{N}^2$ は少々複雑ですが $p = \lfloor \frac{1+\sqrt{1+8(t-1)}}{2} \rfloor$ （ただし、 $\lfloor x \rfloor$ は $x$ を超えない最大の整数を表す）とおいて、 $g(t) = (\frac{p (p+1)}{2}+1-t, t - \frac{p (p-1)}{2})$ と定義できて、f, gは全単射(1対1対応)となることがわかります。
$\mathbb{N}^2$ と $\mathbb{N}$ の基数が等しいことがわかりましたので、 $\mathbb{N}^3$ も $\mathbb{N}^2$ と基数が等しい（たとえば、 $\mathbb{N}^3$ の最初の2成分を、 $\mathbb{N}^2$ 最初の成分に対応させる）、結局 $\mathbb{N}$ の基数 $\aleph_0$ と等しいことがわかります。一般に $\mathbb{N}^m$ (mは任意の自然数)も基数は $\aleph_0$ であることがわかります。
またすべての有理数は分数つまり整数の比で表せるのですから、有理数全体は整数の２つ組(n, m)の全体と対応させることができます。単純に(n,m)とn/mを対応させてしまうと、同じ分数を表す、(n,m)が複数あることになってしまいますが、一度出てきたもの（既約分数でないもの）は飛ばして、対応させれば、自然数と1対1対応であることがわかります。