• ベストアンサー
  • 困ってます

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

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 を だいたい可算無限の意味がよくわかりません。 お願いします。

共感・応援の気持ちを伝えよう!

  • 回答数3
  • 閲覧数674
  • ありがとう数2

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

  • ベストアンサー
  • 回答No.3

かりに0と1の間のすべての数が、  1:0.123455343……  2:0.2434293335……  3:0.746943489……  4:0.34235255……  :  : のように番号付けて並べられたとします。しかしこのリストの中にない数を必ず構成することができます。上のリストの中のn番目の数の小数第n桁の数字を取り出すと、  1:1  2:4  3:6  4:3  :  : となります。そこで第n桁の数字がこれとは異なるように、例えば1多い数字で置き換えて  0.2574…… という数を考えると、これは上のリストの中の数のどれとも異なることになります。これが「今最後に作った実数は、それぞれ小数点以下第n位の数字が番号nの実数とは異なっている。ということは、∞番まで自然数を振ったとしても、最低こうやって作った実数はもれていることになる。」ということです。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

ありがとうございます。とてもわかりやすかったです。

関連するQ&A

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

    以下、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(有理数全体)では成り立たないことを教えてください。

  • 可算無限についてお願いします

    集合Xが有限集合の時、 ∪{Xの、要素数kの部分集合を全て集めた集合}  (k=0,1,2…|X|) は、Xのべき集合(2^X)と同じものですよね。 でも集合Xが有限集合ではなく、自然数の集合Nであった場合、 ∪{Nの、要素数kの部分集合を全て集めた集合}  (k=0,1,2…) は可算無限であり、Nのべき集合(2^N)は非可算無限だと聞きましたが、 その違いはいったいなぜ起こるのですか? ※ 集合Y(≠∅ )に対し f:Y→2^Y となる全射が存在しないので、X=Nとすることで2^Nが非可算である事は理解しています。

  • 有理数集合の濃度は非可算?!

    有理数集合の濃度は非可算?! 有理数集合Qの濃度は可算ですが、以下のように考えたところQ(の部分集合)が非可算無限集合になってしまいました。 どこが誤りかご教授願います。 正の有理数は素数のベキを用いて 2^α×3^β×…(α,β,…∈Z) で一意的に表される。 素数の個数は可算無限個なので Q+とZの可算無限個の直積が一対一対応する。 このときZも可算無限集合なので、可算無限集合の可算無限直積で非可算無限集合になる。 よってQ+は非可算無限集合である。

その他の回答 (2)

  • 回答No.2

野矢茂樹さんが『無限論の教室』という本を出していらっしゃいます。加算無限の意味から対角線論法まで、言葉で分かりやすく解説されています。数式による厳密な証明とは別のアプローチで取り敢えず全体的な意味を把握するというのも悪くないかもしれません。(ただ、数学ではなく数学の哲学になってしまうかもしれませんが)

共感・感謝の気持ちを伝えよう!

質問者からのお礼

ありがとうございます。

  • 回答No.1

可算無限集合というのは、自然数の集合との間に全単射が存在するような集合です。 全単射 ψ: X → 2^X が存在したとします。X の部分集合 A をa∈Xに対して、  a∈A if a ∈/ ψ(a)   a∈/ A if a ∈ψ(a) で定義します。ここで∈/は∈の否定を表わすものとします。すると、A ∈ 2^X であって、ψ は全射だから、ある x に対して A = ψ(x) とならなければならないことになります。そこでx ∈ ψ(x) とすると x ∈ A。ところがAはx∈ψ(x)のときx∈/ Aとなるように構成されていたのだからこれは矛盾。同様にx ∈/ ψ(x)としても矛盾が生じるから全単射は存在しないことになります。

共感・感謝の気持ちを伝えよう!

質問者からの補足

ありがとうございます。 ちょっと対角線論法をよく理解してなくて、 http://www.geocities.co.jp/WallStreet/1356/kuru/EVILMATH.html を読んでいるのですが、 そこの、 「今最後に作った実数は、それぞれ小数点以下第n位の数字が番号nの実数とは異なっている。ということはだ、∞番まで自然数を振ったとしても、最低こうやって作った実数はもれていることになる。というわけで、どうやっても「もれなく番号がふれない」、実数の方があまる、ということは、自然数より実数の方が多い(濃い)訳だよ。 」というところがわかりません。 特に、「今最後に作った実数は、それぞれ小数点以下第n位の数字が番号nの実数とは異なっている。ということはだ、∞番まで自然数を振ったとしても、最低こうやって作った実数はもれていることになる。」のところです。 お願いします。

関連するQ&A

  • 無限集合の定義で

    ∃f:全単射 such that f:A→B (但し、BはAの真部分集合) の時、Aを無限集合と言うのがデデキントの無限集合の定義だと思いますが 非可算集合の時にも(例えば実数体)このような全単射写像はするのでしょうか?

  • 無限集合に関することです。

    無限集合に関することです。 自然数全体を可算無限個の互いに交わらない集合A1,A2,A3・・・(どのAkも可算無限集合)の和として表わされることを示したいのですがどうすれば良いですか? 可算無限集合は自然数全体の集合との間に1対1対応の関係がある集合のことなのに、自然数全体を互いに交わらない集合で示せるのでしょうか?

  • 1 と 2 の間の ほとんどすべての q に対し、"非可算無限" の

    1 と 2 の間の ほとんどすべての q に対し、"非可算無限" の 『1 の q-進表現』が存在する http://ja.wikipedia.org/wiki/0.999... を読んでいて、次のようなことが書かれていました。 0.999...=1 に相当する結果を他の基数にも適用することができる。例えば 2 を基数とする(二進法)と 0.111...=1 であり、3 を基数とする(三進法)と 0.222...=1 である。 1 の別表現は、非整数を基数としても現れる。例えば、黄金比を基数とすると、2つの標準的表示は 1.000... と 0.101010... であるが、他にも0.11, 0.1011, 0.101011 のように隣接する "1" を含む無数の表現がある。一般的に、1 と 2 の間の ほとんどすべての q に対し、"非可算無限" の 『1 の q-進表現』が存在する。 最後の部分がどうしてなのかがわかりません。詳しく説明されているサイトなどがあれば教えてください。

  • 実数の濃度(連続体濃度)についての問題の添削をおねがいします。対角線論法をつかってます。

    問: 任意の写像 f:N→R につき、f は全単射でないことを背理法を使わず証明せよ 添削していただきたいのは上の問です 背理法に引っかかっていないのかどうかが自分には分かりません *のように、並べると――等とすることは可算集合であることを仮定することになってしまいませんか? 解答:  開区間(0,1)をとると 全単射 (0,1)→R x |→tan[π(x-1/2)] がつくれるので、(つくれてますか??) |(0,1)| = |R| よって、g:N→(0,1) が 全単射でないことを示せばよい 各実数 g(n) を10進法によって無限小数に展開して (ただし、有限小数も無限小数で表す) g(n) = 0.a(n1)a(n2)a(n3)… と表すとする ( a(ni)は0から9までの整数 ) 全て並べると……* g(1) = a(11)a(12)a(13)… g(2) = a(21)a(22)a(23)… g(3) = a(31)a(32)a(33)… … ここで a(11)≠b(1), a(22)≠b(2), … となる数列をとれば 0.b(1)b(2)b(3)… という実数は g(1), g(2), … のどれとも異なる 従って g(n) の値域に入らない実数があるため、 gは全射でない  ■ よろしくおねがいします。

  • 位相 可算集合

    Aを可算集合とする。このとき、次の条件(1)(2)(3)を満たすAの 部分集合族{A_n|n∈N}(Nは自然数とする)が存在することを証 明せよ。 (1)すべてのn∈NについてA_nは可算集合である。 (2)A=∪_n∈N(A_n) (3)n≠n'⇒A_n∩A_n'=Φ よくわかりません!! f:N×N→N の全単射とする。 A_n={f(n,m)|m∈N}とすればよい。 と使えばいい思っているんですが、どのようにしたら いいかわかりません!この先の解答を教えてください!! 経過もお願いします!!

  • 可算であることの証明

    可算についてなのですが、次の2つがどうしても証明出来ません。 1.可算集合の無限部分集合は可算である 2.有理数a,bを端点とする開区間(a,b)全体の集合は可算である 一応濃度、可算集合については一通り勉強したのですが…。 言っている事はなんとなくわかるのですが、自分でいざ問題を解いてみる(証明してみる)と何をどう書いてよいのやらまったくのお手上げです。 きちんと理解できていないのが原因だと思うのですが、いろいろな本を読み漁ってもこの”集合論”という分野、いまいちピンときません。 どうか回答のほどよろしくお願いします。

  • "無理数全体の集合から実数全体への全単射が存在する"の証明の説明をお願いします。

    次の問題の解答で分からないところがあるので説明をしてもらいたいです。 問: 無理数全体の集合からRへの全単射が存在することを証明せよ 解: R-Q から R への全単射の存在を示せばよい R-Q は無限集合であるから、可算部分集合 A が存在する ここで Q は可算集合なので、A∪Q は可算集合 よって全単射 f: A→A∪Q が存在するので 関数 g:R-Q →Rを     g(x)= { x (x∈R-A)         〔 f(x) (x∈A) と定義すると g は全単射である ■ 最後のところで、なぜgを上のように定義すると全単射になるのかがわかりません。 よろしくおねがいします。

  • 「集合Sの真部分集合S'からSへ全単射写像が存在する時、Sを無限集合という」を使ってのR:無限の証明は?

    無限集合の定義は 「集合Sの真部分集合S'からSへ全単射写像が存在する時、Sを無限集合という」 だと思います。 NやQやZは無限集合であることはわかりますが、 R(実数の集合)が無限集合であることは上の定義から導く事は可能なのでしょうか? N⊂Rで 「無限集合を含む集合は無限集合である」 という命題からRは無限集合と導く他ないのでしょうか?

  • ベルンシュタインの定理の証明について(集合論 Wikipedia)

    集合の勉強をしているのですが、 ベルンシュタインの定理の証明が分からずに困っています。 参考書として「集合・位相入門 松坂和夫著」を使っているのですが そこに載っている証明法が理解できず、ネットで調べてみた所、Wikipediaに簡単そうな証明法が出ていたので、とりあえずこちらから理解しよう思ったのですが、こちらもまた理解できずに困っています。 http://ja.wikipedia.org/wiki/%E3%83%99%E3%83%AB%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E3%81%AE%E5%AE%9A%E7%90%86 理解できない箇所は2箇所で、 まず h(x)=  f(x) xがCの元の時     g-1(x) xがCの元でない時 の部分で、 f(x)とg-1(x)は同じもののような感じがするのですが、 どこが違うのかということです。 もう1箇所は g-1(C)=g-1(C/C0)=f(C) の部分です。 よろしくお願いします。    

  • 福祉の充実した国家での問題点は?

    福祉の充実した国には、 フィンランド ・ デンマーク ・ ノルウェー ・ スウェーデン がありますが、 こうした国が国内で抱えている問題にはどんなものがあるのでしょうか? 各国ごとに詳しく教えて下さると助かります。 参考 http://ja.wikipedia.org/wiki/%E7%A6%8F%E7%A5%89%E5%9B%BD%E5%AE%B6%E8%AB%96#.E7.A6.8F.E7.A5.89.E3.83.AC.E3.82.B8.E3.83.BC.E3.83.A0.E8.AB.96 http://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%A6%E3%82%A7%E3%83%BC%E3%83%87%E3%83%B3#.E7.A6.8F.E7.A5.89 http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%B3%E3%83%A9%E3%83%B3%E3%83%89 http://ja.wikipedia.org/wiki/%E3%83%8E%E3%83%AB%E3%82%A6%E3%82%A7%E3%83%BC http://ja.wikipedia.org/wiki/%E3%83%87%E3%83%B3%E3%83%9E%E3%83%BC%E3%82%AF

専門家に質問してみよう