可算かどうか

「ＸをＮ（自然数の集合）の有限部分集合全体の集合とするとき、|Ｘ|=アレフゼロ（可算濃度）となることを証明せよ」
を教えてください。

自然数Ｎと一対一対応もしくは、先頭から番号をつけていくことができるというような証明の仕方ではないのかなとは思うのですが、具体的な証明方法が思いつきません、教えてください。
よろしくお願いいたします。

No.2 ベストアンサー 回答者： kabaokaba 回答日時： 2008/01/20 11:33

加算ではなく「可算」で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との全単射を構築」することですが，
何でもかんでも写像を構築するわけでもないのです．

この回答への補足

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

補足日時：2008/01/20 21:07

No.3 回答者： zk43 回答日時： 2008/01/20 14:23

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}}
・・・
となっているから、順番に自然数を割り振っていくことができる。

この回答へのお礼

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

お礼日時：2008/01/20 21:12

No.1 回答者： noname#50894 回答日時： 2008/01/20 06:33

>「ＸをＮ（自然数の集合）の有限部分集合全体の集合とするとき、

>|Ｘ|=アレフゼロ（可算濃度）となることを証明せよ」
“アレフゼロ”とは、加算無限集合ではなかったですか？

1.ＸからＮへの単射な写像が存在すれば、Ｘは加算集合である。

2.ＮからＸへの全単射な写像が存在すれば、Ｘは加算無限集合である。
【Ｘの濃度はＮと同じである】
（事例）Ｘが偶数全体の集合であれば、
写像f：Ｎ→Ｘ［f(n)=2n（n∈Ｎ）］は全単射な写像になる。
従って、偶数全体の集合は、加算無限集合。

この回答へのお礼

さっそくの回答ありがとうございました。

アレフゼロはおそらく、可算基数≒Ｎと同じ基数（要素数）だったと理解しています。

お礼日時：2008/01/20 21:11