第4講 集合の濃度
集合の濃度
二つの集合 $A$，$B$ の間に全単射が存在するとき
$\# A=\# B$
と表し，このとき $A$ と $B$ の
濃度は等しいという．
有限集合については，例えば
$\#\{\,1,2,3\,\}=\#\{\,a,b,c\,\}$
のように，要するに濃度が等しいとは「要素の個数が等しい」ということである．
無限集合になると，例えばすべての正の偶数からなる集合を $2\mathbf{N}=\{\,2n\ |\ n\in\mathbf{N}\,\}$ と表すとき
$f:\mathbf{N}\to 2\mathbf{N},\ n\mapsto 2n$
は全単射なので $\#\mathbf{N}=\#2\mathbf{N}$，すなわち $\mathbf{N}$ と $2\mathbf{N}$ の濃度は等しい．この状況を「要素の個数が等しい」と表現できるかどうかは意見が分かれるところであろう．
この例のように，無限集合では，ある集合とその真部分集合との濃度が等しいということが起こる．このことは有限集合との決定的な違いと言ってよい．以下，我々の興味の対象は無限集合どうしの濃度の関係である．
この $\# A=\# B$ という関係は，次の意味で同値関係であるといえる：
- $\# A=\# A$
恒等写像 $id_A:A\to A$ は全単射である
- $\# A=\# B\Rightarrow \# B=\# A$
写像 $f:A\to B$ が全単射ならば，その逆写像 $f^{-1}:B\to A$ も全単射である
- $\# A=\# B,\ \# B=\# C\Rightarrow \# A=\# C$
写像 $f:A\to B$，$g:B\to C$ が全単射ならば，その合成写像 $g\circ f:A\to C$ も全単射である
Bernsteinの定理
集合 $A$ から集合 $B$ への単射が存在するとき
$\#A\le \#B$（または $\#B\ge \#A$）
と表す．
$f:\mathbf{N}\to \mathbf{R},\ x\mapsto x$ は単射なので $\#\mathbf{N}\le\#\mathbf{R}$ である．
一般に
$A\subset B\Rightarrow \#A\le \#B$
が成り立つ．包含写像 $f:A\to B,\ x\mapsto x$ は単射だからである．
よって，次の関係は直ちにわかる：
$ \#\mathbf{N}\le\#\mathbf{Z}\le\#\mathbf{Q}\le\#\mathbf{R}\le\#\mathbf{C}$
また，
次も成り立つ：
$ \#A\le \#B,\ \#B\le \#C\ \Rightarrow \#A\le \#C$
二つの単射の合成はやはり単射だからである．
は，$A$ から $B$ への単射，$B$ から $A$ への単射がともに存在するならば，$A$ と $B$ の間に全単射が存在することを主張する
証明pdf．この定理より直ちに
$\#A\le \#B,\ \#B \le \#A \ \Rightarrow\ \#A=\#B$
が成り立つことが言える．
不等号で表すと当たり前のことに見えるかもしれないが，決してそうではない．
おなじみの「$\le$」「$=$」といった記号は，ここでは「単射が存在する」「全単射が存在する」といった二つの集合の間の関係を示しているのであって，実数 $x$，$y$ の大小関係について
「$x\le y,\ y\le x\ \Rightarrow\ x=y$」というのとは意味が違うのである．
二つの集合の濃度が等しいというためには，それらの集合の間に全単射が存在することを言わなければならないが，全単射を具体的に構成することは一般には容易ではない．Bernsteinの定理は，例え全単射を具体的に構成できなくともその存在を保証してくれるという，集合の濃度を比べる際に非常に強力な役割を果たす．
$A=(-1,0)$，$B=[0,1]$ とする．開区間と閉区間なので，この二つの集合の間に全単射をつくろうとするとなかなか難しい．しかし，単射でよいのであれば，例えば
$f:A\to B,\ x\mapsto x+1$
$g:B\to A,\ x\mapsto -\dfrac{x}{2}-\dfrac{1}{4}$
のように簡単につくれる．
この $f$ と $g$ はもちろん全単射ではないが，
Bernsteinの定理によると，これらの単射の存在から $A$ と $B$ の間の全単射の存在が保証され
，従って
$\#A=\#B$
が結論できるというのである．
有限集合，可算集合，非可算集合
-
集合 $A$ が有限集合であるとは，ある $N\in\mathbf{N}$ が存在して
$\# A=\# \{\,1,2,\ldots,N\,\}$
となることをいう．
-
集合 $A$ が可算集合（または可算無限集合）であるとは
$\# A=\#\mathbf{N}$
となることをいう．
そもそも「物を数える」とは，対象物に $1,2,3,\ldots$ と番号をつけていくことであるから，
それは $\mathbf{N}$ (の部分集合)との間に全単射をつくることに他ならない．
そういうわけで，$\mathbf{N}$ との間に全単射が存在する集合は「数えられるcountable」「可算である」と言われるのである．
そういう意味では，「可算集合」という言葉は有限集合および可算無限集合を指すとも言えるが，習慣的に可算集合というとき有限集合は念頭に置かないことが多い．有限集合も含むことをはっきりさせたいときは「高々可算」という言い方をする．
-
有限集合でも可算集合でもない集合を非可算集合（または非可算無限集合）という．
数の集合としては
$\mathbf{N}$，$\mathbf{Z}$，$\mathbf{Q}$ は可算集合
$\mathbf{R}$，$\mathbf{C}$ は非可算集合
である．
特に，$\mathbf{Q}$ と $\mathbf{R}$ の違いに注目しよう．
$\mathbf{R}$ については次講で詳しく調べることにして，今回は $\mathbf{Q}$ が可算であることを確認しておきたい(練習3)．