カントールの定理、ベルンシュタインの定理

サイトのTOP→理系インデックス
集合論のTOP→集合論インデックス





D17 ( カントールの定理 )

は非可算集合である。( つまり、card<card である )

証明 ( カントールの対角線論法 )

区間 (0、1] が無限可算であると仮定する。(背理法)

いま、各実数 x∈(0、1] に番号を付けることができる。

つまり、(0、1]={α、α、・・・} と表せる。

有限小数については次のような2通りの表し方がある。



ここでは、右辺のような表記法を採用する。

−−−−−−−−−−−−−−−−−−−−

ここで、

「 本当に 0.25 と 0.24999・・・を等号でつないでよいのだろうか?」

・・・と疑問に思う人がいるかもしれない。

しかし、この表記に問題はない。

これは実数の連続性に基づく事実である。

実数の連続性について詳しいことは微分積分学を参照。

ただし、これを知らないことによって以下の理解に支障が出ることはない。

ここでは上の事実を認めることにしよう。

−−−−−−−−−−−−−−−−−−−−

ここで、amn は 0、1、・・・、9 のいずれかを表すものとする。

いま、区間 (0,1] における全ての実数は次のように表せる。



対角線上に位置する数 ann について、新しく b を次のように定める。



そして、小数βを次のように定める。



いま、βは区間 (0、1] に属する。

しかし、βはどのα とも一致しない。

なぜなら、α とβは第 n 位の数が必ず異なるからである。

つまり、最初の仮定が間違っていたことになるから、区間 (0、1] は無限可算ではない。

また、(0、1] と は濃度が等しいから、 も無限可算ではない。(※D16)

よって、card≠card である。

一方、明らかに から への単射が存在するので、card≦card である。

よって、card<card である。

別証明

微分積分インデックスの 『 区間縮小法 』 を用いた証明を行う。

実数の連続性を知らない人はこの証明を読まなくてよい。

が無限可算であると仮定する。(背理法)

いま、 の元に番号を付けることができる。

そこで、 を次のようにおく。



ここで、数列 a、a、a 、・・・と b、b、b、・・・ を次のようにおく。



上の定め方により、次のことが順番に導かれる。



( これらは高校レベルの簡単な計算によって導かれるので、この部分の証明は省略する )

(*2)より、



(*3)より、



(*1)より、



区間縮小法より、



c∈ であるから、(*0)より、



つまり、c∈{ x、・・・、x }である。(★1)

任意の n に対して c∈[ a、b ] であるから、c∈[ a、b ] である。(★2)

(★1)、(★2)より、



これは(*4)と矛盾する。

よって、最初の仮定が間違っていたことになる。

よって、 は無限可算ではない。

D18 ( ベルンシュタインの定理 )

X、Y を集合とする。

単射 f:X→Y と 単射 g:Y→X が存在すると仮定する。

このとき、cardX=cardY が成り立つ。

補足

つまり、cardX≦cardY かつ cardY≦cardX ならば cardX=cardY である。

ベルンシュタインの定理は一見するとシンプルであるが、その証明は意外に面倒である。

証明

f:X→Y、g:Y→X を単射とする。

まず、次のようにおく。



次のようにおく。



次の(1)〜(4)を証明する。

(1) b∈B ならば g(b)∈A である。

(2) 任意の a∈A に対し、ある b∈B が一意に存在して、g(b)=a となる。

(3) a∈X−A ならば f(a)∈Y−B である。

(4) 任意の b∈Y−B に対し、ある a∈X−A が一意に存在して、f(a)=b となる。

−−−−−−−−−−−−−−−−−−−−

(1)の証明

b∈B とおく。

いま、ある整数 n ( n≧0 ) が存在して、b∈B となるようにできる。

よって、g(b)∈An+1 である。

よって、g(b)∈A である。

−−−−−−−−−−−−−−−−−−−−

(2)の証明

a∈A とおく。

いま、ある自然数 n が存在して a∈A となるようにできる。

よって、ある b∈Bn−1 が存在して a=g(b) となるようにできる。

また、b∈B である。

g は単射であるから、a=g(b) を満たす b は一意である。

−−−−−−−−−−−−−−−−−−−−

(3)の証明

a∈X−A とおく。

a∈X であるから、f(a)∈f(X)⊂Y である。

ここで、f(a)∈B と仮定する。(背理法)

いま、ある自然数 n が存在して f(a)∈B となるようにできる。

よって、ある a’∈A が存在して f(a)=f(a’) となるようにできる。

f は単射であるから、a=a’である。

つまり、a∈A である。

しかし、これは最初の仮定 『 a∈X−A 』 と矛盾する。

よって、f(a)∈Y−B である。

−−−−−−−−−−−−−−−−−−−−

(4)の証明

b∈Y−B とおく。

いま、b は B に属さない。

よって、b∈f(X)である。

よって、ある a∈X が存在して b=f(a) となるようにできる。

ここで、a∈A と仮定する。(背理法)

いま、ある自然数 n が存在して、a∈A となるようにできる。

よって、b=f(a)∈B である。

よって、b∈B である。

これは最初の仮定 『 b∈Y−B 』 に矛盾する。

よって、a∈X−A である。

f は単射であるから、b=f(a)を満たす a は一意である。

−−−−−−−−−−−−−−−−−−−−

(1)、(3)より、次のような写像を定めることができる。



( つまり、h は g の制限であり、h は f の制限である )

g と f は単射なので、h と h は単射である。

また、(2)、(4)より、h と h は全射である。

よって、h と h は全単射である。

よって、h の逆写像 h−1:A→B が存在する。

さらに、次のような写像を定める。



−1 と h は全単射であるから、h も全単射である。

よって、cardX=cardY である。

補足

上の証明では、次のようにおいた。



,A,・・・や B,B,B ,・・・ がどのように表されるのか図で示してみよう。

まず、B と f(X) を図示すると、



さらに、A を書き加えると、



さらに、B を書き加えると、

( B は f(X)に含まれていることに注意する )



さらに、A を書き加えると、

( B∩B=φで、g は単射であるから、A∩A=φとなることに注意 )



これが無限に繰り返される。



D19

card=card()である。

証明

次のように定める。



明らかに、f は から への単射である。(★1)

−−−−−−−−−−−−−−−−−−−−

一方、(a、b)∈(0、1] に対して、次のようにおく。



数字を交互に並べて、次のような小数を考える。



次のように定める。



明らかに、g は単射である。

また、(0、1] と の濃度は等しい。(※D16)

よって、(0、1] の濃度は等しい。

つまり、(0、1] の間に全単射が存在する。

この全単射と写像 g を合成すれば、 から への単射ができる。(★2)

−−−−−−−−−−−−−−−−−−−−

(★1)と(★2)より、card=card()である。(※D18)

定義 ( 有限集合の濃度 )

A を n 個の元から構成される有限集合とする。

このとき、明らかに、次は同値である。

(1) ある集合 B が存在して、cardA=cardB となるようにできる。

(2) B は n 個の元から構成される有限集合である。

そこで、n個 の元から構成される有限集合 A の濃度を cardA=n と定義する。

この定義により、『 濃度 』 という概念の中には 『 個数 』 という概念が内包されていることが分かる。

本来、個数という概念は有限集合についてのみ考えられる。

それを無限個にまで拡張させたものが濃度である。

定義 ( 連続体濃度 )

の濃度を 『 連続体濃度 』 という。

連続体濃度を次式の右辺のような記号で表す慣習がある。



この記号を 『 アレフ 』 という。

ところで、「 card と card の間の濃度は存在しない 」 という主張がある。

これを 『 連続体仮説 』 という。

しかも、次のことが知られている。

「 連続体仮説はZFCそれ自体が矛盾を含まない限り、ZFC公理系からは証明も反証もできない 」

これに関する話は難しいのでここでは触れない。

詳しいことは数理論理学や公理的集合論で議論される。