集合の濃度

集合の濃度とは集合の元の個数を拡張した概念のことです．

今回は，濃度という概念を導入し，無限集合の性質について解説していきます．

まずは，濃度の定義について確認します．

濃度の定義

集合 $A,B$ の間に全単射があるとき， $A$ と $B$ は対等であるという．
集合 $A$ と対等な集合全体の集合（実は集合と呼ぶには大きすぎる）を $A$ の濃度といい， $|A|$ とかく．もし， $A$ と $B$ が対等ならば， $|A|=|B|$ となる．

対等な集合の例

・集合 $A$ が有限集合のとき，すなわち， $A$ の要素の数が $n$ 個のときは，集合 $\{1,2,\dots ,n\}$ と全単射があるはずなので， $|A|=|\{1,2,\dots ,n\}|$ となる．これより，有限集合の濃度は元の個数であるといえる．

・自然数全体の集合 $\mathbb{N}$ は，整数全体の集合 $\mathbb{Z}$ と対等．
写像 $f:\mathbb{N} \longrightarrow \mathbb{Z}$ を次のように定義すれば， $f$ は全単射となる． $$f(x)= \left\{ \begin{array}{cccc} \frac{x-1}{2}\quad (x\ :\ odd\ number)\\ \ \ \,\frac{-x}{2}\ \quad (x\ :\ even\ number) \end{array} \right. $$

定義から次の関係はすぐにもとまります．このような関係を同値関係といいます．

$|A|=|A|$ （ $A$ から $A$ への恒等写像を考えれば良い）
$|A|=|B|\Longrightarrow |B|=|A|$ （全単射の逆写像は全単射より）
$|A|=|B|,|B|=|C|\Longrightarrow |A|=|C|$ （全単射の合成写像は全単射より）

濃度の大小

次に濃度の大小について考えます．

濃度の大小の定義

集合 $A$ が集合 $B$ のある部分集合 $B’$ と対等なとき， $|A|\leq |B|$ と定義する．このとき， $A$ と $B$ が対等でないなら， $|A|\lt |B|$ と定義する．

$|A|\leq |B|$ のとき， $|B|$ は $|A|$ 以上といい， $|A|\lt |B|$ のとき， $|B|$ は $|A|$ より大きいといいます．（「以下」，「より小さい」も同様）

ここで， $A$ と $B'(\subset B)$ が対等であることは， $A$ から $B$ への単射があることや， $B$ から $A$ への全射があることと同値となります．

命題

任意の 2 つの集合 $A,B$ に対して， $$|A|\lt |B|,\ \ |A|=|B|,\ \ |A|\gt |B|$$ のいずれか 1 つのみが必ず成り立つ．

証明

2 つ以上の関係が同時に成り立たないことは $\lt$ の定義と下のBernsteinの定理から容易にわかる．
必ずいずれかの関係が成り立つことは（順序集合の知識が必要なので）証明略．

また，次の定理より， $|A|\leq |B|$ かつ $|B|\leq |A|$ ならば， $|A|=|B|$ が成り立ちます．

Bernsteinの定理

$A$ から $B$ への単射と， $B$ から $A$ への単射が存在すれば， $A$ から $B$ への全単射が存在する．

ここまでの議論から次の関係がもとまります．このような関係を順序関係といいます．

$|A|\leq|A|$ （恒等写像は単射なので）
$|A|\leq|B|,|B|\leq|A|\Longrightarrow |A|=|B|$ （Bernsteinの定理より）
$|A|\leq|B|,|B|\leq|C|\Longrightarrow |A|\leq|C|$ （単射の合成写像は単射より）

では，濃度の大小を用いた例として，次の驚くべき命題を証明します．

命題

(1) 自然数全体の集合 $\mathbb{N}$ は，有理数全体の集合 $\mathbb{Q}$ と対等．
(2) 自然数全体の集合 $\mathbb{N}$ と，実数全体の集合 $\mathbb{R}$ とは対等ではなく， $|\mathbb{N}| \lt |\mathbb{R}|$ ．したがって， $|\mathbb{Q}| \lt |\mathbb{R}|$

証明

(1)
$\mathbb{N} \subset \mathbb{Q}$ なので， $|\mathbb{N}| \leq |\mathbb{Q}|$ ．
また，次の図のように $\mathbb{N}$ を $y$ 座標が 0 以上の格子点に対応させると，この対応は $\mathbb{N}$ から $\mathbb{Z}\times (\mathbb{N}\cup \{0\})$ への全射であり， $\mathbb{Q}$ の任意の点は $a\in \mathbb{Z}$ と $b\in (\mathbb{N}\cup \{0\})$ によって， $\frac{a}{b}$ とかけるので（ $\frac{a}{0}=0$ としておく），この対応は $\mathbb{N}$ から $\mathbb{Q}$ への全射となっている．よって， $|\mathbb{N}| \geq |\mathbb{Q}|$ であって，したがって， $|\mathbb{N}| = |\mathbb{Q}|$ ．

(2)
まず， $f(x)=tan（\pi x+{\pi\over2}）$ が開区間 $(0,1)$ から $\mathbb{R}$ への全単射となることから，開区間 $(0,1)$ は $\mathbb{R}$ と対等なので， $(0,1)$ と $\mathbb{N}$ の関係を調べれば良い．
もし， $\mathbb{N}$ と $(0,1)$ との間に全単射があれば， $$f(1)=0.a_1^{(1)}a_2^{(1)}\dots a_n^{(1)}\dots$$ $$f(2)=0.a_1^{(2)}a_2^{(2)}\dots a_n^{(2)}\dots$$ $$\vdots$$ $$f(n)=0.a_1^{(n)}a_2^{(n)}\dots a_n^{(n)}\dots$$ $$\vdots$$ と，対応させられる．しかし， $b_n$ を $$b_n= \left\{ \begin{array}{cccc} 1\quad (a_n^{(n)} \neq 1)\\ 2\quad (a_n^{(n)} = 1) \end{array} \right. $$ と定めると， $\beta = 0.b_1b_2\dots b_n\dots$ は $\mathbb{N}$ と対応していない $(0,1)$ の元となっている．したがって， $\mathbb{N}$ から $(0,1)$ への全単射は存在しない．よって，対等でない．
ここで， $\mathbb{N} \subset \mathbb{R}$ より， $|\mathbb{Q}|=|\mathbb{N}| \leq |\mathbb{R}| = |(0,1)|$ であり， $\mathbb{N}$ と $(0,1)$ は対等でないので， $|\mathbb{Q}| \lt |\mathbb{R}|$ .

上の証明により， $\mathbb{Q}$ は $\mathbb{N}$ と同じ数だけ存在していて， $\mathbb{R}$ は $\mathbb{Q}$ よりも多く存在する．といえるでしょう．

また，上の証明により，任意の写像 $f:\mathbb{Q}\longrightarrow\mathbb{R}$ に対して，$\mathbb{R}’=\mathbb{R}-f(\mathbb{Q})\neq\emptyset$ となりますが，このとき， $|\mathbb{R}’|$ の濃度はどのようになっているのでしょう？

実は $|\mathbb{R}’|$ に関して次の命題が成り立ちます．

命題

任意の写像 $f:\mathbb{Q}\longrightarrow\mathbb{R}$ に対して，$\mathbb{R}’=\mathbb{R}-f(\mathbb{Q})$ は $|\mathbb{Q}|\lt |\mathbb{R}’|$ となる．

証明

$|\mathbb{N}|=|\mathbb{Q}|$ より，任意の写像 $f:\mathbb{N}\longrightarrow\mathbb{R}$ に対して，$\mathbb{R}’=\mathbb{R}-f(\mathbb{N})$ が $|\mathbb{N}|\lt |\mathbb{R}’|$ となることを示せば良い．
$|\mathbb{N}|\geq |\mathbb{R}’|$ と仮定して矛盾を導く． $|\mathbb{N}|\geq |\mathbb{R}’|$ ならば， $|\mathbb{N}|$ は後に示すように濃度が最小の無限集合であるので， $\mathbb{R}’$ は有限集合か $\mathbb{N}$ と対等な集合となる．

任意の写像 $f:\mathbb{N}\longrightarrow\mathbb{R}$ を 1 つとると， $$f(1)=x_1,\ f(2)=x_2,…,\ f(n)=x_n,…$$ とかける．

このとき， $\mathbb{R}’$ が有限集合ならば， $$ \mathbb{R}’ =\{a_1,a_2,…,a_m\}$$ とかけて，写像 $g:\mathbb{N}\longrightarrow\mathbb{R}$ を $$g(1)=a_1,\ g(2)=a_2,…,\ g(m)=a_m,\\ g(m+1)=x_1,…,\ g(m+n)=x_n,…$$ と定義すると，この写像は全射となり $|\mathbb{N}| \lt |\mathbb{R}|$ と矛盾する．

$\mathbb{R}’$ が $\mathbb{N}$ と対等ならば， $$ \mathbb{R}’ =\{a_1,a_2,…,a_n,…\}$$ とかけて，写像 $h:\mathbb{N}\longrightarrow\mathbb{R}$ を $$h(1)=a_1,\ h(3)=a_2,…,\ h(2n-1)=a_n,…\\ h(2)=x_1,\ h(4)=x_2,…,\ h(\ \ \ 2n\ \ \ )=x_n,…$$ と定義すると，この写像は全射となり $|\mathbb{N}| \lt |\mathbb{R}|$ と矛盾する．

したがって， $|\mathbb{N}|\lt |\mathbb{R}’|$ であるので， $|\mathbb{Q}|\lt |\mathbb{R}’|$ ．

この命題より，写像 $f:\mathbb{Q}\longrightarrow\mathbb{R}$ を $f(a)=a$ とおくと，無理数は有理数よりも多く存在する．ということができます．

濃度が最小の無限集合

$\mathbb{Z}$ や $\mathbb{Q}$ など $\mathbb{N}$ と対等な集合を可算集合といい，可算集合の濃度を $\aleph_0$ （アレフ・ゼロ）とかきます．

$\mathbb{R}$ などの $\mathbb{N}$ より濃度の大きい集合を非可算集合といいます．特に， $\mathbb{R}$ の濃度を連続濃度といい $\aleph$ （アレフ）とかきます．

$\aleph_0$ が無限集合の濃度で最小となることは次の定理によりわかります．

定理

任意の無限集合は，可算集合を部分集合に含む．

証明

$M$ を与えられた無限集合とする．まず， $M$ の任意の元 $a_1$ をとる．続けて， $M-\{a_1\}$ 任意の元 $a_2$ をとり， $M-\{a_1,a_2\}$ 任意の元 $a_3$ をとる．同様にして，任意の $n$ に対して， $n$ 個の元をとったとき， $M$ は無限に多くの元を持つので， $M\neq \{a_1,a_2,\dots ,a_n\}$ である．したがって， $M- \{a_1,a_2,\dots ,a_n\}\neq \emptyset$ なので，この集合からまた任意の元 $a_{n+1}$ が取れる．よって， $M$ から取り出した $\{a_1,a_2,\dots ,a_n,\dots\}$ は $M$ の可算な部分集合となっている．

注）この証明で，集合 $X_i＝M- \{a_1,a_2,\dots ,a_i\}$ から元を 1 つ選ぶ操作は選択公理によって保証されている．つまり， $f_i(X_i)\in X_i$ となる $f_i$ が存在することが選択公理により保証されているので， $a_{i+1}=f_i(X_i)$ とおけば良い．

濃度が最大の集合

次の定理から最大の濃度を持つ集合は存在しないことがわかります．

定理

任意の無限集合 $X$ の部分集合全体の集合 $\mathfrak{P}(X)$ の濃度は $X$ の濃度よりも大きい．

証明

$f$ を $X$ から $\mathfrak{P}(X)$ への写像とする．このとき， $X$ の各元 $x$ に対して， $f(x)$ は $X$ の部分集合となる．したがって， $x\in X$ に対して， $x\in f(x)$ か $x\notin f(x)$ のいずれかが成り立つ．今，次のような $X$ の部分集合 $B$ を考える． $$B=\{x\in X\ |\ x\notin f(x)\}$$ このとき， $x\in f(x)$ ならば $x\notin B$ であり， $x\notin f(x)$ ならば $x\in B$ である．
したがって，任意の $x\in X$ に対して $f(x)\neq B$ となる．これは， $X$ の部分集合 $B$ に対応する $X$ の元が存在しないということなので， $f$ は全単射でない．

この定理から，いくらでも大きな濃度の集合を作れることがわかります．例えば， $\mathfrak{P}(\mathfrak{P}(X))$ は $\mathfrak{P}(X)$ より大きな濃度の集合です．

連続体仮説

可算集合の濃度より大きく連続濃度より小さい濃度があるか，つまり

$$\aleph_0 \lt |X| \lt \aleph$$

となる集合 $X$ は存在するかということについて述べておきます．

このような $X$ は存在しないという仮説を連続体仮説といい，現在一般的に用いられている集合論の公理系であるZFC公理系の元で連続体仮説は証明できないことが分かっています．

このことがZFC公理系の不完全性を示している．とも言われています．

無限集合に関する事実

最後に，無限集合について成り立つ事実を一通り載せておきます．

無限集合に関する事実

・ $|\{2,4,…,2k,…\}|=|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|=|\mathbb{N}^a|$（ $2\leq a\lt \infty,\ a\in \mathbb{N}$）

・ $|\mathbb{R}|=|\mathbb{C}|=|\mathbb{N}^{\mathbb{N}}|=|\mathfrak{P}(\mathbb{N})|=|\mathbb{R}^a|$（ $2\leq a\leq \infty,\ a\in \mathbb{N}$）

・ $\mathbb{R}$ から $\mathbb{R}$ への連続関数全体の集合を $C(\mathbb{R})$ とかくと， $|C(\mathbb{R})|=|\mathbb{R}|$ ．

・ $X$ が無限集合で $|A|\lt |X|$ のとき， $|X-A|=|X\cup A|=|X\times A|=|X|$ ．

Please Share