• 締切済み
  • すぐに回答を!

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

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

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

  • 回答数5
  • 閲覧数1656
  • ありがとう数1

みんなの回答

  • 回答No.5

何をもって「対角線論法」と称するかという問題がありますね. 自然数の集合のベキ集合 P(N) にしろ,実数の集合 R にしろ,それが可算でないことを証明しようとしたら,何らかの形で対角線論法に訴える必要があります.「対角線論法によらない証明」というのはたぶん見かけの問題だけで,本質的に対角線論法を回避した証明はないと思います. 多くの数学書では,実数の10進無限小数表示を使った対角線論法で R が可算でないことを証明して,「ここで使った論法は対角線論法と呼ばれる」などと説明していると思います. しかし,10進無限小数表示を使うのは,あくまで「対角線論法を使った証明の,ひとつの例」でしかありません.「対角線論法といえば無限小数表示を使うもの」と考えているとしたら,それは,ひどく狭い解釈です. 理論計算機科学における停止問題(halting problem)の決定不可能性の証明や,数学基礎論におけるゲーデルの不完全性定理の証明で使われる手法も「対角線論法」と呼ばれますが,それらの証明には実数の無限小数表示は出てきません. #4 さんの回答では P(N) が可算でないことを経由して証明していますが,P(A) が A より濃度大であること(カントールの定理)の証明は,対角線論法そのものです. また,#3 さんの回答にある区間縮小法を使った証明も,広い意味で対角線論法と呼ぶべきものです. ==== なお,重箱の隅をつつくようで恐縮ですが,#3,#4 の証明について,#3 は2分割でなく3分割(最小番号の実数が第1区間に属せば第3区間を選択,さもなくば第1区間を選択),#4 の P(N) の R への埋め込みは2進小数でなく3進小数を使うほうが,テクニカルな問題を回避できて,初学者向けの説明としては無難かと思います. 藤田博司「魅了する無限」(技術評論社) では,「3分割」の区間縮小法を使った証明(これも本質的には対角線論法)がていねいに書かれています. 嘉田勝「論理と集合から始める数学の基礎」(日本評論社) では,「P(N) は可算でない」「P(N) から R への単射が存在する」の2段で証明していますが,前者の証明の方法について「対角線論法と呼ばれます」と明言しています(ちなみに,後者の証明では3進小数を使ってカントール集合に埋め込んでいます).

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

関連するQ&A

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

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

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

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

  • 可算無限集合と非可算無限集合の違いが分かりません。

    例えば、こういう問題のときそれぞれ可算無限集合と非可算無限集合のうちどっちですか? (1)0≦x≦1を満たす実数x (2)任意の自然数N (3)任意の実数R 回答よろしくお願いします。

  • 回答No.4

”実数の集合が非可算であること”は次のような証明も知られています。カントールは任意の集合Aとそのベキ集合P(A)の間には1対1対応は存在しないことを示しました。証明は例えば  メアリー・タイルズ著三浦雅弘訳「集合論の哲学」産業図書、p.71 区間[0,1]に含まれる実数の2進少数展開を考えれば自然数Nの ベキ集合P(N)と[0,1]に含まれる実数の間に1対1対応があることはすぐに分かるので、実数の集合は非可算であることになります。

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

  • 回答No.3
  • funoe
  • ベストアンサー率46% (222/475)

(命題) 閉区間の列[a1,b1]⊃[a2,b2]⊃・・・⊃[an,bn]⊃・・・ があって、bn-an→0のとき、各区間に共通に含まれる実数が唯一つ存在する。 を前提にします。 区間[0,1]の実数にすべて付番できたとします。 この区間を半分に分けた[0、1/2]、[1/2,1]のうち、最小の番号が付番された 実数を含まない方を選択します。 (このとき選択された区間には1番が含まれないので最小のものは2番以上です) 選ばれた区間を半分に分け、両方の区間の中で最小の番号が付番された実数を含まない方を選択します。 (このとき選択された区間の最小のものは3番以上です) 選ばれた区間を半分に分け、両方の区間の中で最小の番号が付番された実数を含まない方を選択します。 (このとき選択された区間の最小のものは4番以上です) この操作を繰り返したとき得られる区間縮小列は、冒頭の条件を満たすので 各区間に含まれる実数が1個決まります。 その実数に付番された番号がNとすると、 上記の操作(区間を半分にして新たな区間を選択する操作)のN+1回目 で選択された区間に含まれる最小のものがN+1であることに反します。

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

  • 回答No.2

カントールは最初1874年にこれを区間縮小法で証明し、後に対角線論法で証明したとされています。

参考URL:
http://www.teachersparadise.com/ency/ja/wikipedia/a/a_/a_a_a_a_a_a_a_e_c_e_.html

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

  • 回答No.1
  • rinkun
  • ベストアンサー率44% (706/1571)

可算でなければ非可算です。自然数(可算無限)と対等でなければ有限か非可算ですが、有限でないのは対角線論法以前に明らかでしょう。 別証明は知りません。おそらく一般に知られていないと思います。

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

関連するQ&A

  • 集合の濃度に関する質問です

    可算無限集合Aの濃度をα_0(アレフ0) R^nの濃度をα_1(アレフ1) (nは自然数) Aの冪集合の濃度を2^α_0(2のアレフ0乗?) ※ヘブライ語のアレフの代わりに、αを使って記述してます。 なので以下αはアレフと読むことにします。 このとき (1)α_0よりα_1のほうが"大きい"こと (2)α_0より2^α_0のほうが"大きい"こと の2つはわかったのですが、α_1と2^α_0ではどちらが大きいのですか? それとも2^α_0=α_1なのでしょうか? 私の記憶では、α_1はα_0の次に"大きい"濃度と定義されていたような気がしますが・・それだとα_0より大きくα_1より小さい濃度は存在してはいけないことになりませんか?(つまり、α_1>2^α_0の可能性はない) 来年度に数学科2年となる身なので、あまり高度な知識は持ち合わせていないです・・。すいません。 どなたか詳しい方がいらっしゃいましたら回答よろしくお願いします。 [補足] (1)については Aが可算(自然数全体の集合Nとの間に1対1かつontoな写像ができる)である一方で、Rは対角線論法により非可算なので、α_0よりα_1のほうが"大きい"としました。(RとR^nの濃度が等しいことの証明は省略します) (2)については Aの冪集合の濃度、つまり元の個数を、Aの各元を含むか含まないかを1と2に対応させることで、小数0.122111222121122・・・・・の総数へと帰着し、あとはこの小数全体に対して対角線論法を用いることで、α_0より2^α_0のほうが"大きい"としました。 「Aの各元を含むか含まないかを1と2に対応させる」とは、 たとえば、A={1,2}であればAの冪集合の濃度(個数)は2^2=4個ですが、これを 0,22⇔Φ(空集合) 0,12⇔{1} 0,21⇔{2} 0,22⇔{1,2} というように小数に対応させるということです。 "大きい"という言葉の定義をしてないのでこの表現が曖昧かもしれませんが、上記のようにして"大きい"かどうかを判断しました。

  • 2元生成の自由群は可算か?

    2元生成の自由群は可算か? バナッハタルスキーのパラドックスを本で読んで証明を追っています。 その途中、2元から生成された自由群(と同型な群)は可算であるから…、との表記が証明なしにありました。 これは正しいですか? 対角線論法と同じように以下のように考えました。 生成元をh,kとしたとき、可算濃度と仮定すると全ての元を e h k hh hk … と順番に並べることができます。 i番目の元のi文字目がhならk、何もない場合やkならh(i=1,2,…)と定めてできたものはすべての元と異なるので矛盾するように思うのですが… あるいは、可算の長さである元について、その選び方は2^(可算無限)となり、全体としても連続濃度になってしまうと思います。

  • 可算かどうか

    「XをN(自然数の集合)の有限部分集合全体の集合とするとき、|X|=アレフゼロ(可算濃度)となることを証明せよ」 を教えてください。 自然数Nと一対一対応もしくは、先頭から番号をつけていくことができるというような証明の仕方ではないのかなとは思うのですが、具体的な証明方法が思いつきません、教えてください。 よろしくお願いいたします。

  • 集合 濃度の問題

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

  • 全ての行列からなる集合の濃度は?

    対称行列は、縦ベクトルと横ベクトルの積で表すことができますから、 n次元ベクトルは、n次元平面と、同じ濃度 したがって、すべて対称行列からなる集合の濃度は、実数の濃度 というのは、わかります。 すべての行列の集合は、対称行列の冪集合と考えてられるのでしょうか? 対角線論法で、確認しようとしたのですが、よくわかりません。 アドバイス、お願いします。

  • 可算であることの証明

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

  • 位相 可算集合

    この問題の解答と途中式をおしえてください!! できれば全解をお願いします。 何度してもできません!! 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'=Φ

  • 位相 可算集合

    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

    Xを自然数全体集合Nの有限部分集合全体とするとき、|X|と可算濃度が同じである証明の仕方を、分かりやすく教えて下さい!

  • 位相 可算集合

    Xを非可算集合とし、AをXの可算な部分集合とする。このとき、XとX-Aが対等であるときを証明せよ。 この問題の解答と経過を教えてください!! おねがいします!!