集合の濃度、そしてそこから

集合論の1つのテーマとして、元の数が無限にある集合同士の大きさの比較がある。これは、前の記事でもやったが、濃度という概念であり、写像の全射、単射を用いている。

全射というのは、もれがないということである。写像先の集合の元すべてに対応関係がある。単射というのは、ダブらないということである。元を変えれば、必ず違う結果となる。

全射でもあり単射でもあるとき全単射であるといい、元の集合の元すべてと写像先のすべての元が1対1対応している。この場合、元の集合の元の個数と写像先の集合の元の個数が等しくないといけないことはわかるだろう。元の集合の元の個数が一つでも多くなってしまうと必ず行先がかぶってしまい単射ではなくなる。逆に写像先の集合の元の数のほうが一つでも多かったとしよう。すると、写像の定義から、一つの元から2つ以上の元を指定することはできない。なので、写像先の集合の元が1つ余ってしまう。つまり、全射ではなくなる。

これからわかることは、2つの集合に対する写像を考えるとその写像がどんな性質を満たしているかで集合の大きさを比べることができるのである。(全単射なら個数が一緒だとわかるように)

実はこれ濃度の大小につながっている。集合Aから集合Bへの全単射が存在するときAとBは濃度が等しいという。これは特に無限集合の大きさを比較するのに用いられる。

濃度という単語を学んだので、これを用いる単語を紹介しよう。それは、可算集合である。自然数全体の集合と濃度が等しい集合のことを指している。

整数全体の集合や有理数全体の集合は可算集合だが、実数全体の集合はそうではない。連続性の公理からもわかる通り、有理数と実数の間には大きな壁があるようだ。実数全体の集合が可算集合ではないということは、対角線論法という方法で証明されている。

濃度という概念に対して、ベルンシュタインによる次の定理がある。

集合A,Bに対し、AからBの単射、BからAへの単射が存在すれば、AとBのの濃度は等しい。この証明はいろいろあるが、今回は省略させていただくが、ざっくり説明させてもらう。Aの元の個数をa,Bの元の個数をbとしよう。AからBの単射が存在するなら、bがa以上でることがわかり、BからAのほうでaがb以上であることがわかる。するとa=bとなる。