📂集合論

カントールの対角線論法

定理 ¹

開区間$(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)$は存在しない。

■