logo

カントールの対角線論法 📂集合論

カントールの対角線論法

定理 1

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

証明

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

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

証明

一対一の対応 f:N(0,1)f : \mathbb{N} \to (0,1) が存在すると仮定すると、aij{ a } _{ ij } は小数点以下jj番目の数字で次のように表せる。 f(i)=0.ai1ai2ai3ai4 f(i)=0. { a } _{ i1 } { a } _{ i2 } { a } _{ i3 } { a } _{ i4 } \cdots すると、自然数 iNi \in \mathbb{N} に対して f(1)=0.a11a12a13a14f(2)=0.a21a22a23a24f(3)=0.a31a32a33a34f(k)=0.ak1ak2ak3ak4 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(0,1)z \in (0,1) を次のように定義しよう。 z=0.z1z2z3z4,(zj={2ajj가 홀수일 때1ajj가 짝수일 때) 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) これは上の配列の対角線上にある数、a11,a22,a_{11} , a_{22} , \cdots たちと奇偶が反対の数を選ぶことだ。zzf(i)f(i) の小数点以下ii番目の数字が奇数か偶数かだけ見てみよう。zi { z }_{ i } が偶数ならaii{ a } _{ ii } は奇数で、 zi\ { z } _{ i } が奇数ならaii{ a } _{ ii } は偶数なので zf(1)zf(2)zf(3)zf(k) z\neq f(1) \\ z\neq f(2) \\ z\neq f(3) \\ \vdots \\ z\neq f(k) \\ \vdots になる。全ての自然数 ii に対してzf(i)z \neq f(i) でありzf(N)z \notin f(\mathbb{N}) とすると、ff は一対一の対応なのでf(N)=(0,1)f(\mathbb{N})=(0,1) でありz(0,1)z \in (0,1) のためzf(N)z\in f(\mathbb{N}) でなければならない。これは仮定に矛盾するので、一対一の対応 f:N(0,1)f : \mathbb{N} \to (0,1) は存在しない。


  1. 이흥천 역, You-Feng Lin. (2011). 집합론(Set Theory: An Intuitive Approach): p231. ↩︎