Are there uncountably many injective functions from $\mathbb N$ to $\mathbb N$? I think there are, but I haven't been able to prove this. I tried to make two injections, but I get stuck on trying to map all functions f from $\mathbb N$ to $\mathbb N$ onto the injective ones. How do you make sure f becomes injective, while making sure that the bigger injection stays injective? Or am I wrong and there are not even uncountably many functions?
 A: There are uncountably many injections $\mathbb{N}$ to $\mathbb{N}$. Here's why:
Suppose I have a set $X\subseteq\mathbb{N}$. Now consider the following idea for "scrambling" $\mathbb{N}$:


*

*If $k\in X$, do swap $2k$ and $2k+1$.

*If $k\not\in X$, don't swap $2k$ and $2k+1$.
For example, if $X=\mathbb{N}$ then our "scrambling" gives $$2,1,4,3,6,5,8,7,...$$ and $X=\emptyset$ doesn't scramble anything at all.
Do you see how to turn this idea into a way to assign to each set of natural numbers an injection from $\mathbb{N}$ to $\mathbb{N}$ (in fact, a permutation of $\mathbb{N}$)? Can you show that two different $X$s yield two different injections?
A: Consider functions of the form $f(n)=2n+\epsilon_n$ where each $\epsilon_n\in\{0,1\}$.
A: Each injection from $\mathbb{N} \to \mathbb{N}$ can be thought of as an infinite sequence. Now use Cantor's diagonal argument to show uncountably many functions. 
A: Let $B = [0,1] \setminus \mathbb{Q}$ be the set of irrational positive numbers smaller than $1$.  
For each $b \in B$, let $(b_n)_{n\in \mathbb{N}}$ be its binary representation. i.e.
$$b = 0.b_0b_1b_2\cdots = \sum_{n=0}^\infty \frac{b_n}{2^{n+1}}\quad\text{ with all }\quad b_n \in \{ 0, 1 \}$$
Let $f_b : \mathbb{N} \to \mathbb{N}$ be the function defined by
$$f_b(n) = n + \sum_{k=0}^n b_k$$
It is easy to see $f_b(n)$ is strictly increasing in $n$, so each $f_b$ is injective.
Since different $b$ leads to different binary representation and hence different $f_b$.
The map 
$$B \ni b\quad\mapsto\quad f_b \in \{ f : \mathbb{N} \to \mathbb{N} \mid f \text{ injective } \}$$
is injective. Since $B$ has uncountably infinitely many elements, so does the set of injective functions over $\mathbb{N}$.
A: Fix a conditionally convergent series. If $x\in \mathbb R$, there is a rearrangement $R_x$ of this series that converges to $x$. i.e. $x\mapsto R_x$ injects $\mathbb R$ into the set of permutations on $\mathbb N$.
Now suppose $\pi:\mathbb N\to \mathbb N$ is a permutation. Consider $\pi(1)=n_1$ and associate to $n_1$ a string $s_1$ of $n_1-1$ zeros followed by a $1$. Now, suppose $s_k$ has been chosen such that by cancatenation we have obtained a string of binary numbers $s_1s_2\cdots s_k.$ Then, if $\pi(k+1)=n_{k+1}$, choose $n_{k+1}$ to be the string of $k$ zeros followed by a $1$. We have thus constructed an injection $\pi\mapsto s_1s_2\cdots s_k\cdots $ into $\mathbb R$ because each string $s_1s_2\cdots s_k\cdots$ is the binary expansion of a unique real nummber.
All that remains now is to invoke the Schroeder-Bernstein theorem. 
