作者ERT312 (312)
看板Math
标题Re: [其他]Prove Countable or Uncountable
时间Tue Oct 30 22:21:23 2018
※ 引述《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://webptt.com/cn.aspx?n=bbs/Math/M.1540909286.A.5D2.html