インフラSE日記

OSS、仮想化、金融工学、ゲーム、ときどきラーメン

対角線論法について

カントール自然数\mathbb{N}と実数\mathbb{R}との間に全単射がないことを証明するために対角線論法を使ったことはあまりにも有名です。 その他にもチューリングの停止性問題、ゲーデル不完全性定理を証明するために対角線論法を使ったことでも有名ですね。

個人的に昔から対角線論法の証明内容が腹落ちしないというか、納得がいかなかったので自分で納得がいく証明方法を考えてみました。

ちなみに、初めてはてなブログMarkdown記法を使ってtexの数式で書いたのですが、 なかなかうまく書けないですね。

定理 自然数\mathbb{N}から実数\mathbb{R}への全単射は存在しない。

証明

自然数\mathbb{N}から実数\mathbb{R}の部分集合[0,1]へ全単射fが存在すると仮定する。

ここで関数g,hを下記の通り定義する。


g:[0,1]\times\mathbb{Z}_{10}\to\mathbb{Z}_{10}


g\left(r, n\right)=\lfloor r\times10^{n} \rfloor mod 10


h:\mathbb{Z}_{10} \to \mathbb{Z}_{10}

関数hは任意のx\in\mathbb{Z}_{10}に対しh\left(x\right)\neq x

を満たす関数であればなんでもよい

ここで実数rを以下の通り定義する。

r={\displaystyle
\sum_{i=1}^{\infty}\frac{h(g(r_{i},i))}{10^{i}}
}

仮定から、実数rに対応する整数Nが存在する。

{\displaystyle
g\left(r,N\right)=g\left(r_{N},N\right)=\lfloor \sum_{i=1}^{\infty}\frac{h(g(r_{i},i))}{10^{i}}\times10^{N} \rfloor mod 10=h(g(r,N))}

となり、矛盾する。 すなわち、自然数\mathbb{N}から実数\mathbb{R}全単射fが存在するという命題が偽であることがわかり、自然数から実数への全単射が存在しないことが証明できた。

僕が普通の対角線論法で納得いかない部分は、自然数から実数への対応表から、対応表にない実数を構成するところでした。対応表にない実数が、無限に並んだ自然数から実数への対応表のどれにも一致しないという論法において、何故無限個の実数と異なることを示すことができるのだろうという疑問がありました。 具体的に対応表に存在しない実数rを対角線上にある自然数から構成し、自然数と実数の間に全単射が存在するという仮定から、実数rに対応する自然数Nが存在することになるが、実数rのN番目の自然数は実数rのN番目の自然数と異なるという矛盾を導き出す。 このことによって、自然数から実数への全単射がないことが証明できる。

次は、ゲーデル不完全性定理かな?

そんな感じです。