📂集合論

カントールの対角線論法

定理 ¹

開区間 $(0,1)$ は非可算集合だ。

証明

実数集合 $\mathbb{R}$ は可算集合ではなく、これは実数集合と任意の可算集合の間に「一対一の対応」が存在しないことから示される。これは自然数集合と開区間 $(0,1)$ の間に一対一の対応が存在しないことを示し、それを系として得られる。

カントールはこれを驚くべき方法で証明し、その方法は「対角線論法」という名前でカントールの成果として残った。結果を抜きにしても、その自体で美しさを感じることができる証明なので、何回読んでも理解できない場合でも、理解できるまで読み続けること。

証明

一対一の対応 $f : \mathbb{N} \to (0,1)$ が存在すると仮定すると、${ a } _{ ij }$ は小数点以下$j$番目の数字で次のように表せる。 $$ f(i)=0. { a } _{ i1 } { a } _{ i2 } { a } _{ i3 } { a } _{ i4 } \cdots $$ すると、自然数 $i \in \mathbb{N}$ に対して $$ f(1)=0. { a } _{ 11 } { a } _{ 12 } { a } _{ 13 } { a } _{ 14 } \cdots \\ f(2)=0. { a } _{ 21 } { a } _{ 22 } { a } _{ 23 } { a } _{ 24 } \cdots \\ f(3)=0. { a } _{ 31 } { a } _{ 32 } { a } _{ 33 } { a } _{ 34 } \cdots \\ \vdots \\ f(k)=0. { a } _{ k1 } { a } _{ k2 } { a } _{ k3 } { a } _{ k4 } \cdots \\ \vdots $$ のような配列で表せるだろう。ここで$z \in (0,1)$ を次のように定義しよう。 $$ z=0. { z } _{ 1 } { z } _{ 2 } { z } _{ 3 } { z } _{ 4 } \cdots, \left( { z } _{ j } = \begin{cases} 2 & { a } _{ jj } \text{가 홀수일 때} \\ 1 & { a } _{ jj } \text{가 짝수일 때} \end{cases} \right) $$ これは上の配列の対角線上にある数、$a_{11} , a_{22} , \cdots$ たちと奇偶が反対の数を選ぶことだ。$z$ と$f(i)$ の小数点以下$i$番目の数字が奇数か偶数かだけ見てみよう。$ { z }_{ i }$ が偶数なら${ a } _{ ii }$ は奇数で、$\ { z } _{ i }$ が奇数なら${ a } _{ ii }$ は偶数なので $$ z\neq f(1) \\ z\neq f(2) \\ z\neq f(3) \\ \vdots \\ z\neq f(k) \\ \vdots $$ になる。全ての自然数 $i$ に対して$z \neq f(i)$ であり$z \notin f(\mathbb{N}) $ とすると、$f$ は一対一の対応なので$f(\mathbb{N})=(0,1)$ であり$z \in (0,1)$ のため$z\in f(\mathbb{N})$ でなければならない。これは仮定に矛盾するので、一対一の対応 $f : \mathbb{N} \to (0,1)$ は存在しない。

■