カントールの対角線論法
📂集合論カントールの対角線論法
定理
開区間 (0,1) は非可算集合だ。
証明
実数集合 R は可算集合ではなく、これは実数集合と任意の可算集合の間に「一対一の対応」が存在しないことから示される。これは自然数集合と開区間 (0,1) の間に一対一の対応が存在しないことを示し、それを系として得られる。
カントールはこれを驚くべき方法で証明し、その方法は「対角線論法」という名前でカントールの成果として残った。結果を抜きにしても、その自体で美しさを感じることができる証明なので、何回読んでも理解できない場合でも、理解できるまで読み続けること。
証明
一対一の対応 f:N→(0,1) が存在すると仮定すると、aij は小数点以下j番目の数字で次のように表せる。
f(i)=0.ai1ai2ai3ai4⋯
すると、自然数 i∈N に対して
f(1)=0.a11a12a13a14⋯f(2)=0.a21a22a23a24⋯f(3)=0.a31a32a33a34⋯⋮f(k)=0.ak1ak2ak3ak4⋯⋮
のような配列で表せるだろう。ここでz∈(0,1) を次のように定義しよう。
z=0.z1z2z3z4⋯,(zj={21ajj가 홀수일 때ajj가 짝수일 때)
これは上の配列の対角線上にある数、a11,a22,⋯ たちと奇偶が反対の数を選ぶことだ。z とf(i) の小数点以下i番目の数字が奇数か偶数かだけ見てみよう。zi が偶数ならaii は奇数で、 zi が奇数ならaii は偶数なので
z=f(1)z=f(2)z=f(3)⋮z=f(k)⋮
になる。全ての自然数 i に対してz=f(i) でありz∈/f(N) とすると、f は一対一の対応なのでf(N)=(0,1) でありz∈(0,1) のためz∈f(N) でなければならない。これは仮定に矛盾するので、一対一の対応 f:N→(0,1) は存在しない。
■