看板 Math 關於我們 聯絡資訊
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
Ricestone : 對每一個n來說,函數共有C(n+2,2)+C(n+1,1)+C(n,0) 10/30 21:35
Vulpix : Yes. 10/30 21:35
Ricestone : 可數,所以總和是countable個countable,所以 10/30 21:35
Ricestone : countable個吧 10/30 21:36
Ricestone : 我錯了,我這樣寫不是總和,而是上限集... 10/30 22:30
Vulpix : 值域共有7種可能。一元值域的函數總共只有三個。 10/30 22:32
Vulpix : 二元值域:較小的值出現有限次數,數它。例如值域= 10/30 22:33
Vulpix : {0,1},計算#{x|f(x)=0},此數有限,所以值域={0,1} 10/30 22:35
Vulpix : 的f跟N一樣多。同理,值域={0,1,2}的跟N^2一樣多。 10/30 22:36
Vulpix : 7個頂多可數集的互斥聯集仍然可數。 10/30 22:36
Ricestone : 如果能這樣寫,那我那樣寫是不是也一樣意思? 10/30 22:47
Ricestone : 因為我是直接寫出每個n會有多少函數 10/30 22:47
Ricestone : 感覺還是不太行... 10/30 22:58
Vulpix : 你是說{1,2,...,n}→{0,1,2}的遞增函數個數? 10/30 23:00
Ricestone : 嗯 10/30 23:00
Ricestone : 我那樣應該是從0開始,不過應該沒差 10/30 23:01
Vulpix : 仔細處理過的話,或許可行吧。但寫起來可能繞遠路。 10/30 23:02
Ricestone : 對,我剛剛就是想到後面處理好像更麻煩 10/30 23:02
Vulpix : 因為x夠大的時候就不重要了,f早已經是個常數。 10/30 23:03
Vulpix : 所以 #S=lim #{g|g:{1,2,...,n}→{0,1,2},g遞增} 10/30 23:05
ERT312 : 令gn=#{g|g:{1,2,...,n}→{0,1,2},g遞增} 10/30 23:15
ERT312 : 則#S=Σgn (n∈N) ≦ #N +#N+.....(+#N terms)=#N 10/30 23:18
Ricestone : 這個Σ算是指聯集嗎? 10/30 23:22
ERT312 : Cardinal numbers 的連加 10/30 23:24
Ricestone : 啊,我是不是只要再多說那是每一個n之後都變常數的 10/30 23:25
Ricestone : 函數,這樣我就可以說是countable 10/30 23:26
Ricestone : 那這樣的確是總和沒錯 10/30 23:26
Ricestone : 應該還是有多數,不過反正總和是countable 10/30 23:28
Ricestone : *n之後都變常數的函數個數 10/30 23:34
ERT312 : 對,其實只要f終究是常數函數,遞增這個條件可以拿 10/30 23:36
ERT312 : 掉,S一樣可數 10/30 23:36
Ricestone : 謝謝各位! 10/31 00:22
Vulpix : 關於n的那些函數可以塞進n+1的,所以我才寫lim。 10/31 02:06
Vulpix : 隨著n增加,S裡面的任一個f總有一天都會被數到。 10/31 02:07
alan23273850: 這題484台大電機離散ㄉ作業 10/31 08:13
ERT312 : @Vulpix 喔喔 原來你是要讓g_(n+1)包含g_n 10/31 08:36
ERT312 : 這樣集合取即限跟做聯集意思一樣,但是對基數取極限 10/31 08:37
ERT312 : 這部分我覺得會出問題 10/31 08:37
Vulpix : 嗯,對,其實lim只能得到∞。(counting measure) 10/31 12:56
Vulpix : 那個寫法當然有很不嚴謹的地方,實際操作上都是寫成 10/31 12:57
Vulpix : Σ來迴避。 10/31 12:57
Vulpix : 不過我認為即使在card.下,x_n≦a => lim x_n ≦a 10/31 13:03
Vulpix : 應該也是對的。 10/31 13:03
Vulpix : 不過lim要重新找定義是麻煩,大概是在基數上找topo. 10/31 13:07