集合の濃度について - バージョン管理された人

2つの有限集合 $A$ と $B$ が同じ数の元を持つとは、 $A$ に含まれる元の個数と $B$ に含まれる元の個数を数えればわかる。
また、有限集合 $A$ が有限集合 $B$ 以上の元を持つことは、集合の元の個数を $|A|$ と表すことで $|A| \leq |B|$ と表すことができるし、 $|A| \lt |B|$ は有限集合 $B$ が有限集合 $A$ よりも元を多くもっていると言える。
この関係は集合の要素の個数を一般化したときにどうなるのだろうか？
また、どのようにこの個数の一般化はなしとげられるのだろうか？

今回はここについて記しておく。

準備

まず、集合の元の個数の一般化にあたって必要な全単射と逆関数、それに合成関数について記す。

集合 $A$ から $B$ への関数 $f: A \to B$ が全単射であるとは、一言で言えば、 $f$ が $A$ と $B$ の要素を一対一で対応付けているということを意味している。
厳密に言えば、関数 $f: A \to B$ が

全射性: $\forall b \in B, \exists a \in A; b = f(a)$
単射性: $\forall a_1, a_2 \in A; f(a_1) = f(a_2) \implies a_1 = a_2$

を満たすことをいう。
$f: A \to B$ が全射であるとは、どの $b \in B$ に対しても、必ず対応する $a$ があることを言っている。
すなわち、写される先 $B$ のどの元も、関数 $f: A \to B$ によって写されるもとが存在することを意味している。
また、 $f: A \to B$ が単射であるとは、どの $a_1, a_2 \in A$ に対しても、必ず、写された先が等しい( $f(a_1) = f(a_1)$ )ならば、 $a_1 = a_2$ でなければならないことを意味している。
これは、関数 $f: A \to B$ によって写される先は重ならないということを意味する。
以上から、全単射はどの写される先の元も写されるもとが存在し、しかも写された先は重ならないという良い性質を持っている。

全射な関数 $f$ によって写される先の集合には $f$ によって写されないものはないし、写されるものには写されるもとがある。ただし、写す元には写されないものがあってもよいし、写されるもとは複数あってよい

単射な関数 $f$ は写すもとの集合の要素を全て重複なく写すが、写される先の集合には、写されないものがあってもよい

全単射な関数 $f$ は写すもとの集合の要素を全て重複なく写し、また写される先の集合には写されないものは存在しない

この全単射な関数 $f: A \to B$ の写す先 $b = f(a) \in B$ と写されるもと $a \in A$ を対応づける関数 $f^{-1}(b) =a$ を逆関数という。
この関数が $f^{-1}(f(a)) = a, f(f^{-1}(b)) = b$ という性質を持つことは明らかであると思う。

また、関数 $f: A \to B$ で写したものを $g: B \to C$ で写すということが考えられる。
これによって、 $A$ の元は $C$ へ写されることとなる。
つまり、 $g(f(x))$ というものが考える。
これは関数の合成と呼ばれ、合成された関数を合成関数と呼び、 $g \circ f(x)$ と表される。
実は、 $f: A \to B$ と $B \to C$ が全単射ならば、合成関数 $g \circ f: A \to C$ は全単射となることが知られている。

以上の定義をもちいて、濃度について調べていく。

濃度

先程の全単射な関数を考えることで、集合が同じだけの元を持つということを定義できる。
全単射な関数が1つでもあれば、集合同士は過不足なく、しかも重複もなく元を対応づけることができる。
これによって、集合どうしが同じだけの元を持つということが言える。
つまり、 $A$ と $B$ に全単射な関数が少なくとも1つでもあれば、 $A$ と $B$ は対等であるという。
対等であることは記号 $\sim$ を使って、 $A \sim B$ と表される。
この関係には次の性質が存在することは簡単に確認できる。

$A \sim A$
$A \sim B \implies B \sim A$
$A \sim B \land B \sim C \implies A \sim C$

簡単に言えば:

$A \sim A$ : $f(x) = x$ という関数を考えると、これは全単射
$A \sim B \implies B \sim A$ : $A$ から $B$ へは全単射な関数が少なくとも1つ存在するので、その逆関数を考える
$A \sim B \land B \sim C \implies A \sim C$ : $A$ から $B$ へ全単射な関数 $A \to B$ が存在し、 $B$ から $C$ への全単射な関数 $g: B \to C$ が存在するので、その合成関数 $g \circ f$ は全単射となる

ということになる。

この関係によって、集合は対等なものと対等でないものにわけることができる。
つまり、集合 $A, B$ が $A \sim B$ であって、さらに集合 $D$ が $B \sim D$ であれば、 $A \sim D$ になるし、集合 $E$ と $F$ が対等でなければ、それは同じだけの要素を持っていないので別のものであるとみなせる。
これをさまざまな集合に対して行えば、対等なものどうしのグループにわけることができる。

分類したグループに対して、

同じグループの集合には同じしるしをつける
異なるグループの集合には異なるしるしをつける

という規則のもと付けたしるしのことを濃度といい、Aの濃度は $|A|$ と書かれる。
$A$ と $B$ が同じグループに入る、つまり、 $A \sim B$ ならば $|A| = |B|$ であるし、逆に $|A| = |B|$ であれば、同じグループに入っているので、 $A \sim B$ となる。
しるしとしては、例えば $A = \{1, \cdots, n\}$ 、つまり $A$ が $n$ 個の元を持つ元であれば $|A| = n$ というしるしをつければよい。

可算集合

有限集合にはしるしとして自然数を割り当てた。
しかし、自然数全体の集合 $\mathbb{N}$ や実数全体の集合 $\mathbb{R}$ などの要素が無限にある集合の濃度には自然数というしるしをつけることはできない。

一般に $\mathbb{N}$ の濃度には $\aleph_0$ という記号がわりあてられる。
$\aleph_0$ は"アレフゼロ"と読む。
つまり、 $\aleph_0$ の濃度を持つ集合は $\mathbb{N}$ と対等だし、 $\mathbb{N}$ と対等な集合の濃度は $\aleph_0$ となる。

この $\mathbb{N}$ と対等な集合のことを可算集合あるいは可付番集合という。
なお、有限集合と可算集合を、合わせて高々可算な集合という

可付番な集合としては

整数全体の集合 $\mathbb{Z}$
有理数全体の集合 $\mathbb{Q}$
整数係数のみをもつ代数方程式 $a_n x^n + a_{n - 1} + x^{n - 1} + \cdots a_1 + x + a_0 = 0 \enspace (a_i \in \mathbb{Z})$ の解となる数(これを代数的数という)の集合

がある。

$\mathbb{Z}$ : $0, -1, 1, -2, 2, \cdots$ と並べて前から順々に自然数を割り当てていく
$\mathbb{Q}$ : まず、正の有理数だけを考え、下図の矢印の順番に自然数を割り当てればよい。従って、正の有理数全体の集合と自然数全体の集合は対等となる。あとは負の有理数と正の有理数を、整数と同じように自然数を割り振り直す
代数的数の集合: $a_0 > 0$ と仮定しても一般性を失しなわないので $a_0 > 0$ とする。一般に方程式 $a_n x^n + a_{n - 1} + x^{n - 1} + \cdots a_1 + x + a_0 = 0$ において、 $n + a_0 + |a_1| + |a_2| + \cdots |a_n|$ なる自然数をその方程式の高さという。高さはあきらかに2以上であるし、高さが同じ方程式の数は有限個となる。なぜならば、高さ $h$ を1つ決めれば、 $n < h, a_0 < h, |a_1| < h, \cdots, |a_n| < h$ とならなければならないからである。さらに、方程式の解の個数は最大でも $n$ なので、代数的数も有限個しかないことがわかる。

意外なことに、 $\mathbb{N}$ と $\mathbb{Z}$ 、 $\mathbb{N}$ と $\mathbb{Q}$ の濃度は同じとなる。

また、可算集合 $A$ の無限部分集合 $B \subseteq A$ は可算となる。
これは $A$ の中から、 $B$ にはいっていないものを除いて、残ったものに小さい順に自然数を割り当てればよいことからわかる。

さらに、高々可算な集合の和集合もまた高々可算な集合となる。

$A$ も $B$ も有限集合とするこのとき、あきらかに $A \cup B$ も有限個しか元を持たない
$A$ か $B$ のどちらか一方が有限集合で、もう一方が可算集合とする。なお、ここでは $A$ を有限集合、すなわち $A = \{a_1, a_2, \cdots, a_n\}$ 、他方、 $B$ を可算集合、すなわち $B = \{b_1, b_2, \cdots\}$ とする。 $A \cup B$ の元を $a_1, a_2, \cdots, a_n, b_1, b_2, \cdots$ と並べて、前から自然数を割り当てればよい
$A$ もl $B$ も可算集合とする。すなわち、 $A = \{a_1, a_2, \cdots\}, B = \{b_1, b_2, \cdots\}$ とする。このとき、 $a_1, b_1, a_2, b_2, \cdots$ というように並べて、前から自然数を割り当てればよい

どの場合も重なるものは飛ばして考えればよい。

非可算集合

$\mathbb{N}$ や $\mathbb{Q}$ は同じ濃度であったが、実数全体の集合 $\mathbb{R}$ の濃度は同じとなるのだろうか？
実は同じとはならないことがカントールによって証明されている。
この $\mathbb{R}$ の濃度は $\aleph_1$ と書かれるが、これが $\aleph_0$ と等しくないことを簡単に証明してみる。
それには、 $\mathbb{R}$ の部分集合に可算でないものがあることを証明すればよい。
そこで、 $(0, 1] = \{x : 0 \lt x \leq 1\}$ が可算でないこと示す。

まず、 $(0, 1]$ が可算であると仮定する。
$(0, 1]$ の元 $x$ は $0$ から $9$ までの自然数を用いて、 $x = 0.a_1 a_2 \cdots a_n \cdots$ と表せるので、

$\begin{array}{c} a_1 = 0.a_{1 1} a_{1 2} a_{1 3} \cdots a_{1 n} \cdots \\ a_2 = 0.a_{2 1} a_{2 2} a_{2 3} \cdots a_{2 n} \cdots \\ a_3 = 0.a_{3 1} a_{3 2} a_{3 3} \cdots a_{3 n} \cdots \\ \vdots \\ a_n = 0.a_{n 1} a_{n 2} a_{n 3} \cdots a_{n n} \cdots \\ \vdots \end{array}$

とならべる。
このうち、 $a_{i i}$ の部分に対し、

$b_n = \begin{cases} 1 & \text{if} \enspace (a_{n n} \neq 1) \\ 2 & \text{if} \enspace (a_{n n} = 1) \end{cases}$

として、数 $b = 0.b_1 b_2 \cdots b_n \cdots$ を定義する。
明らかに $0 \lt b \leq 1$ なので、 $b$ はある $a_i$ と等しくなる。しかし、 $b$ の定義からどの $a_i$ に対しても $b$ は等しくない数を $i$ 桁目に含んでいる。
よって、 $b \neq a_i$ 。
しかし、これは矛盾となるので、 $(0, 1]$ は可算集合とはならない。

さらに、 $\mathbb{R}$ から $\mathbb{R}$ への関数全体 $F$ の濃度は $\aleph_0$ でも $\aleph_1$ でもない。
ここではこのことについて考えてみる。

まず、どんな $x \in \mathbb{R}$ に対しても定数 $a \in \mathbb{R}$ を割り当てる関数 $f_a$ を考えると、 $f_a \in F$ 。
このような関数 $f_a$ 全体の集合を $C$ とすれば明らかに任意の $f_a \in C$ は $f_a \in F$ なので、 $C$ は $F$ の部分集合となる。
$f_a$ はある $a \in \mathbb{R}$ に対して定義されており、それが全ての実数に対して定義されているので、 $C$ と $\mathbb{R}$ は一対一対応している。
すなわち、 $C \sim \mathbb{R}$ 。
ここから、 $F$ は高々可算な集合でないことがわかる。
高々可算な集合であれば、その全ての部分集合もまた高々可算となるが、 $C$ は高々可算な集合ではないからである。
次に、 $F$ と $\mathbb{R}$ が対等でないことを示す。
今、 $\mathbb{R}$ から $F$ への全単射の関数 $g$ があると仮定する。
すると、任意の $F$ の元はある $a \in \mathbb{R}$ から $g$ で写されたものとなる。
これを $g_a$ とする。
ここで、任意の $a \in \mathbb{R}$ に対し、 $h(a) = g_a(a) + 1$ を考える。
これは実数を受けとって、実数を返しているので、 $h \in F$ 。
よって、これはある $g_b$ と等しい。
つまり、 $h(x) = g_b(x)$ 。
とくに、 $h(b) = g_b(b)$ 。
しかし、これは $h(b) = g_b(b) + 1$ であることに矛盾。
よって、 $F$ と $\mathbb{R}$ の濃度は等しくない。

以上から、 $F$ の濃度は $\aleph_0$ でも $\aleph_1$ でもない。

濃度の大小

有限集合においては、 $A$ の濃度が $B$ の濃度よりも小さいということは、 $B$ の中に、 $A$ と対等な真部分集合 $B_1 \subset B$ (つまり、 $B \neq B_1$ かつ $B_1$ は $B$ の部分集合)があるといことになる。
このときに限って $|A| < |B|$ が成立することとなる。

しかし、この定義を無限集合にそのまま適用することはできない。
たとえば、 $\mathbb{N} \subset \mathbb{Q}$ ではあるものの、先程示したように $\mathbb{N}$ も $\mathbb{Q}$ も濃度は $\aleph_0$ である。
よってそのままこの定義を無限集合へと延長して利用することはできない。

そこで、濃度 ${\frak a}$ 、及び ${\frak b}$ を持つどんな集合 $A, B$ ( $|A| = {\frak a}, |B| = {\frak b}$ )にたいしても、 $A \sim B_1, B_1 \subseteq B$ なる $B_1$ があれば、 ${\frak a}$ は ${\frak b}$ よりも大きくない、あるいは ${\frak b}$ は ${\frak a}$ よりも小さくないといい、 ${\frak a} \leq {\frak b}$ あるいは ${\frak b} \geq {\frak a}$ と書かれる。
とくに、 ${\frak a} \leq {\frak b}$ かつ ${\frak a} \neq {\frak b}$ のとき、 ${\frak a}$ は ${\frak b}$ よりも小さい、あるいは ${\frak b}$ は ${\frak a}$ よりも大きいといい、 ${\frak a} < {\frak b}$ と書く。

これは有限集合でも無限集合でも濃度を上手く比較することができる。
しかし、これは ${\frak a}$ と ${\frak b}$ を持つ任意の集合について成立しなければ、 ${\frak a} \leq {\frak b}$ が成立しないということには注意しなければならない。

ここで、 $|A| = |C|, |B| = |D|$ とし、 $A \sim B_1, B \subseteq B_1$ なる $B_1$ があるとすれば、 $C \sim D_1, D_1 \subseteq D$ となる $D_1$ が存在する、という性質について言及しておく。
まず、 $B \sim D$ から $B$ から $D$ への一対一対応する $f$ がある。
$B_1$ の元を $f$ によって写した先の全体を $B_1^f$ とすると、 $B_1^f \subseteq D$ で、 $B_1 \sim B_1^f$ 。
この $B_1^f$ を $D_1$ とおくと、 $D_1 \subseteq D$ で、しかも、 $|A| = |C|$ と $A \sim B_1$ から $C \sim A \sim B_1 \sim B_1^f = D_1$ 。
よって、 $C \sim D_1$ 。

また、 ${\frak a} \leq {\frak b}, {\frak b} \leq {\frak c} \implies {\frak a} \leq {\frak c}$ ということが示せる。
まず、 $|A| = {\frak a}, |B| = {\frak b}, |C| = {\frak c}$ となる集合 $A, B, C$ を考える。
${\frak a} \leq {\frak b}, {\frak b} \leq {\frak c}$ から、 $A \sim B_1, B_1 \subseteq B$ かつ $B \sim C_1, C_1 \subseteq C$ となる $B_1, C_1$ がある。
$B$ から $C_1$ への一対一対応を $f$ 、 $B_1$ の元を $f$ で写したもの全体を $B_1^f$ とする。
すると、 $A \sim B_1 \sim B_1^f$ かつ、 $B_1^f \subseteq C_1 \subseteq C$ 。
ゆえに、 $A \sim B_1^f, B_1^f \subseteq C$ 。
これは ${\frak a} \leq {\frak c}$ ということを示してる。

以上から、まとめると、 $\mathbb{R}$ から $\mathbb{R}$ への関数全体の集合の濃度を ${\frak f}$ とすると、
$\aleph_1 \neq \aleph_0, \aleph_1 \neq {\frak f}, \aleph_0 \neq {\frak f}$ であって、

$\mathbb{N}$ は $\mathbb{R}$ の部分集合
$\mathbb{R}$ から $\mathbb{R}$ への関数全体の集合 $F$ 証明の中で利用した、任意の $x \in \mathbb{R}$ をある $a \in \mathbb{R}$ に対応づける関数の集合 $C$ と $\mathbb{R}$ は対等( $\mathbb{R} \sim C, C \subseteq F$ )