Prove that {f:N->N, f increasing function} ~ R How can I prove that 
{$f:N \to N$, f increasing function} ~ R
and 
{$f:N \to N$, f decreasing function} ~ N
Thank you! 
 A: If $f:\mathbb{N}\rightarrow\mathbb{N}$ is increasing, then $g$ defined as $g(0)=f(0)$ and $g(n+1)=f(n+1)-f(n)$ can be any function $\mathbb{N}\rightarrow\mathbb{N}$. $f$ can be reconstructed from $g$ by $f(n)=\sum\limits_{k=0}^n g(k)$. Thus, this provides a bijection between increasing functions $\mathbb{N}\rightarrow\mathbb{N}$ and all functions $\mathbb{N}\rightarrow\mathbb{N}$. The latter set is known to be of the same cardinality as $\mathbb{R}$.
If $f:\mathbb{N}\rightarrow\mathbb{N}$ is decreasing, it must eventually become constant since otherwise the sequence $(a_k)$ where $a_k=f(k)$ will contain an infinite strictly decreasing sequence of natural numbers. This contradicts well-ordering of natural numbers. So, there is a bijection between decreasing functions $f:\mathbb{N}\rightarrow\mathbb{N}$ and finite decreasing sequences of natural numbers. The latter is clearly infinite, so an injection into naturals is enough to show that this set is countable. There are many ways to construct such an injection, for example $(a_k) \mapsto \prod p_i ^{a_k}$, where $p_i$ is the sequence of prime numbers.
