作者pentiumevo (神秘數學組織SIGMA)
看板Math
標題[分析] 「存在不可數集」的證明
時間Sat Jul 9 21:43:43 2011
範圍是點集拓樸
首先列出我看的書上的定理（基本跟Munkres沒多大差別）
定理1.7.3 集合X可數 若且唯若 存在從正整數集Z+到X的onto映射
定理1.7.6 設X是一個集合，Y＝{0,1}，記Y^X是X到Y的所有映射的集合
則存在從X到Y^X的1-1映射（injective），但不存在從X到Y^X的的一一映射
（bijection）
-------------------------------------問題開始--------------------------------
書本上說
推論1.7.7 存在不可數集
證明：在定理1.7.6中，令X為正整數集Z+，Y={0,1}，則由定理1.7.6知{0,1}^Z+是不
可數集。 □
我想不通怎麼由定理1.7.6知道這結果
目前我已知道
（1） 存在從Z+到{0,1}^Z+的1-1映射
（2） 不存在從Z+到{0,1}^Z+的一一映射
但我沒辦法推出不存在從Z+到{0,1}^Z+的onto映射，也就不能用定理1.7.3證明{0,1}^Z+
這玩意兒是不可數。
請各位幫幫忙，謝謝。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.233.5.242
1F：→ wickeday :diagonal argument 07/09 21:49
不，我不要用對角論證法，我想直接用定理，麻煩了
※ 編輯: pentiumevo 來自: 125.233.5.242 (07/09 21:54)
2F：推 jacky7987 :沒有Z+ 到{0,1}^{Z+}的bijective函數 07/09 22:35
3F：→ jacky7987 :可數的定義是從存在bijective function 從N-->X 07/09 22:36
j大不好意思，可以請您再講清楚些嗎？我看不大懂...
※ 編輯: pentiumevo 來自: 125.233.5.242 (07/09 22:38)
4F：→ jacky7987 :Definition X is said to be countable if there 07/09 23:08
5F：→ jacky7987 :exists a bijective function f:N--->X 07/09 23:08
剛剛在洗澡時，我想出來了。
我用的這本書對於可數的定義是：
若集合X與正整數集Z+間有1-1映射存在，則稱X是可數的
這定義比較廣，因為這樣連有限集也算是可數的
此時易證以下事實：
當X是無限集，X是可數的若且唯若X與Z+間存在一一映射
回來原來問的問題
現在要證明{0,1}^{Z+}是不可數，我們要先確認這集合是無限集
因{0,1}^{Z+}＝{f|f:Z+ → {0,1}}
從中可以取得一個函數序列{f_n}
f_n的取法是：
0 x!=n
f_n (x) =
1 x=n
那麼{f_n}是無限集。而再由定理1.7.3知{0,1}^{Z+}與Z+間不存在一一映射，那麼
{0,1}^{Z+}就是不可數的。
※ 編輯: pentiumevo 來自: 125.233.5.242 (07/09 23:20)
6F：推 jacky7987 :By thm 1.7.6 there is no bijective function 07/09 23:11
7F：→ jacky7987 :from N to {0,1}^N, hence {0,1}^N is uncountable 07/09 23:12
8F：推 jacky7987 :N就是Z+阿XD 07/10 00:02
9F：→ jacky7987 :這樣想沒錯:) 07/10 00:03
10F：推 Lindemann :這不就還是對角線法的精神嗎?XD 07/10 01:40