• ベストアンサー
  • すぐに回答を!

可算かどうか

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

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

  • 回答数3
  • 閲覧数485
  • ありがとう数4

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

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

加算ではなく「可算」でOKです. これは``countable''の訳語です. 加算だとむしろ``additive''だけども一般的ではないですな. それと「アレフゼロ」も「濃度」でOK. 可算無限集合の濃度(「基数」というべきか)を 「アレフゼロ」とするわけです. 「可算濃度」といってしまうと確かに問題なので 「可算無限濃度」ということの方が正確ですね. #大抵は自明なので,無限を略することもないわけではないけども #ややこしい文脈・有限を包含する文脈もあるので注意 さて本題. XはNの有限部分集合の全体ですよね. Xを 要素0個の連中,1個の連中,2個の連中・・・・ とわけていきます. この段階で,Xはアレフゼロ個分のグループに分割されます. そして,0以外の自然数kに対して 要素k個のグループは,必ずアレフゼロ個です 例: 1個の連中:{1},{2},{3},・・・・ 2個の連中:{1,2},{1,3},{2,3},・・・ という具合(これをまじめに証明するのは,ご自分でどうぞ). よって,アレフゼロの集合がアレフゼロだけあるわけだから 全体はアレフゼロです. 細かいところは自分で穴埋めしてください. 基本は「Nとの全単射を構築」することですが, 何でもかんでも写像を構築するわけでもないのです.

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

質問者からの補足

わかりやすい回答をありがとうございます。 なるほど、非常によくわかりました。 無理やり写像にこじつけなくても、ある規則にしたがって並べたらどうなるかということを論述していいんですね。 あとは自分でなんとかがんばってみます。 ありがとうございました。

関連するQ&A

  • 可算濃度2

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

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

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

その他の回答 (2)

  • 回答No.3
  • zk43
  • ベストアンサー率53% (253/470)

A∈Xを取ると、Aには有限個の自然数が含まれているので、Aに含まれる 要素全体の和は自然数である。 よって、 f:X→Nを、f(A)=Aに含まれる要素全体の和 によって定義すると、f(X)はNの部分集合となる。 (実際にはf(X)はNに一致する。) n∈Nに対して、f(A)=nとなるA∈Xはいくつあるかを考えると、nをいく つかの自然数の和として表す仕方の総数だけあり、それは有限個であ る。 X=f^(-1)(1)∪f^(-1)(2)∪f^(-1)(3)∪…∪f^(-1)(n)… となっており、交わりはなく、各f^(-1)(k)は有限個の要素から成る。 具体的には、 f^(-1)(1)={{1}} f^(-1)(2)={{2}} f^(-1)(3)={{3},{1,2}} f^(-1)(4)={{4},{1,3}} ・・・ となっているから、順番に自然数を割り振っていくことができる。

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

質問者からのお礼

詳しい回答ありがとうございます。 なるほど、このようなやり方もあるのですね。 元の並べ方は、何通りもあって、とにかく数え上げられることが重要で、それが示せればいいということがわかりました。 ありがとうございました。

  • 回答No.1
noname#50894
noname#50894

>「XをN(自然数の集合)の有限部分集合全体の集合とするとき、 >|X|=アレフゼロ(可算濃度)となることを証明せよ」 “アレフゼロ”とは、加算無限集合ではなかったですか? 1.XからNへの単射な写像が存在すれば、Xは加算集合である。 2.NからXへの全単射な写像が存在すれば、Xは加算無限集合である。 【Xの濃度はNと同じである】 (事例)Xが偶数全体の集合であれば、 写像f:N→X[f(n)=2n(n∈N)]は全単射な写像になる。 従って、偶数全体の集合は、加算無限集合。

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

質問者からのお礼

さっそくの回答ありがとうございました。 アレフゼロはおそらく、可算基数≒Nと同じ基数(要素数)だったと理解しています。

関連するQ&A

  • 可算であることの証明

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

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

    可算無限集合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

      任意の集合はそのべき集合を作り続けることによって、無限に増大する濃度を持つ集合列が生成できることは証明されています。 例えばこれを可算集合から開始した場合、 可算集合の濃度=アレフ0 可算集合のべき集合の濃度=アレフ1 可算集合のべき集合のべき集合の濃度=アレフ2 可算集合のべき集合のべき集合のべき集合の濃度=アレフ3         ・         ・         ・         ・ 以下無限に続く。 このように無限に増大する濃度を持つ集合列アレフ0、アレフ1、アレフ2、・・・・が生成されます。 また同様にして連続体から開始した場合、 連続体の濃度=ベート0 連続体のべき集合の濃度=ベート1 連続体のべき集合のべき集合の濃度=ベート2 連続体のべき集合のべき集合のべき集合の濃度=ベート3         ・         ・         ・         ・ 以下無限に続く。 このように無限に増大する濃度を持つ集合列ベート0、ベート1、ベート2、・・・・が生成されます。 さて質問です。 1. 任意の自然数nに対して適当な自然数mを取ることにより、ベートn=アレフmを成立させることが出来ますか。 2. 任意の集合に対しその濃度をAとするとき、適当な自然数mやnを取ることによりA=アレフm、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'=Φ

  • 位相 可算集合

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

  • 位相 可算集合

    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}とすればよい。 と使えばいい思っているんですが、どのようにしたら いいかわかりません!この先の解答を教えてください!! 経過もお願いします!!

  • 濃度を求める問題

    次の集合 A = {S⊂R | Sは高々可算 } の濃度を求めよ、という問題の解き方が分からず困っています。 以下、Nを連続濃度(アレフ)とします。 (アレフが入力できないので…すいません。) 写像 f :R→A , x ↦ {x} は単射なので、N≦ |A| である事が分かります。 さらにA⊂2^Rなので、|A|≦2^Nである事も分かります。 この後、どうしたらよいのかが分かりません。 Sが有限の場合なら解けるのですが、可算となると写像をどのように作ればいいかがピンときません。 濃度はNか2^Nになるのだと思いますが… 分かる方がいましたら回答よろしくお願いします。

  • 自然数の濃度

    問、Xを自然数全体の集合Nの部分集合全体とするとき、   |X|>|N| (||は濃度をあらわします。)を証明せよ。 この問の証明を教えてください。 解法として、 1).|X|≧|N|が成り立つ。 2).|X|≠|N|である。 を示したいのですが、2)が分かりません。 XがNの部分集合だったら、全射にならないことは直観でも分かるのですが、 XがNの部分集合全体の時はどう考えればいいのでしょうか。

  • Q.Xを自然数全体の集合Nの部分集合とするとき、|X|>アレフゼロを証

    Q.Xを自然数全体の集合Nの部分集合とするとき、|X|>アレフゼロを証明せよ。 以下、ネットでのどなたかの回答を参考に、私なりにテキストを読み返すなどして解釈して、作成しました。 テスト問題としての解答として、 「修正および補足」などをお願いします。 A. |X|=|N|と仮定すると、NからXへの全単射fが存在する。 ∀n∈N ⇒ f(n)=M, ∃M∈X ∀M∈X ⇒ f(n)=M, ∃n∈N つまり 1 ←→ M1 2 ←→ M2 ・ ・ n ←→ Mn ・ ・ このとき、左右の対応関係について、属するか属さないかを分類でき、 N∈Mn または n?Mnとなる。 次に集合M'を以下のように定義する。 (1) n∈Mnのときnを要素としない。 (2) n?Mnのときnを要素とする。 この集合は一意に決まり、また自然数だけを要素に持つ集合となり、明らかに自然数の部分集合を意味する。 つまりM'∈Xであるが、このM'は定義により、上の対応関係からは外れている。 これはNとXとが全単射できたという仮定に矛盾する。 |X|≠アレフゼロ また、写像g:N→Xをgn={n}とすると、これは単射であるから |N|=アレフゼロ≦|X| 以上より、アレフゼロ<|X|

  • 離散数学の問題について質問させていただきます。

    離散数学の問題について質問させていただきます。 以下の2つの問題がどうしても分かりません。 解答・解説ともに手元に無く、大変困っております。急を要しております。 どうか力をお貸し下さい。よろしくお願いします。 (1)可算集合の高々可算個の和集合が可算集合であることの証明 (2)Nを自然数全体の集合(N = {1,2,3…})としたとき、Nのべき集合すなわちすべての部分集合の集合は、可算集合でないことの証明

専門家に質問してみよう