[其他]Prove Countable or Uncountable

看板Math作者 (yu12510 )時間7年前 (2018/10/30 21:16), 編輯推噓1(1推 0噓 43→)
留言44則, 4人參與, 7年前最新討論串1/2 (看更多)
Let S be the set of non-decreasing functions from N to {0,1,2} In other words, S = {f:N → {0,1,2}|f(i) <= f(i+1) for every i} Is S coutable ? How do I prove it ? Thanks! -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.45.90.225 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1540905417.A.CFE.html
→
10/30 21:35, 7年前 , 1F
對每一個n來說，函數共有C(n+2,2)+C(n+1,1)+C(n,0)
10/30 21:35, 1F
→
10/30 21:35, 7年前 , 2F
Yes.
10/30 21:35, 2F
→
10/30 21:35, 7年前 , 3F
可數，所以總和是countable個countable，所以
10/30 21:35, 3F
→
10/30 21:36, 7年前 , 4F
countable個吧
10/30 21:36, 4F
→
10/30 22:30, 7年前 , 5F
我錯了，我這樣寫不是總和，而是上限集...
10/30 22:30, 5F
→
10/30 22:32, 7年前 , 6F
值域共有7種可能。一元值域的函數總共只有三個。
10/30 22:32, 6F
→
10/30 22:33, 7年前 , 7F
二元值域：較小的值出現有限次數，數它。例如值域=
10/30 22:33, 7F
→
10/30 22:35, 7年前 , 8F
{0,1}，計算#{x|f(x)=0}，此數有限，所以值域={0,1}
10/30 22:35, 8F
→
10/30 22:36, 7年前 , 9F
的f跟N一樣多。同理，值域={0,1,2}的跟N^2一樣多。
10/30 22:36, 9F
→
10/30 22:36, 7年前 , 10F
7個頂多可數集的互斥聯集仍然可數。
10/30 22:36, 10F
→
10/30 22:47, 7年前 , 11F
如果能這樣寫，那我那樣寫是不是也一樣意思？
10/30 22:47, 11F
→
10/30 22:47, 7年前 , 12F
因為我是直接寫出每個n會有多少函數
10/30 22:47, 12F
→
10/30 22:58, 7年前 , 13F
感覺還是不太行...
10/30 22:58, 13F
→
10/30 23:00, 7年前 , 14F
你是說{1,2,...,n}→{0,1,2}的遞增函數個數？
10/30 23:00, 14F
→
10/30 23:00, 7年前 , 15F
嗯
10/30 23:00, 15F
→
10/30 23:01, 7年前 , 16F
我那樣應該是從0開始，不過應該沒差
10/30 23:01, 16F
→
10/30 23:02, 7年前 , 17F
仔細處理過的話，或許可行吧。但寫起來可能繞遠路。
10/30 23:02, 17F
→
10/30 23:02, 7年前 , 18F
對，我剛剛就是想到後面處理好像更麻煩
10/30 23:02, 18F
→
10/30 23:03, 7年前 , 19F
因為x夠大的時候就不重要了，f早已經是個常數。
10/30 23:03, 19F
→
10/30 23:05, 7年前 , 20F
所以 #S=lim #{g|g:{1,2,...,n}→{0,1,2},g遞增}
10/30 23:05, 20F
→
10/30 23:15, 7年前 , 21F
令gn=#{g|g:{1,2,...,n}→{0,1,2},g遞增}
10/30 23:15, 21F
→
10/30 23:18, 7年前 , 22F
則#S=Σgn (n∈N) ≦ #N +#N+.....(+#N terms)=#N
10/30 23:18, 22F
→
10/30 23:22, 7年前 , 23F
這個Σ算是指聯集嗎？
10/30 23:22, 23F
→
10/30 23:24, 7年前 , 24F
Cardinal numbers 的連加
10/30 23:24, 24F
→
10/30 23:25, 7年前 , 25F
啊，我是不是只要再多說那是每一個n之後都變常數的
10/30 23:25, 25F
→
10/30 23:26, 7年前 , 26F
函數，這樣我就可以說是countable
10/30 23:26, 26F
→
10/30 23:26, 7年前 , 27F
那這樣的確是總和沒錯
10/30 23:26, 27F
→
10/30 23:28, 7年前 , 28F
應該還是有多數，不過反正總和是countable
10/30 23:28, 28F
→
10/30 23:34, 7年前 , 29F
*n之後都變常數的函數個數
10/30 23:34, 29F
→
10/30 23:36, 7年前 , 30F
對，其實只要f終究是常數函數，遞增這個條件可以拿
10/30 23:36, 30F
→
10/30 23:36, 7年前 , 31F
掉，S一樣可數
10/30 23:36, 31F
→
10/31 00:22, 7年前 , 32F
謝謝各位！
10/31 00:22, 32F
→
10/31 02:06, 7年前 , 33F
關於n的那些函數可以塞進n+1的，所以我才寫lim。
10/31 02:06, 33F
→
10/31 02:07, 7年前 , 34F
隨著n增加，S裡面的任一個f總有一天都會被數到。
10/31 02:07, 34F
推
10/31 08:13, 7年前 , 35F
這題484台大電機離散ㄉ作業
10/31 08:13, 35F
→
10/31 08:36, 7年前 , 36F
@Vulpix 喔喔 原來你是要讓g_(n+1)包含g_n
10/31 08:36, 36F
→
10/31 08:37, 7年前 , 37F
這樣集合取即限跟做聯集意思一樣，但是對基數取極限
10/31 08:37, 37F
→
10/31 08:37, 7年前 , 38F
這部分我覺得會出問題
10/31 08:37, 38F
→
10/31 12:56, 7年前 , 39F
嗯，對，其實lim只能得到∞。(counting measure)
10/31 12:56, 39F
→
10/31 12:57, 7年前 , 40F
那個寫法當然有很不嚴謹的地方，實際操作上都是寫成
10/31 12:57, 40F
→
10/31 12:57, 7年前 , 41F
Σ來迴避。
10/31 12:57, 41F
→
10/31 13:03, 7年前 , 42F
不過我認為即使在card.下，x_n≦a => lim x_n ≦a
10/31 13:03, 42F
→
10/31 13:03, 7年前 , 43F
應該也是對的。
10/31 13:03, 43F
→
10/31 13:07, 7年前 , 44F
不過lim要重新找定義是麻煩，大概是在基數上找topo.
10/31 13:07, 44F
‣ 更多 triumphant10 的文章
文章代碼(AID): #1Rs5d9p- (Math)
‣ 更多 triumphant10 的文章
文章代碼(AID): #1Rs5d9p- (Math)