从$ℕ$到$ℕ$的递增函数是不可数的

hbghlyj

从$ℕ$到$ℕ$的函数是不可数的(ProofWiki).
从$ℕ$到$ℕ$的递减函数是可数的(MSE).
如何证明“从$ℕ$到$ℕ$的递增函数是不可数的”?
使用上面的证明$g(n) = f_n(n) + 1$这步出现了问题: 构造的$g$不一定递增, 因为$g(n+1)$可能等于$g(n)-1$.

hbghlyj

在MSE找到了构造
$f(1)=1$
$f(n+1)=f(n)+f_n(n+1)-f_n(n)+1.$

Czhang271828

这不用证吧. 数列 $(f(k+1)-f(k))_{k=0}^\infty$ 一一对应 $\mathbb N^\mathbb N$ 中元素. 所以显然.

hbghlyj

类似地:
  $ℕ\toℕ,f(n+1)>f(n)^2$的函数是不可数的
证明:
数列 $(f(k+1)-f(k)^2)_{k=0}^\infty$ 一一对应 $\mathbb N^\mathbb N$ 中元素. 所以显然.