• 締切済み

対角線論法による全単射有無の証明について

以下、Wikipediaの対角線論法の項目です。 http://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%B3%E3%83%88%E3%83%BC%E3%83%AB%E3%81%AE%E5%AF%BE%E8%A7%92%E7%B7%9A%E8%AB%96%E6%B3%95#.E8.87.AA.E7.84.B6.E6.95.B0.E3.81.AE.E9.9B.86.E5.90.88.E3.81.A8.5B0.2C_1.5D.E5.8C.BA.E9.96.93.E3.81.AE.E6.BF.83.E5.BA.A6.E3.81.AE.E9.81.95.E3.81.84 こちらをみていて思ったのですが、RをQ(有理数)と読み変えてもこの証明が可能なように思えてしまいます。はて、自然数は有理数に対して全単射のはず…。 (例えば、全ての有理数をp/qの形で表し、(p,q)なる数字の組み合わせとして番号付加すると、自然数と1対1対応できてしまいます。) Wikipediaの証明が、Q(有理数全体)では成り立たないことを教えてください。

  • entap
  • お礼率29% (93/313)

みんなの回答

  • nag0720
  • ベストアンサー率58% (1093/1860)
回答No.3

＞RをQ(有理数)と読み変えてもこの証明が可能なように思えてしまいます。 「aiを二進数展開したときのj桁目をai,jとし[3]、biを￢ai,iとする。 　そしてbを小数点展開が0.b1b2…となる実数とする。」 この最後の「実数とする」を「有理数とする」と読み替えてもいいんならね。 bは有理数？

  • B-juggler
  • ベストアンサー率30% (488/1596)
回答No.2

集合論ちゃんとやってみようかな？ でもここの質問に答えるために集合論をやるっていうのはおかしいか＾＾； 不完全性定理でここ使う？　使った覚えがない＾＾； 　＃どんどんと自信が無くなっていくんだけど。 代数学屋さんには、（例えば・・・）のところが怪しく見えます。 （２／５）と（４／１０）のときは、等しいけど。 有理数を自然数だけで一意的に決められるかなぁ？ 自信ないけど、一応。　だからベストアンサーはつけないで。 (=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

対角線論法で「Q と Z の濃度が異なる」といおうとした場合, 証明はどのような概形になるでしょうか? 実際に書いてみると「あやしいところ」に気付くかもしれませんよ.

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • 可算無限集合のベキ乗が可算無限でないことを対角線論法で証明する。

    http://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%B3%E3%83%88%E3%83%BC%E3%83%AB%E3%81%AE%E5%AF%BE%E8%A7%92%E7%B7%9A%E8%AB%96%E6%B3%95 をみているのですが、 わかりません。 証明 背理法による。全単射 ψ: X → 2^X が存在したとしよう。X の部分集合 A を だいたい可算無限の意味がよくわかりません。 お願いします。

  • 対角線論法　１０進数展開

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

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

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

  • イプシロンデルタ論法の証明について

    中学生です。まだ自分で読んだ程度なので未理解な部分もありますが、 自分で勝手に作った以下の話は解釈として正しいのでしょうか。 任意の正の数 ε に対し、ある正の数 δ が存在し、 0 < |x − a| < δ を満たせば、|f(x) − b| < ε が成り立つ。 これがイプシロンデルタ論法ですよね。 本には、εを適当に選んだら、δはそれに応じて選ぶもの と書いてあったんですが、つまりこれは、 δを一つ決めるときに行う計算（普通参考書には書いてない？）は、 0 < |x − a| < δが必要条件になり、 実際のイプシロンデルタ論法で行う証明では、必要十分条件であること を示そうとしている、と考えていいのでしょうか。 wikipediaにもあったんですけど、lim[x→2]x^2＝4を示すやり方 でも、おそらく|x^2-4|＜εからδ＝√(ε+4)-2を導いて、 証明では|x-2|＜δから|x^2-4|＜εを導いていますよね。 どこか勘違いしているようにも感じるんですが、 この解釈が正しいのかどうか、説明も兼ねてどなたか説明を お願いできませんか。よろしくお願い致します。

  • ユークリッドの素数無限の証明を教えて

    ユークリッドの素数無限の証明で分からないところがあります。 とりあえずWikipwdiaから引用します。 素数が無数に存在することの証明 - Wikipedia https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E3%81%8C%E7%84%A1%E6%95%B0%E3%81%AB%E5%AD%98%E5%9C%A8%E3%81%99%E3%82%8B%E3%81%93%E3%81%A8%E3%81%AE%E8%A8%BC%E6%98%8E a, b, …, k を任意に与えられた素数のリストとする。その最小公倍数 P := a × b × ⋯ × k に 1 を加えた数 P + 1 は、素数であるか、合成数かのいずれかである。素数であれば、最初のリストに含まれない素数が得られたことになる。 素数でなければ、何らかの素数 p で割り切れるが、p はやはり最初のリストに含まれない。なぜならば、リスト中の素数は P を割り切るので、P + 1 を割り切ることは不可能だからである。任意の素数のリストから、リストに含まれない新たな素数が得られるので、素数は無数に存在する。 ---- 引用ここまで ---- 前半はわかります。後半の「リスト中の素数は P を割り切るので、P + 1 を割り切ることは不可能」の部分がどうもわかりません。 「リスト中の素数は P を割り切る」のは当然ですが、だとするとなぜ「P + 1 を割り切ることは不可能」になるのかつながりませんでした。 なぜ「P + 1 を割り切ることは不可能」なのでしょうか？ この点について教えてください。 よろしくお願いします。

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

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

  • 自然数と小数を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とか がたくさんあっても対角線論法で、無矛盾するためには どうすればよいでしょうか?

  • Wikipediaの歴史の正確さと悪魔の証明について

    http://ja.wikipedia.org/wiki/%E6%96%B0%E3%83%BB%E3%82%B4%E3%83%BC%E3%83%9E%E3%83%8B%E3%82%BA%E3%83%A0%E5%AE%A3%E8%A8%80SPECIAL_%E6%88%A6%E4%BA%89%E8%AB%96 第3巻に対する非難で 証拠資料の不在はロジック上、集団自決否定の根拠にはならない とかかれていますが、これは悪魔の証明の要求ですか？

  • 仮言三段論法なのか定言三段論法なのか教えて

    http://100.yahoo.co.jp/detail/%E5%91%BD%E9%A1%8C%E8%AB%96%E7%90%86%E5%AD%A6/に、 ＡならＢ Ａ ゆえにＢ という、伝統的論理学の時代に「仮言三段論法」とよばれた推論とありますが、これは定言三段論法ではないのでしょうか？　下記のものが 仮言三段論法ではないのでしょうか？ ＡならＢであれば 且つ Ａであれば そのときはＢ

  • この初等的証明は何故、証明になってるのですか？

    https://ja.wikipedia.org/wiki/%E4%BB%A3%E6%95%B0%E5%AD%A6%E3%81%AE%E5%9F%BA%E6%9C%AC%E5%AE%9A%E7%90%86

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する