2014/11/30

集合の濃度と可算無限・非可算無限

分野: 代数,情報・暗号理論  レベル: 大学数学

有限集合の大きさは要素数ではかれる。
無限集合の大きさの表現には濃度を用いる。

高校数学の範囲を逸脱していますが非常に有名な話題です。

集合論における濃度

・集合 $A$ の大きさ $|A|$ について考えます。 $A$ が有限集合のときには $|A|$ を $A$ の要素数とすればよいのですが,無限集合のときは要素数を数えることができません。無限集合の中でも「要素がたくさんある」ものと「要素があまりない」ものを区別するために,集合に対して濃度という概念が定義されます。

濃度の定義:
1:有限集合 $A$ の濃度 $|A|$ は $A$ の要素数とする。
2:$A$ から $B$ への全単射(一対一対応)がある場合(またそのときに限って)$|A|=|B|$ とする。
3:集合 $A$ から $B$ への単射が存在するとき,$|A|\leq |B|$ とする。

  • 単射とは $x\neq y$ ならば $f(x)\neq f(y)$ となる関数,つまり行き先がかぶらない関数のことです。単射があれば行き先の方が広い(狭くはない)というわけです。
  • 2と3が矛盾しないことは厳密にはベルンシュタインの定理というものによって保証されます。
  • 無限集合の濃度は大小関係しか表すことができません。つまり,「こちらの無限集合がより濃度が大きい」とか「濃度が等しい」などと述べることはできますが,集合 $A$ の濃度はいくらか?ということは多くの場合問題にしません。

無限集合の濃度の具体例

・整数全体の集合 $\mathbb{Z}$ の濃度と正の整数全体の集合 $\mathbb{N}$ の濃度は等しい。
濃度が等しいというのは全単射が存在するということです。そこで,整数全体の集合と正の整数全体の集合の間の一対一対応を作ることで証明します。

証明

整数全体の集合から正の整数全体の集合への関数 $f$ を以下のように定める:
$f(x)=2x+1\:(x\geq 0),\:f(x)=-2{x}\:(x <0)$
とおくと,例えば $f(-2)=4,\:f(-1)=2,\:f(0)=1,\:f(1)=3,\:f(2)=5$ などとなり,$f$ は $\mathbb{Z}$ から $\mathbb{N}$ への全単射である。

自然数の方が整数よりもたくさん(二倍くらい)あるじゃないか!と思いますが,濃度という観点から見ると両者は同じです。


・偶数全体の集合と整数全体の集合の濃度は等しい。
証明は先ほどと同様に全単射を構成してやればOKです。簡単にできます。


・正の整数全体の集合と有理数全体の集合の濃度は等しい。
直感的には有理数の方が圧倒的にたくさんありますが,濃度という観点から見ると両者は同じなのです!

大雑把な証明

正の有理数全体の集合 $\mathbb{Q}_+$と $\mathbb{N}$ の濃度が等しいことを言えばよい。

正の有理数 $\dfrac{q}{p}$ を $p+q$ を小さい順に並べて既約分数のみ残して番号を振っていけば,$\mathbb{Q}_+$から $\mathbb{N}$ への全単射が構成できる:
$f(\frac{1}{1})=1,\:f(\frac{1}{2})=2,\:f(\frac{2}{1})=3,\:f(\frac{1}{3})=4,\:$
$f(\frac{3}{1})=5,\:f(\frac{1}{4})=6,\:f(\frac{2}{3})=7,\cdots$


・任意の集合 $A$ に対して,$A$ のべき集合の濃度は $A$ の濃度より真に大きい(カントールの定理)。
→カントールの定理の証明と対角線論法


・実数全体の集合の濃度は有理数全体の集合の濃度より真に大きい。
有理数と実数の間には濃度の意味でギャップがあります。証明には対角線論法というものを用います。

可算無限と非可算無限

  • 正の整数全体の集合 $\mathbb{N}$ と濃度が等しい集合を可算集合といいます。可算集合の要素は可算無限個などと言います。可算無限とは「無限個あるけど番号をふっていける程度」の無限です。
  • 上記の例から分かるように,整数は可算無限個であるのはもちろん,有理数も可算無限個です。
  • 可算集合は $\mathbb{N}$ と全単射があるので,要素に $1$ から順番に番号をふっていくことができます。そのため可付番集合とも言います。
  • 無限集合であり,可算集合でないものを非可算集合と言います。実数全体や複素数全体は非可算無限です。非可算無限とは「番号をふることすらできない」無限です。
整数と有理数の濃度が等しいというのは感覚的に理解しがたいですね。
分野: 代数,情報・暗号理論  レベル: 大学数学