基数

基数

全単射は今までの例を見てみると、始域の元と終域の元の数が全く同じでなければ作ることができません。

なぜなら、以前にも示した通り、
始域の元の数よりも終域の元の数の方が多い場合、全射をとることはできませんし、
また、始域の元の数よりも終域の元の数の方が少ない場合、単射をとることはできないからです。


ところで、これを逆に言えば、全単射の存在する集合同士は同じ元の数を持っている、というように考えることができると思います。
そのようにして定義された集合の元の数のことを基数、あるいは濃度といいます。
それでは、以下の例を見てみましょう。

自然数と整数、どちらが多い?

自然数の集合$\displaystyle{\mathbb{N}}$と整数の集合$\displaystyle{\mathbb{Z}}$、果たしてどちらの集合の方が多くの元を持っているでしょうか?

恐らく多くの方々は、
「だって整数の中で負の数でないのが自然数なわけだから、自然数って整数の半分の数しか持ってないわけでしょ?だから整数の方が多いに決まってるじゃん」
なんて考えるでしょう。
中には、
「うぅん・・・どちらも無限個の元を含んでいる分けだから、そもそも無限同士に大小関係とかあるの?」
なんて考える人もいたりして(笑)

さぁ、そこで先ほど紹介した、「全単射が存在すれば、二つの元の数は同じ」という規則を使いましょう。
果たして$\displaystyle{\mathbb{N}}$$\displaystyle{\mathbb{Z}}$の間に全単射が存在するのでしょうか?

まず次のような関数を考えましょう。
$\displaystyle{f(x)=\cases{{\frac{x-1}{2}}&(xが奇数)\\{-\frac{x}{2}}&(xが偶数)}}$
もし、この関数が何をやっているのか分からなければ、

$\displaystyle{f(1),f(2),f(3),f(4),f(5),f(6),f(7),\cdots}$

と並べてみますと、

$\displaystyle{0,-1,1,-2,2,-3,3,\cdots}$

となります。こうすると見やすくなると思います。

よ〜く見てください。これって全単射じゃないですか?
だって、このように並べてみますと、全ての整数は絶対にこの数の並びに含まれることが分かります。つまり全射です。
また、この並びでは整数が重複して現れるようなことは絶対にないと思います。つまり単射です。

だから$\displaystyle{\mathbb{N}}$$\displaystyle{\mathbb{Z}}$の間には確かに全単射が存在することになります。
つまり全単射が存在する→$\displaystyle{\mathbb{N}}$$\displaystyle{\mathbb{Z}}$は同じ大きさの集合!!

実は、自然数と整数の元の数は同じだったのです!!!
何だか非直感的なので、最初は信じられないかもしれないですが、そうなるものだと思って下さい。

偶数と整数、どちらが多い?

「そりゃさすがに整数の方が多いに決まってるじゃん。だって偶数の半分が整数なわけだから・・・」
なんてことは、前に述べたのを見るとそうとも言ってられませんね。
$\displaystyle{f(x)=2x}$
これは明らかに全単射となります。
よって偶数と整数の元の数も等しいことになります。
また、整数と自然数の元の数も等しいため、
偶数と自然数の元の数も等しいことに・・・
また同様に、奇数も自然数の元の数と等しくなります。

自然数とその直積、どちらが多い?

直積、つまり
$\displaystyle{\mathbb{N}\times\mathbb{N}}$
は覚えてますね?

さて$\displaystyle{\mathbb{N}}$$\displaystyle{\mathbb{N}\times\mathbb{N}}$では、どちらの元が多いでしょうか?
「もちろん、直積って元の数が多くなるわけだから、直積の方が・・・」
さて、本当にそうでしょうか?
また、先程と同じように、
$\displaystyle{f(1),f(2),f(3),f(4),f(5),f(6),f(7),\cdots}$
と並べてみるとすると、
$\displaystyle{(1,1),(2,1),(1,2),(1,3),(2,2),(3,1),(4,1),\cdots}$

となるように関数$\displaystyle{f}$を定めます。
これが一体どのような規則性で並んでいるのか一見分かりにくいと思うので、下の図を見てみましょう。



この図を見てみると、上の並び、つまり$\displaystyle{f(x)}$$\displaystyle{\mathbb{N}\times\mathbb{N}}$を隙間なく埋めてくれることが分かります。

隙間なく$\displaystyle{\mathbb{N}\times\mathbb{N}}$の集合 を埋め尽くすことができるということは、全射が存在するということです。当然、重複も現れないので単射にもなれます。

ということは・・・信じられないことに$\displaystyle{\mathbb{N}}$$\displaystyle{\mathbb{N}\times\mathbb{N}}$は同じ元の数を持っている、ということになります。

同様に$\displaystyle{\mathbb{N}}$$\displaystyle{\mathbb{N}\times\mathbb{N}\times\mathbb{N}}$も同じ元の数だということも示せると思います。

自然数と有理数、どちらが多い?

それでは、自然数と有理数も同じ基数になるのでしょうか?
任意の有理数は、適当な整数$\displaystyle{a}$$\displaystyle{b}$を選んで、
$\displaystyle{\frac{a}{b]}$
の形に表すことができます。
つまり、どんな形の有理数でも整数分の整数の形に表すことができます。

ところで、前に示した通り、自然数と自然数の直積は同じ集合の数を持っています。
また、 だから、有理数は2つの整数で全て表すことができると考えると、
$\displaystyle{f(1),f(2),f(3),f(4),f(5),f(6),f(7),\cdots}$

$\displaystyle{\frac11,\frac12,\frac21,\frac31,\frac13,\frac14,\frac34,\cdots}$
と、表せることができます。
$\displaystyle{\frac22}$$\displaystyle{\frac24}$は飛ばしましたが、
それは既に出てきた$\displaystyle{\frac11}$$\displaystyle{\frac12}$が同じ数だからです。
同じものが2回出てきては、単射になることはできないですから。

このように、有理数も自然数と同じ元の数をもっていることが分かりました。
今の議論では0より大きな有理数しか示していないですが、0より大きい有理数と有理数全体が同じ基数を持つことはすぐ分かると思います。。。

自然数と実数、どちらが多い?

なんと自然数と有理数が同じ基数を持つことが分かりました。
それでは、自然数と実数はどうでしょうか?

今までのように自然数と実数も同じ基数を持つことが示せそうです・・・と思いきや?
実は自然数と実数の間には全単射を定義することがどうしてもできません!!!
だから、実数だけは、自然数より確かに多いのです。
これは意外・・・

自然数と実数が同じ基数を持つことができないことの証明は、ここでは省略します・・・。

可算集合

$\displaystyle{\mathbb{N}}$と同じ濃度を持つ集合のことを可算集合といいます。
可算集合の濃度のことを可算個といい、記号$\displaystyle{\aleph_0}$(アレフゼロと読む)と表すことがあります。
「可算集合」とは、漢字から、「数えられる集合」というイメージがありそうですが、有限集合でなく無限集合なので、そこは気をつけましょう。
また、有限集合の基数と可算集合の基数を含めて、高々可算個の集合と呼ぶこともあります。
$\displaystyle{\mathbb{R}}$のように、可算個でない無限集合のことを非可算集合といいます。 非可算集合の基数を非可算個といいます。

戻る