対角線論法（？）について

オートマトン言語理論計算論I（サイエンス社）という本の第７、８ページに
すべての無限集合が等しい濃度を持つわけではない例として、
「整数全体の集合と実数全体の集合について考えてみよう。仮に、実数の
全体が正整数と１対１に対応づけられたとする。そのとき、各 i=1,2,3,…
について小数点以下 i 桁目が、第 i 番目の実数（上の対応で正整数 i に
対応づけられた実数）の小数点以下 i 桁目の数字に法１０のもとで５を加え
た数であるような実数を考える。するとこれは上で正整数と対応づけられた
どの実数とも異なる数である。このことから、実数全体と正整数を１対１に
対応づけることがそもそも不可能だったことがわかる。」
とあり、この議論が対角線論法と呼ばれるそうですが、何度読んでもさっぱ
り理解できないのです。

特に
「そのとき、各 i=1,2,3,…について小数点以下 i 桁目が、第 i 番目の実数
（上の対応で正整数 i に対応づけられた実数）の小数点以下 i 桁目の数字に
法１０のもとで５を加えた数であるような実数を考える」
がイメージできないのです。

もし対角線論法について理解されてる方がいらっしゃいましたら、是非とも
ご教授願いませんでしょうか？

よろしくお願いします。

No.1 回答者： uzo 回答日時： 2001/04/10 12:44

カントールによる有名な証明です。

全ての実数が一列に並べられたとします。
そして、一つ目の実数の小数点一桁めの数字とは違う数字を選ぶ
　　　　２つめの実数の小数点二桁目の数字とは違う数字を選ぶ
　　　　・・・・
　　　　ｎこめの実数の小数点ｎ桁目の数字とは違う数字を選ぶ
　　　　・・・・
こうやって新しい数をつくります。
以上のように選んだ数字で、小数点ひとけためから順序よく新たな
数字をつくります。
するとそのような数字は、もともと並べた数字のどれとも異なります。
なぜなら、必ず、小数点以下ｉ桁目の数が違うように選ばれているわけですから。
したがって、「全ての実数を一列に並べられる」という仮定が誤っている、
したがって、実数は時全数と一対一の対応がつかない、との結論が得られます。

紙に書いてみると、左上から右下へ「対角線上の数字」に着目していきます
から、「対角線論法」と呼ばれます。


＞「そのとき、各 i=1,2,3,…について小数点以下 i 桁目が、第 i 番目の実数
＞（上の対応で正整数 i に対応づけられた実数）の小数点以下 i 桁目の数字に
＞法１０のもとで５を加えた数であるような実数を考える」

これは上記の論法で、「i桁目とは異なる数値を選ぶ」ということを嫌い、
特定の数値を指定するためのしかけだと思います。「選択公理」を使うことを
嫌ったのでしょう。
　
ＵＲＬは「カントール」でGooを検索するといくつかでてきますが、
わかりやすいものがパッと見つけられませんでした。
だけれども、少し探せばあると思います。

この回答へのお礼

解説ありがとうございました。
本の初っ端からつまづいていて、先が思いやられてますが、もっと想像力をもって読んでいこうと思います。

お礼日時：2001/04/10 13:46

No.2 回答者： serpent-owl 回答日時： 2001/04/10 12:50

　下記参考URLの質問「ごめんなさい、また無限です」をご覧下さい。

無限ネタは少し前に流行ったようですね。そこでのstomachmanさんの回答が完璧回答です。

参考URL：http://oshiete1.goo.ne.jp/kotaeru.php3?q=31937

この回答へのお礼

すいませんでした。　あらかじめ「教えてｇｏｏ」内を自分で検索するべきだったかもしれません。
有用なＵＲＬを教えていただきありがとうございました。

お礼日時：2001/04/10 13:42

No.3 ベストアンサー 回答者： Umada 回答日時： 2001/04/10 12:58

おぼろげですが思い出しました。

証明は背理法によります。

仮定：すべての実数は順序付けできる(整数と対応付けできる)

いますべての実数を順序付けできたとすると、

1番目　0.1100・・・
2番目　0.12102・・・
3番目　0.13451・・・

と書き下すことができるはずです。(上の数字は例えばのものです。もちろん実際にはもっと稠密です)

さていま1番目の実数の小数点第1位を、適当な数に書き換えてみましょう。
(上記の例では「法10で5を加える」なんて書いてあるので分かりにくくなっているのですね。必ずしもそれでなくてよいのです)
例えば
0.2100・・・
といった具合です。さらに小数点第2位も適当に書き換えますが、このときにも第2番目の数の小数点第2位以外の数字を選びます。2番目の数字の小数点第2位は2ですから、例えば7に書き換えるとして
0.2700・・・
とします。さらに小数点第3位についても3番目の数字の第3位と違う数字に書き換えます。上記の例では4以外の数字を選びます。5にしてみましょう。
0.2750・・・

さてこうして作られた数は、一番最初の「実数を順番に並べたもの」のどこに入っているでしょうか。ところがi番目の数とは必ず小数点第i位の数字がが違いますから、この作られた数は実数のはずなのに、実数の集合のどこにも入っていないことになります。矛盾。

従って仮定が間違っていた・・・実数は整数と対応付けできない、という結論が導かれるのです。

この回答へのお礼

目から鱗が落ちるようでした。なるほど、そう言われればそう解釈できますね。
もっと読解力を養わなければいけませんね。
ありがとうございました。

お礼日時：2001/04/10 13:38