集合論③ カントールの対角線論法
カントールの対角線論法とは?
ここでは実数の集合$\mathbb{R}$が可算集合でないことを示します。背理法をもちいますが、今回紹介する方法が対角線論法と呼ばれています。前提:可算集合や濃度の定義など
定義以外にも細かい説明は前回記事におおざっぱにのせてあるので、細かいことは前回記事をご覧ください。(参考:集合の濃度とベルンシュタインの定理(+可算集合))可算集合とは?
可算集合
自然数と濃度が等しい集合を可算集合といいます。
集合の濃度とは?
集合の濃度
\begin{align*}
「集合AとBの濃度が等しい」&\stackrel{\mathrm{def}}{\Leftrightarrow}AとBの間に全単射が存在する\\
「集合Aの濃度はBの濃度以下」&\stackrel{\mathrm{def}}{\Leftrightarrow}AからBへの単射は存在する
\end{align*}
可算集合の無限部分集合は可算集合
可算集合の中で無限部分集合を考えると、その無限部分集合も可算集合になります。もちろん、これは証明すべきことなのですが、一旦事実として話を進めます。
対角線論法による証明
対角線論法を用いて、実数が非可算濃度をもつことを証明します。背理法を用いる
実数の集合$\mathbb{R}$が可算集合と仮定します。この仮定の下では、$\mathbb{R}$の無限部分集合$[0,1]$も可算集合になります。可算集合の定義から、$\mathbb{R}$と$\mathbb{N}$の間には1対1の対応(全単射)が存在することになります。
対応関係を考える
つまり、写像$f$:$\mathbb{N}$$\mapsto$$[0,1]$を考えて、\begin{align*}
f(1)&=0.a_{11}a_{12}a_{13}\cdots \\
f(2)&=0.a_{21}a_{22}a_{23}\cdots \\
&\vdots \\
f(k)&=0.a_{k1}a_{k2}a_{k3}\cdots \\
&\vdots
\end{align*}
という対応関係を1対1で考えることができます。ただ、新しい数$b_n$を$a_{nn}$が奇数なら2として、$a_{nn}$が偶数なら1として定義し、以下のような数を作ります。
\begin{align*}
0.b_1b_2b_3\cdots b_n \cdots
\end{align*}
これはどの$f(n)$とも異なる数になります。というわけで、全単射ということに矛盾します。よって、$\mathbb{R}$が可算集合ということに矛盾します。よって、$\mathbb{R}$は非可算です。