cardinality of the set of $ \varphi: \mathbb N \to \mathbb N$ such that $\varphi$ is an increasing sequence I know that the set of functions $ f:\mathbb N \to \mathbb N$ is uncountable, but what if we consider only $f$ such that $f$ is increasing? I want to know if this set is countable D: and also the case of bijective and increasing (clearly if the firstone holds then this too). I think that it could be possible that it's countable
 A: Let $e_1,e_2,e_3,\dots$ be any sequence of $0$'s and/or $1$'s. Let $a_1=1$ and $a_{i+1}=a_i+e_i+1$.
This shows that there are at least $c$ increasing sequences. So there are exactly $c$.   
A: It's uncountable. Suppose that $f_n$ is a sequence of strictly increasing sequences, let $g(0)=f_0(0)+1$; and $g(n+1)=\max\{g(n)+1, f_{n+1}(n+1)+1\}$. Clearly $g$ is not one of the $f_n$'s.
A: Let $\mathscr{F}$ be the set of strictly increasing functions from $\Bbb N$ to $\Bbb N$: then $|\mathscr{F}|=2^\omega=|\wp(\Bbb N)|$, so $\mathscr{F}$ is certainly uncountable. One way to see this is to construct a bijection between $\mathscr{F}$ and ${}^{\Bbb N}\Bbb N$, the set of all functions from $\Bbb N$ to $\Bbb N$. This isn’t too hard.
Define a function $\mathscr{F}\to{}^{\Bbb N}\Bbb N:f\mapsto\hat f$ as follows: let $f\in\mathscr{F}$, and define $\hat f$ by setting $\hat f(0)=0$ and $\hat f(k)=f(k)-f(k-1)-1$ for $k>0$. It’s easy to check that this map is a bijection, so $|\mathscr{F}|=\left|{}^{\Bbb N}\Bbb N\right|$, which you probably already know is $2^\omega=|\wp(\Bbb N)|$.
Added: The inverse map is easy enough to write down as well: if $f\in{}^{\Bbb N}\Bbb N$, let 
$$g:\Bbb N\to\Bbb N:n\mapsto n+\sum_{k\le n}f(k)\;.$$
then $$\hat g(n)=\left(n+\sum_{k\le n}f(k)\right)-\left((n-1)+\sum_{k\le n-1}f(k)\right)-1=f(n)\;,$$
i.e., $\hat g=f$.
A: A nice idea how to prove this was given in this answer by Srivatsan. I am reposting it here since the other question addresses several points, so this might be easily missed among solutions of other parts of that question.

Consider only maps $\varphi \colon \mathbb N\to\mathbb N$ such that $k$ is mapped either to $2k$ or to $2k+1$. 
Every such map is increasing.
We have two possibilities how to choose $\varphi(k)$ for each $k$, so there is $2^{\aleph_0}=\mathfrak c$ such functions. (To make this argument more rigorous, you can show that you can obtain for each element of $\{0,1\}^{\mathbb N}$ a different function of this form.)
A: This is essentially reversing Brian M. Scott's initial argument...
Let $\mathbb{N}^{\mathbb{N}\uparrow}$ denote the family of strictly increasing functions $\mathbb{N} \to \mathbb{N}$.  Given any function $f : \mathbb{N} \to \mathbb{N}$ define $\Phi ( f ) : \mathbb{N} \to \mathbb{N}$ by  $$\Phi ( f ) ( n ) = \sum_{i=0}^n ( f(i) + 1 )$$ Then $\Phi ( f )$ is strictly increasing, and the mapping $f \mapsto \Phi ( f )$ is one-to-one.
Therefore, $| \mathbb{N}^\mathbb{N} | \leq | \mathbb{N}^{\mathbb{N}\uparrow} |$. A quick application of the Cantor–Bernstein–Schröder Theorem then yields $| \mathbb{N}^{\mathbb{N}\uparrow} | = | \mathbb{N}^\mathbb{N} | = 2^{\aleph_0}$.
