[理工] 離散 可數不可數

[clonsey1314 (Clonsey)]

剛剛看到書上寫{0, 1}*字串是不可數
直覺的想法是所有01字串的個數是2的指數, 所以必為不可數

但是下面這題(交大104)又說0,1字串必定可以對應到一個正整數, 所以是可數

https://imgur.com/geofuUs
https://imgur.com/RUGo06M

如果0,1字串可以對應到一個正整數的話, 是可以onto對完所有正整數沒錯,
但例如01和001, 都會對到1, 這樣不是就不符合one-to-one?

所以到底0,1字串是可數還是不可數?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.163.181.227
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1512907185.A.8E5.html
※ 編輯: clonsey1314 (1.163.181.227), 12/10/2017 20:35:38
推 alan23273850: 你舉的兩個例子都是可數喔，你可以把字串長度當作基
→ alan23273850: 準，從長度1開始列，然後長度2、長度3，依此類推，
→ alan23273850: 然後依然所有字串都能獲得一個序號，所以是可數的
→ alan23273850: Ex. 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ..
→ outofyou: 對應到2和4
→ alan23273850: btw, 可不可數是看能不能把元素有條不紊的排成一列
→ alan23273850: 絕對不是看長度是不是指數次方
→ TMDTMD2487: {0,1}* 是可數集吧我印象中 @@
→ TMDTMD2487: 這題很難我記得我之前看到直接跳過
推 TMDTMD2487: 第二題 兩個都是program 都是01字串的集合 皆可數集
https://imgur.com/wCAkWUD
我是因為看到這題的詳解所以產生疑惑
他詳解說錯了嗎?
※ 編輯: clonsey1314 (1.163.181.227), 12/10/2017 21:55:24
→ TMDTMD2487: 抱歉我更正 我剛剛看了一些東西 他跟證明[0,1]不可數
→ TMDTMD2487: 的方法是一樣的
→ TMDTMD2487: 都是用那個對角線的方式證明的 所以{0,1}* 不可數呢
@@ 那那題交大104說"programs是01字串組成的集合所以可數"的又是?
※ 編輯: clonsey1314 (1.163.181.227), 12/10/2017 22:25:02
→ TMDTMD2487: 我可以確定program是可數的我剛剛查過了
→ TMDTMD2487: 不過他的解釋 看起來很ok 可是我感覺我可以用她的解釋
→ TMDTMD2487: 方式 去說{0,1}* 是可數的讓我困惑到現在XD
→ TMDTMD2487: https://goo.gl/HzL7Vn  你可以看看
→ TMDTMD2487: 他基本上是用可數集的聯集依然是可數的方式
→ TMDTMD2487: 然後長度為n的program是有限集(所以可數
→ TMDTMD2487: 所以把n=0到無限大都union起來 說這也是可數的
https://math.stackexchange.com/questions/568161/is-it-countable
剛也有查一下資料, 他說當字串長度有限的時候, 01字串是可數
方法也是跟你說的union無限多個可數集
所以{0, 1}*的字串長度無限就不是可數
證明用對角線論證法
source:
https://math.stackexchange.com/questions/338094/why-is-the-set-of-all-binary-sequences-not-countable

那所以program的字串長度有限的01字串囉? 是這樣嗎?
※ 編輯: clonsey1314 (1.163.181.227), 12/10/2017 22:50:58
※ 編輯: clonsey1314 (1.163.181.227), 12/10/2017 22:53:20
→ TMDTMD2487: 這我不懂 因為program是無限集 所以他union到無限長
→ TMDTMD2487: 的program才對(我的認知拉
→ TMDTMD2487: 可是union到無限長度的話就跟{0,1}*是一樣的東西
→ TMDTMD2487: 所以應該不是這樣(一片混亂
後來想想, program的長度應該是有限的, 如果有無限長的code還滿可怕的哈哈
然後programs的set為所有program(有限長度的01字串)無限union而成的, 所以是可數
目前的理解是這樣
※ 編輯: clonsey1314 (1.163.181.227), 12/10/2017 23:06:30
→ TMDTMD2487: 應該說any長度的set聯集再一起跟{0,1}*是不一樣的東西
→ TMDTMD2487: 看看有沒有人念語言的XD 我只能理解到這邊了
※ 編輯: clonsey1314 (1.163.181.227), 12/10/2017 23:09:45
→ TMDTMD2487: 考試的話這題已經有點偏了 所以可以跳過了
→ TMDTMD2487: 媽的交大上次還哪次考那個複雜度好一點的矩陣乘法
→ TMDTMD2487: 跳過都跳過
→ clonsey1314: 說的也是哈哈，感謝你陪我耗時間在這個東西上@@