対角線論法
Cantor's diagonal argument
1891
背理法に基づく証明手法
実数の集合などが非可算であることを証明
命題: 「$ |\mathbb{N}|=|\mathbb{R}|が成り立つか？」を背理法を用いて証明する この際に対角線論法を使う
$ \mathbb{N}と$ (0,1)の間に全単射写像が存在するか？を見ればいい
「存在する」と仮定すると、
全単射写像$ f:\mathbb{N}\to(0,1)が存在する 表を書く
自然数$ 0,\cdotsに対し、$ (0,1)の元を対応させていく
1の行には$ 0.a_{11}a_{12}a_{13}a_{14}a_{15}\cdotsという一つの少数を書く
$ 0.a_{11}a_{12}a_{13}a_{14}a_{15}\cdots=0.000\cdots01のイメージ
$ 0.a_{21}a_{22}a_{23}a_{24}a_{25}\cdots=0.000\cdots02のイメージ
https://gyazo.com/6950933a53a29b66201e513d15198b56
表の対角線に着目し、
$ a_{11}と異なる数値$ b_1
$ a_{22}と異なる数値$ b_2
..
をn+1行目に追加する
https://gyazo.com/5897963347eeeddfe04fc465855ad3f3
この新しい数$ 0.b_1b_2b_3b_4\cdotsは上の表内には存在しない数字になる
なぜか
例えばこのbの数が1行目の$ 0.a_{11}a_{12}a_{13}a_{14}a_{15}\cdots=0.000\cdots01と同じだとすると
「$ a_{11}と異なる数値$ b_1」に矛盾する
よって$ 0.b_1b_2b_3b_4\cdotsは$ (0,1)の元だが、上の表には存在しないので、「全単射写像$ f:\mathbb{N}\to(0,1)が存在する」に矛盾する
よって$ |\mathbb{N}|\ne|(0,1)|がわかった
次に$ |(0,1)|=|\mathbb{R}|を証明する
$ y=\tan{(\pi({x-\frac{1}{2}}))}のグラフを考えると自明にわかる
https://gyazo.com/9648fcd3d45f5c1a4a3d7be305c2b3a1
左は普通の$ y=\tan{x}で、それを平行移動したものが右
$ x軸で見ると$ (0,1)で、$ y軸で見ると$ |\mathbb{R}|なので$ |(0,1)|=|\mathbb{R}|がわかる
以上より$ |\mathbb{N}|\ne|(0,1)|=|\mathbb{R}|が導けた
ちなみに
同じ議論により$ |\mathbb{Q}|\lt|\mathbb{R}|が導ける
$ \mathbb{R}= $ \mathbb{Q}+無理数
なので、有理数より、無理数の方がめちゃくちゃ多いということがわかる
参考
https://www.youtube.com/watch?v=Id7doZHJ9WI