集合の濃度まとめ - 数学をする

はじめに

この記事の目標は，

「 $\mathbb{R}$ 上実数値連続関数全体の集合の濃度は， $\mathbb{R}$ の濃度と等しい」

を示すことです．
この主張を示すには，集合の濃度に関する基礎的な主張をある程度網羅する必要があり，理解の目安になるのではないかと思います．

ただし， $\mathbb{R}$ 上実数値連続関数が有理数での値によって決まることは，濃度の話から反れるので既知とします．

はじめに
証明の流れ
- 命題1
- 命題2
命題1の証明
命題2の証明
- 補題1
- 補題2
- 命題2
証明

証明の流れ

$\mathbb{R}$ 上実数値連続関数全体の集合を $X$ とします．
$X$ の元は，有理数においてとる値によって決まるので，
\[|X|=|\mathrm{Hom}(\mathbb{Q},\mathbb{R})|\]となります．
ここでキーとなる命題が2つあります．

命題1

\[|\mathrm{Hom}(A\times B,C)|=|\mathrm{Hom}(A,\mathrm{Hom}(B,C))|\]

命題2

\[|P(\mathbb{N})|=|\mathbb{R}|\]

命題1は簡単に示せます．命題2を示すには少し準備が必要です．
以下で順に述べていきます．

命題1の証明

証明

$f\in\mathrm{Hom}(A\times B,C)$ に「各 $a\in A$ に $f(a,\cdot\,)\in \mathrm{Hom}(B,C)$ を対応させる写像」を対応させる写像を $\phi\colon\mathrm{Hom}(A\times B,C)\to\mathrm{Hom}(A,\mathrm{Hom}(B,C))$ とします．
また， $g\in \mathrm{Hom}(A,\mathrm{Hom}(B,C))$ に「各 $(a,b)\in A\times B$ に $g(a)(b)\in C$ を対応させる写像」を対応させる写像を $\psi\colon\mathrm{Hom}(A,\mathrm{Hom}(B,C))\to\mathrm{Hom}(A\times B,C)$ とします．

このとき，
\begin{align}
&\psi(\phi(f))(a,b)=\phi(f)(a)(b)=f(a,b)\\
&\phi(\psi(g))(a)(b)=\psi(g)(a,b)=g(a)(b)
\end{align}となるので， $\phi,\psi$ は全単射であり，命題が示せました． $\Box$

ちなみに，集合 $A$ から集合 $B$ への写像全体の集合を $B^A$ と表せば，命題1は
\begin{align}
\vert C^{A\times B} | = | (C^B)^A |
\end{align}となり，集合の濃度について指数法則が成り立つことを主張しています．

命題2の証明

命題2を示すには補題2が必要であり，補題2を示すには補題1が必要です．

補題1

任意の無限集合 $A$ は，可算な部分集合をもつ．

証明

$A$ の有限部分集合全体の集合を $F$ とします． $A$ は無限集合なので，任意の $B\in F$ に対して $\overline{B}\neq \varnothing$ です．
よって，選択公理により，選択関数 $\displaystyle f\colon F\to \bigcup_{B\in F}\overline{B}$ をとることができます．
$a_0=f(\varnothing), a_1=f(\{a_0\}),a_2=f(\{a_0,a_1\}),\dots$ とおけば， $a_n$ は $\{a_0,\dots ,a_{n-1}\}$ に含まれないので， $\{a_n\}$ に重複はなく，可算集合となります． $\Box$

無作為に無限個の元をとらないといけないので，選択公理は回避できないように思います．

補題2

任意の無限集合 $A$ に対して，
\begin{align}
\vert A| + |\mathbb{N}| = |A|.
\end{align}

証明

$A$ が可算なときは簡単に全単射が作れます．
$A$ が可算でないときは，まず補題2を用いて $A$ の可算な部分集合 $B$ をとると， $|B|+|\mathbb{N}|=|B|$ となります．
よって， $|A|+|\mathbb{N}|=|A\cup\mathbb{N}|=|(A\setminus B)\cup(B\cup\mathbb{N})|=|(A\setminus B)\cup B|=|A|$ となり，主張が示せました． $\Box$

それでは命題2の証明に入ります．

命題2

\[|P(\mathbb{N})|=|\mathbb{R}|\]

証明

基本的には， $\mathbb{R}$ と $(1,2]$ の濃度が等しいことを利用して，実数の2進数展開を用います．
$P(\mathbb{N})$ を，有限部分集合の全体 $P_1$ ，補集合が有限集合である部分集合の全体 $P_2$ ，それ以外の部分集合の全体 $P_3$ に分けます． $(1,2]$ の2進数展開と対応するのは $P_2\cup P_3$ です．

$P_1$ の濃度は，要素の個数を基準にして考えると， $S=\mathbb{N}\cup(\mathbb{N}\times\mathbb{N})\cup(\mathbb{N}\times\mathbb{N}\times\mathbb{N})\cup\cdots$ の濃度と等しくなります．
そして，この集合は， $(a_1,a_2,\dots,a_n)\in S$ の各成分の和を基準にして並べることで， $\mathbb{N}$ との全単射を作ることができます．
したがって， $|P_1|=|\mathbb{N}|$ です．

よって，補題2から $|P(\mathbb{N})|=|(P_1\cup P_2)\cup P_3|=|P_2\cup P_3|=|\mathbb{R}|$ となります． $\Box$

証明

この記事の目標である，

「 $\mathbb{R}$ 上実数値連続関数全体の集合の濃度は， $\mathbb{R}$ の濃度と等しい」

を示しましょう．命題1，2を用いれば簡単に証明できます．

証明

\begin{align}
\vert X|&=|\mathrm{Hom}(\mathbb{Q},\mathbb{R})|\\
&=|\mathrm{Hom}(\mathbb{Q},P(\mathbb{N}))|&\\
&=|\mathrm{Hom}(\mathbb{Q},\mathrm{Hom}(\mathbb{N},\{0,1\}))|\\
&=|\mathrm{Hom}(\mathbb{Q}\times\mathbb{N},\{0,1\})|\\
&=|\mathrm{Hom}(\mathbb{N},\{0,1\})|=|\mathbb{R}|
\end{align}