• ベストアンサー

対角線論法(?)について

オートマトン言語理論計算論I(サイエンス社)という本の第7、8ページに すべての無限集合が等しい濃度を持つわけではない例として、 「整数全体の集合と実数全体の集合について考えてみよう。仮に、実数の 全体が正整数と1対1に対応づけられたとする。そのとき、各 i=1,2,3,… について小数点以下 i 桁目が、第 i 番目の実数(上の対応で正整数 i に 対応づけられた実数)の小数点以下 i 桁目の数字に法10のもとで5を加え た数であるような実数を考える。するとこれは上で正整数と対応づけられた どの実数とも異なる数である。このことから、実数全体と正整数を1対1に 対応づけることがそもそも不可能だったことがわかる。」 とあり、この議論が対角線論法と呼ばれるそうですが、何度読んでもさっぱ り理解できないのです。 特に 「そのとき、各 i=1,2,3,…について小数点以下 i 桁目が、第 i 番目の実数 (上の対応で正整数 i に対応づけられた実数)の小数点以下 i 桁目の数字に 法10のもとで5を加えた数であるような実数を考える」 がイメージできないのです。 もし対角線論法について理解されてる方がいらっしゃいましたら、是非とも ご教授願いませんでしょうか? よろしくお願いします。

  • 科学
  • 回答数3
  • ありがとう数7

質問者が選んだベストアンサー

  • ベストアンサー
  • Umada
  • ベストアンサー率83% (1169/1405)
回答No.3

おぼろげですが思い出しました。 証明は背理法によります。 仮定:すべての実数は順序付けできる(整数と対応付けできる) いますべての実数を順序付けできたとすると、 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位の数字がが違いますから、この作られた数は実数のはずなのに、実数の集合のどこにも入っていないことになります。矛盾。 従って仮定が間違っていた・・・実数は整数と対応付けできない、という結論が導かれるのです。

unicorn01
質問者

お礼

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

その他の回答 (2)

回答No.2

 下記参考URLの質問「ごめんなさい、また無限です」をご覧下さい。無限ネタは少し前に流行ったようですね。そこでのstomachmanさんの回答が完璧回答です。

参考URL:
http://oshiete1.goo.ne.jp/kotaeru.php3?q=31937
unicorn01
質問者

お礼

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

  • uzo
  • ベストアンサー率30% (10/33)
回答No.1

カントールによる有名な証明です。 全ての実数が一列に並べられたとします。 そして、一つ目の実数の小数点一桁めの数字とは違う数字を選ぶ     2つめの実数の小数点二桁目の数字とは違う数字を選ぶ     ・・・・     nこめの実数の小数点n桁目の数字とは違う数字を選ぶ     ・・・・ こうやって新しい数をつくります。 以上のように選んだ数字で、小数点ひとけためから順序よく新たな 数字をつくります。 するとそのような数字は、もともと並べた数字のどれとも異なります。 なぜなら、必ず、小数点以下i桁目の数が違うように選ばれているわけですから。 したがって、「全ての実数を一列に並べられる」という仮定が誤っている、 したがって、実数は時全数と一対一の対応がつかない、との結論が得られます。 紙に書いてみると、左上から右下へ「対角線上の数字」に着目していきます から、「対角線論法」と呼ばれます。 >「そのとき、各 i=1,2,3,…について小数点以下 i 桁目が、第 i 番目の実数 >(上の対応で正整数 i に対応づけられた実数)の小数点以下 i 桁目の数字に >法10のもとで5を加えた数であるような実数を考える」 これは上記の論法で、「i桁目とは異なる数値を選ぶ」ということを嫌い、 特定の数値を指定するためのしかけだと思います。「選択公理」を使うことを 嫌ったのでしょう。   URLは「カントール」でGooを検索するといくつかでてきますが、 わかりやすいものがパッと見つけられませんでした。 だけれども、少し探せばあると思います。

unicorn01
質問者

お礼

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

関連するQ&A

  • 対角線論法 10進数展開

    対角線論法を用いて、自然数全体の集合と[0,1]区間の間には全単射な写像は定められないということを示す証明を読んでいて疑問に思ったのですが、 循環しない少数は10進数展開が一意には定まらない(例えば、2/5=0.400…=0.399…)のに、なぜ「実数a,bに対して、a,bの少数第n位が異なればa,bが異なる」というようなことができるのでしょうか? あと、循環しない少数ではない実数(1/3とか√2とかπとか)の10進数展開は一意に定まると思うのですが、その証明が考えてもわかりません。知っている方がいたら教えてもらえないでしょうか? 最後に、10進展開についても疑問があるのですが、 「実数aが10進展開できる」とはどういうことなのでしょうか? これは、An=k(n)/(10^n) (ただし0≦k(n)≦9)という数列の級数がaと一致する。すなわち、級数の部分和がaに収束する ということなのでしょうか? それとも、 {ΣAn}⊂Map({整数},{有理数})という集合(今度はAnのnは整数にすることにします。雰囲気的にはΣはローラン展開のΣに近いと思います。あと、-9≦k(n)≦9ということにします。)に自然に和を定義し、積を(小学校のときの筆算を自然に拡張する意味で)自然に定義します。そのとき{ΣAn}が体をなすことを示し、{実数全体}と{ΣAn}が同型であるとき、実数aに対応する{ΣAn}の元をaの10進展開と呼ぶのでしょうか? 以上です。よろしくお願いします。

  • Cantorの対角線論法を用いる証明

    自然数全体の集合Nと、集合Nから集合{0,1}への写像すべてからなる集合Xの濃度が等しいことを証明するのに、Cantorの対角線論法をどのように用いればよいのですか?

  • 自然数と小数を1対1対応で対角線論法し無矛盾したい

    自然数と有理数(循環小数)を1対1対応をつけて、対角線論法して無矛盾したいです。 自然数を1から始めることにします。 斜めに拾った数字で数を作ります。 有理数は循環小数なので、0.1010101・・・を0⇔1変換すると 0.0101010・・・になるのでは?が基本アイデアです。 自然数と有理数(循環小数)の一部を2進数表記にして 対応付けを作ります。 リスト1 1:11/12 =0.916666666・・・は2進数表記で  0.1110101010101… 2:8 /12 =0.666666666・・・は2進数表記で  0.1010101010101… 3:11/48 =0.229166666・・・は2進数表記で  0.0011101010101… 4:8 /48 =0.166666666・・・は2進数表記で  0.0010101010101… 5:11/192=0.057291666・・・は2進数表記で  0.0000111010101… 6:8 /192=0.416666666・・・は2進数表記で  0.0000101010101… 7:11/768=0.014322916・・・は2進数表記で  0.0000001110101… 8:8 /768=0.010416666・・・は2進数表記で  0.0000001010101… . n:11/3*2^(n+1){nは奇数}は2進数表記で 0.(0がn-1個続いて)11101010101… n:8 /3*2^(n ){nは偶数}は2進数表記で 0.(0がn-2個続いて)10101010101… . . 1つ目の有理数(循環小数)の小数1桁目を0⇔1反転し、 nつ目の有理数のn桁目を0⇔1反転して 対角線論法で作った2進数は0.010101010101…です。 でもリスト1に数がないです。 2つ目と3つ目の間に0.0101010101010…を入れると、 対角線論法で作った2進数が変わってしまい、うまくいきませんでした。 しょうがないので一桁づらしてリスト2を作ります。 リスト2 1:11/24 =0.4583333333・・・は2進数表記で  0.0111010101010… 2:8 /24 =0.3333333333・・・は2進数表記で  0.0101010101010… 3:11/96 =0.1145833333・・・は2進数表記で  0.0001110101010… 4:8 /96 =0.0833333333・・・は2進数表記で  0.0001010101010… 5:11/384 =0.0286458333・・・は2進数表記で  0.0000011101010… 6:8 /384 =0.0208333333・・・は2進数表記で  0.0000010101010… 7:11/1536=0.0071614583・・・は2進数表記で  0.0000000111010… 8:8 /1536=0.0052083333・・・は2進数表記で  0.0000000101010… . n:11/3*2^(n ){nは奇数}は2進数表記で 0.(0がn-1個続いて)01110101010… n:8 /3*2^(n+1){nは偶数}は2進数表記で 0.(0がn-2個続いて)01010101010… となって、リスト2の2つ目にリスト1から対角線論法で作った数が出てきます。 なんとなく自然数と有理数の一部が対応したような感じがします。 リスト1とリスト2個別にみれば 単調増加なので同じ有理数に、違う自然数が対応してるような 感じがします。 ・基本的に誤りでしょうか? ・リストが2つに分かれちゃいましたが1つにまとめられますか? ・有理数全体の有限小数でつまり、循環のパターン110とか001とか がたくさんあっても対角線論法で、無矛盾するためには どうすればよいでしょうか?

  • カントールの対角線論法についておしえてください。

      《無限集合にはその大きさの大小があるということ》  というカントールの定理をめぐる次の証明の仕方はマチガイではないでしょうか?  なるべく数式を使わずにおしえてくださるとありがたいです。 ▲ (哲学するサラリーマン:平行線が交わる点) ~~~~   http://blogs.dion.ne.jp/le_fou/archives/10216164.html  2.神の証明  (その後半部分)  ( a ) 次に、2つめの定理〔*--《無限集合にはその大きさの大小があるということ》--〕を見てみましょう。  ( b ) これもわかりやすい例を挙げて説明します。無理数全部の集合と自然数全部の集合とはどちらが大きいでしょうか。  ( c ) ここに(0と1の間の)すべての無理数がただ1つの列にリストアップされていると仮定します。例えば、   0.17643567……   0.23482435……   0.62346286……  ( d ) 次に、この無限列の各行に対応する各々の無理数と、1から始まる自然数とが次のような1対1対応を作ると仮定します。   1⇔0.17643567……   2⇔0.23482435……   3⇔0.62346286……  ( e ) ここで自然数1に対応する無理数から小数点以下1番目の位を取ります。次に自然数2に対応する無理数から2番目の位を取ります。これを続けていけば0.133……という無理数が得られます。  ( f ) この無理数の小数点以下の数字を各々勝手に変えます。このような操作によって例えば0.245……という無理数ができます。  ( g ) この数は、自然数1に対応する無理数とは小数以下1番目の位で違い、自然数2に対応する無理数とは2番目の位で違い……となり、自然数と1対1対応させたどの無理数とも異なっていることが明らかです。  ( h ) すなわち、無理数全部の集合は自然数全部の集合よりも濃度において大であることが示される訳です。  ~~~~~~~~  【Q‐1】 ( c )の《(0と1の間の)すべての無理数》というとき そのすべてがリストアップされうるのでしょうか? それは 無限――つまりこの場合 可能無限――であると見てよいか?  【Q‐2】 もし前項の無理数の集合が 無限であるならば ( d )の 1,2,3,・・・とやはり対応させられる自然数の数も無限になる。と捉えてよいか?  【Q‐3】 もしよければ ( f )に言うあらたに勝手に作った無理数(例えば0.245……)は もともとその無理数の集合の中にふくまれているものではないか?  【Q‐4】 言いかえると その無理数((例えば0.245……)も とうぜん自然数の無限の列挙と初めに対応していたはずではないか? なぜ( g )のような結論にみちびかれるのか?

  • 「無理数全体の集合Pについて、|P|>N0(アレフゼロ)を示せ」

    「無理数全体の集合Pについて、|P|>N0(アレフゼロ)を示せ」 という問題がわかりません。解き方を教えて下さい。 教科書には実数の集合の濃度がアレフゼロより大きいことの証明が載っていて、それは無限小数に関する対角線論法を使っていたので、同じ方法で証明しようとしたのですが、その場合、対角線論法により作られた新しい無限小数が無理数に含まれることを示せなかったので挫折しました。(当然実数には含まれるのですが・・・)この方法でできるのでしょうか?それとも全く違った方法を使うのでしょうか?  よろしくお願いします。

  • 集合 濃度の問題

    集合・位相の初心者です。 以下の問題の意味がよくわかりません。 問.Xを小数点以下の各桁の値が2か3か4であるような   小数全体の集合とするとき、|X|>|N|を証明せよ。 質問(1)小数点以下の各桁の値が2か3か4であるような小数    とは、例えばどんな小数ですか。   (2)証明の仕方は、1)|X|≧|N|が成立する。2)|X|≠|N|    である。を示せばよいですか。    また、対角線論法を使いますか。 レベルの低い質問かもしれませんが、いろいろ教えていただけたら 助かります。お願いします。

  • 実数と自然数は同じ個数なのではないでしょうか?

    すべての自然数とすべての実数を1対1で対応させる(すべての実数を一列に並べる)方法を考えました。間違いがあれば教えてください。 *方法1*「後出し」は実数の専売特許にあらず まず、すべての自然数と、異なる実数を無限に並べたもの、とを対応させるのだが、それは、異なる実数を無限に並べた「第一列」の「一番目」の実数を「1・1」とすると、 1→1・1 2→1・2 3→1・3 ・ ・ ・ と表すことができる。これはいわゆる「すべての自然数とすべての実数を1対1に対応させたと仮定したもの」であり、対角線論法によってこの表には存在しない実数を作れることから、仮定は間違い=「実数は自然数より多い」という結論になるのが従来の話である。しかしこれは、自然数を対応させる対象を「第一列」に限定したことによる間違った結論だ。 対角線上の数字のずらし方は、すべて一つずらす1111…の他に、1211…,1234…,2624…と無限にあるので、一つの対角線から、「第一列」には存在しない実数を無限に生み出すことができる。対角線論法によって生み出された無限の実数を並べた「第二列」に自然数を対応させることができなければ先の結論は正しいことになるが、そんなことは全然なく、「第二列」の「一番目」の実数を「2・1」とすると、 1→1・1 2→2・1 3→1・2 4→2・2 5→1・3 6→2・3 ・ ・ ・ のように、始めの、自然数と「第一列」の対応を解消した後、あらためて自然数を、「第一列」と「第二列」に、交互に対応させればいいだけの話なのだ。で、これは、「第一列」と「第二列」を合わせて「新たな第一列」にした(=始めの状態にリセットした)ということであり、この「新たな第一列=N1」の対角線から、対角線論法によって「新たな第二列=N2」が生まれるので、そしたらまたそれまでの対応を解消して 1→N1・1 2→N2・1 3→N1・2 4→N2・2 5→N1・3 6→N2・3 ・ ・ ・ と、自然数を「新たな第一列」と「新たな第二列」に交互に対応させ、これを無限に繰り返せばいいのである。自然数を、「新たな第二列」の実数に、無限に対応させ続けることができるということは、すなわち両者の個数は同じということなのである。 それにしても、無限に生み出される「新たな第一列」と「新たな第二列」は合わせて「新たな第一列」にできるのに、なぜ始めから一列に並べることができないのか。 方法1を別の言い方でまとめると、まず 1→1・1 2→1・2 3→1・3 ・ ・ ・ のように、すべての自然数と、異なる実数を無限に並べたもの、とを対応させるところから始めて、次に 1→1・1 2→  ←2・1 3→1・2 4→  ←2・2 5→1・3 6→  ←2・3 ・ ・ ・ と、「第二列」の実数を「第一列」に割り込ませて、始めの、すべての自然数と、異なる実数を無限に並べたもの、とを対応させた状態 1→1・1 2→2・1 3→1・2 4→2・2 5→1・3 6→2・3 ・ ・ ・ ↓ 1→1・1(1・1) 2→1・2(2・1) 3→1・3(1・2) 4→1・4(2・2) 5→1・5(1・3) 6→1・6(2・3) ・ ・ ・ にリセットして、そしたらまた 1→1・1 2→  ←2・1 3→1・2 4→  ←2・2 5→1・3 6→  ←2・3 ・ ・ ・ と、「第二列」の実数を「第一列」に割り込ませて…とこれを無限に繰り返す、といった具合に説明することができる。 *方法2*実数を整列させる 方法1は「動的な対応」とでも言うべきものであり、できれば「静的な対応」が望ましいわけで、そのためには実数を整列させる必要があるのだが、以下のようなやり方ではだめなのか。 まず 1→0.1 2→0.2 ・ ・ ・ 9→0.9 10→0.01 11→0.11 12→0.21 ・ ・ ・ 99→0.99 100→0.001 101→0.101 102→0.201 ・ ・ ・ 9999→0.9999 10000→0.00001 10001→0.10001 10002→0.20001 ・ ・ ・ …835218→0.812538… …835219→0.912538… …835220→0.022538… ・ ・ ・ というように、すべての自然数と、0と1の間のすべての実数を、1対1に対応させる。右側が「0と1の間のすべての実数」であることに異論はあるだろうか。この列に存在しない(0と1の間の)実数は存在するのか。この列は、小数第一位の数字が1,2…9,0,1…9,0,1…となっているので、だいたいその値で推移しながら、実数が、0と1の間を無限に埋めていく形になっている。 例えば、小数点以下、一恒河沙の一恒河沙乗番目が2、一阿僧祇の一阿僧祇乗番目が3、一那由他の一那由他乗番目が4の 0.1…2…3…4… のような無理数について、この並びの途中までのものしかないとしたら、ではどこまでのものならあるのか。0.1…2か、0.1…2…3か、0.1…2…3…4か。実際には「途中まで」などということはなく、つまりこの列にこの無理数は存在し、この任意の無理数が存在するなら(0と1の間の)すべての無理数が存在するのである。で、この表は左右が対称的になっているから、右に無限小数が存在するなら左には無限桁の自然数が存在するのである。 有限桁の自然数を重複することなく無限に並べることができないのと同様に、有限小数を、重複することなく無限に並べることはできない。この列は0と1の間の実数を整列させたものであり、この列に存在しない(0と1の間の)実数は存在しない。 で、すべての実数を整列させると 0,0.1,0.2…0.9,0.01,0.11,0.21… 1,1.1,1.2…1.9,1.01,1.11,1.21… 2,2.1,2.2…2.9,2.01,2.11,2.21… ・ ・ ・ (0),-0.1,-0.2…-0.9,-0.01,-0.11… -1,-1.1,-1.2…-1.9,-1.01,-1.11… -2,-2.1,-2.2…-2.9,-2.01,-2.11… ・ ・ ・ となるので、すべての自然数とすべての実数を1対1に対応させると、 1→0 2→0.1 3→-0.1 4→1 5→-1 6→2 7→-2 8→1.1 9→-1.1 10→0.2 11→-0.2 12→0.3 13→-0.3 14→1.2 15→-1.2 16→2.1 17→-2.1 18→3 19→-3 ・ ・ ・ のようになる。 ところでそれでも従来の考えが正しい場合、循環小数と非循環小数の個数に差が出る本質的な原因、両者の違いは何なのか。明確な違いは「整数比で表せるか表せられないか」だが、循環小数と非循環小数をそれぞれ循環数列と非循環数列に置き換え(今問題にしているのは個数であり、小数点を取り除いても個数は変わらない)れば整数比は関係なくなるわけだし。単なる数字の組み合わせに過ぎない同じ無限数列でありながら、循環させないというだけで個数が多くなるというのは何とも妙な話である。

  • 実数の集合が非可算であることの証明

    対角線論法を用いて、実数の集合と自然数の集合が対等でないことを示せば、”実数の集合が非可算であること”は示せているのでしょうか?別の証明方法があるなら教えていただきたいです。 よろしくお願いします。

  • 四捨五入

    実数Xの小数点以下2桁目を四捨五入して実数Hとするプログラムと Xの10の位を四捨五入して整数Lとするプログラム(Xは正の整数) を教えてください。

    • ベストアンサー
    • Java
  • 常用対数

    (2/9)^50の小数点以下を切り捨てると、何桁の整数であるか求めよ。 という問題で、整数部分は33下桁の数である。というのはわかったのですが、ふと小数点以下の数が何桁あるのか求めることができるのかどうかが気になりました。どのように求めるか教えていただけないでしょうか?