こんにちは！ケンけんです。前回は、全単射を崩した単射と全射を取り扱いました。今回はいよいよ数える話を大元「集合の等濃性」とその「可算性」を取り上げます。
キーワード：集合の濃度・可算性
導入
これまで私たちは、元を数えられない場合を見て集合を一般化しようと言う流れで命題論理と集合を決めて解決してきました。そうすると、次のような疑問が出るのではないでしょうか。
$$「数えられない」はどうやって説明するのだろう。$$
こんな場合は、数えられるものを考えればいいのです。具体的には自然数全体の集合を見ます。
中学校1年での数学で整数や有理数といった数系の枠組みの中で最も小さく加法以外閉じない集合です。そして、そんな自然数は算数でのケースでよく説明されます。では問題ですが、
$$「リンゴ2個」と「自然数2」の2は同じ？$$
同じと思っていませんか？実は同じ$2$でも全然違う情報です。リンゴはモノであり個数と言う量を表しています。対して自然数$2$は「$\{\emptyset, \{\emptyset , \{\emptyset\}\}\}$」と言う集合が実際の姿です。はぁ？と思ったことでしょう。実は自然数は、空集合を持つ集合を含むように作られます。そして、これがモノの個数に調度一対一対応するようにできるから$2$と表していたのです。（自然数の構成はいずれ記事にします。）
- モノの数：個数と言う量
- 自然数：空集合による集合
空集合を積み重ねることから絶対に自然数はいつもの数える行為ができます。そうなると、モノと自然数を一対一対応させることでモノの個数は自然数と対応することで説明されます。つまりリンゴの個数は、自然数によってラベル付けされて得られると言えます。
図：リンゴと自然数の対応
そうすれば、リンゴの集合と自然数の部分集合（上の図では$\{1, 2, 3\}$）と集合として同型になるように取れる。そうすると、リンゴの総数は$3$個だと言えます。
算数の掛ける数・掛けられる数を重視するのは、数を整数や自然数とはみなさず個数と言う情報を見ているからです。数学的には正しくても算数的に間違いとなるのはこんなところにも理由があるんです。
つまり、数えられる集合は、「自然数全体の集合と集合として同型」であることによって「数えられる」と決めてもよいと言えそうです。これが数えられる集合の性質「可算」を示しています。
つまり、命題の否定「自然数全体の集合と集合として同型ではない」ことで、これまでよくわからなかった数えられない元を持つ集合を定義できると言えます。
こう言った理由を見ると、一対一対応（全単射）は数えられることだけでなく数えられないものも指定する物差しとして優秀だとわかるでしょう。
そして、無限の集合も可算か否かでさが表れることもわかります。
大まかに次の3つのタイプが考えられます。
- 有限集合（自然数の部分集合と対応するため可算な集合）
- 自然数と集合として同型な無限集合
- 自然数と集合として同型ではない無限集合
下に行くほど無限で添え字部分を自然数が使えないと不便になっていきます。そうなると、同じ無限集合でも元の数として自然数と対応させられない元を持つ3つ目はとても元の数？が大きいと言えるでしょう。
この無限の大小も含めた元の数の情報として集合の「濃度」が現れます。しかし、濃度自体はかなり他に準備が必要なので現段階では説明できません。そこで、全単射のみで説明できる元の数らしきものが一致するかどうかをを定義します。
定義
それでは、等濃と可算についてしっかり定義しましょう。
$U$：普遍集合 $X,Y \subset U$
$X$と$T$は等濃（$\rm{equipotent}$）である $\overset{def}{\iff} \exists f:X \rightarrow Y(f:全単射)$.
$X \sim Y$と書く.
等濃でない場合, $X \nsim Y$と書く.
$X$は可算集合（$\rm{countable}$）である.$\overset{def}{\iff} X \sim \mathbb{N}$.
$X$は有限集合（$\rm{finite \; set}$）である. $\overset{def}{\iff} \exists n \in \mathbb{N} s.t. X \sim \{1,2, \ldots , n\} $.
$X$は高々可算である $\overset{def}{\iff}(X:有限集合) \vee (X:可算集合)$.
ずっと数えられる数えられないと言葉で話してきましたがようやく可算・非可算と説明できるようになりかなり説明が楽になりますね。
等濃の記号で使った「$\sim$」は、同値関係の時に見ました。もう気付いているでしょうが、これは同値関係です。
普遍集合$U$のべき集合上で2つの集合が等濃である関係「$\sim$」は同値関係である.
詳しく書くと,
$U$：普遍集合 $X,Y,Z \subset U$
- $X \sim X$
- $X \sim Y \Rightarrow Y \sim X$
- $(X \sim Y) \wedge (Y \sim Z) \Rightarrow X \sim Z$
この証明は、実は全単射を持つ関係が同値関係だと以前示したのですぐに従います。
ちなみに、同値関係は集合の元に対して決まるため普遍集合$U$の部分集合をべき集合の元とみなす必要があります。この制限をしない場合は、「集合の集合は集合にならない」によって集合の元とみなせなくなり同値関係とは言えなくなります。
実際の可算・非可算集合を見る
では、可算集合・非可算集合を調べやすいものから見ていきます。
１．可算集合の例
自然数全体の集合$\mathbb{N}$は可算であることは、同値関係から明らかです。では、他の可算集合と言うと整数全体の集合$\mathbb{Z}$や有理数全体の集合$\mathbb{Q}$がそうです。
$\mathbb{Z}$について$f:\mathbb{N} \rightarrow \mathbb{Z}(n \mapsto (-1)^{n}[\frac{n}{2}])$を定義するとこれが全単射になっています。
単射性は、$(-1)^{m}[\frac{m}{2}]=(-1)^{n}[\frac{n}{2}]$について$[\frac{m}{2}]=[\frac{n}{2}]$から$m-n=1$、$(-1)^{m}=(-1)^{n}$から符号が一致するためには$m=n$である。（$f(m)=f(n) \Rightarrow m=n$）
全射性は、整数の符号によって対応させる自然数の偶奇が定まります。次に整数の絶対値$m$を考えると、$\frac{n}{2} \leq [\frac{n}{2}] < \frac{n}{2}+1$から$n \leq 2m <n+2$となります。以上から、符号が正の場合は$n=2m$、負の場合は$n=2m+1$とすることで定義されます。以上から、$f(n)=m$です。
有理数については少し準備が必要なのでところどころ略しながら挙げます。$f:\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}((m,n) \mapsto \frac{(m+n-2)(m+n-1)}{2}+n)$と言う写像を構成します。これが、全単射より$\mathbb{N} \times \mathbb{N} \sim \mathbb{N}$であることがわかります。
すると、$\mathbb{N} \times \mathbb{N} \sim \mathbb{N} \sim \mathbb{Z}$となります。
（ここは、$X \sim X’, Y \sim Y’ \Rightarrow X \times Y \sim X’ \times Y’$を利用しています。※要証明）
そして、$M=\{(1,0)\} \cup \{(m,n) \in \mathbb{N} \times \mathbb{Z}|n \neq 0, mとnは整数として互いに素\}$とする$\mathbb{N} \times \mathbb{Z}$の部分集合を取ります。
そうすると、$f:\mathbb{N} \times \mathbb{Z} \rightarrow \mathbb{Q}((m,n) \mapsto \frac{n}{m})$を定義します。これは、$0$か既約分数$\frac{n}{m}$を像として持っています。そうするとこれが、全単射になるので$M \sim \mathbb{Q}$となります。ここで、「可算集合の無限部分集合は可算」である命題（※要証明）から$M$が可算であると言えて$\mathbb{Q}$も可算であるとなります。
以上から、$\mathbb{Z},\mathbb{Q}$は可算集合だとわかります。
２．非可算集合の例
これはもう何度も例で出てきているのでわかると思います。$\mathbb{R}$や区間$[0,1],(2,6)$などです。これの証明は、それだけで一本記事になるほど重いので別の機会に回します。今回は、実数や区間の元すべてを自然数で添え字づけられないんだなと理解すれば十分です。
おわりに
ようやく数えられる・数えられないを定義でき、目標の定理が見えてきました。今回、可算についていろいろな命題を説明の都合上カットしました。おそらく、全単射や等濃・非可算集合（$\mathbb{R}$）の話の記事を挟むことになります。
次回は、目標である「ベルンシュタインの定理」を取り扱います。
以上、ケンけんでした。
