※ 引述《triumphant10 (yu12510 )》之銘言：
: 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!
考慮首次出現 f(i)=0 的 i，記 n0=i
若f(i)≠0 for all i ，則記 n0 = -1
首次出現 f(i)=1 的 i，記 n1=i
若 f(i)≠1 for all i，記 n1=-1
n2 依以類推
即若 f(0)=0，f(1)=1，f(2)=2，則 n0=0，n1=1，n2=2
顯然 S 中的每個元素都對應一組 (n0,n1,n2)
且不同的元素對應不同的 (n0,n1,n2)
即存在函數 g:S → ({-1}∪N)^3
g 是 injective，所以 #S≦(#N)^3
因此 S is countable.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.238.207.61
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1540909286.A.5D2.html