I was curious about this one the other day. I came up with my own proof but it's reliant on the continuum hypothesis.
The proof is below, but I was wondering if it's possible to have a "proven" proof. Also, I want to get the proof below reviewed to see if it is correct.
The proof reliant on the continuum hypothesis is just a diagonalisation argument, just like Cantor's:
Assume that the set $S$ of all bijective functions from $\mathbb N$ to $\mathbb N$ has cardinality $\aleph_0$
Then the set is listable as ${f_n}$
Let g be a function that has the following properties:
Property 1: $\lbrace g(3n), g(3n+1), g(3n+2) \rbrace = \lbrace 3n, 3n+1, 3n+2 \rbrace \forall n \in \mathbb N$
Property 2: $(g(3n), g(3n+1), g(3n+2)) \notin \lbrace (f_{3n}(3n), f_{3n}(3n+1), f_{3n}(3n+2)), (f_{3n+1}(3n), f_{3n+1}(3n+1), f_{3n+1}(3n+2)), (f_{3n+2}(3n), f_{3n+2}(3n+1), f_{3n+2}(3n+2)) \rbrace \forall n \in \mathbb N$
Property 1 says that g is just the identity function but "3-wise permutated", meaning that for every group of three consecutive numbers of the form $3n, 3n+1, 3n+2$ the image of that small set is itself. This tells us that g is bijective
Property 2 says that the function g differs from every other function in the list. To see this, start with $f_1, f_2, f_3$. The numbers $1$, $2$ and $3$ might not even appear as $f_1(k), f_2(k), f_3(k)$ (for $k = 1, 2 $or $3$) at all. The worst case scenario, however, is that all three of $f_1(\lbrace 1,2,3 \rbrace), f_2(\lbrace 1,2,3 \rbrace)$ and $f_3(\lbrace 1,2,3 \rbrace)$ are permutations of $\lbrace 1,2,3 \rbrace$
But since we have $3!$ of said permutations, we will always have at least 3 choices for the tuple $(g(1), g(2), g(3))$.
The same thing happens for all subsets of the form $\lbrace 3n, 3n+1, 3n+2 \rbrace$
So g is well defined, bijective, and different to every function in the list ${f_n}$
This ends the diagonalisation argument by contradiction, because g is both in the list and different from every function in the list
Thus, the set in question is (obviously infinite), non numerable, and a subset of all functions from $\mathbb N to \mathbb N$
So its cardinality, $|S|$, satisfies $\aleph_0 < |S| ≤ c$.
The proof ends if we assume the continuum hypothesis.
Thanks for checking this proof and please let me know if there's a proof that doesn't assume CH
Best Answer
Here is a proof:
For any bijection $f:\Bbb N\to\Bbb N$ define a subset $A_f=\{x\in\Bbb N\mid f(x)=x\}$.
Suppose that $A\subset\Bbb N\setminus\{0,1\}$, then I can find a bijection $f:\Bbb N\to\Bbb N$ such that $A=A_{f}$. Let $B=\Bbb N\setminus A$, then $B$ is either finite or infinite. Also, note that $B$ has at least two elements ($0$ and $1$).
If $B$ is finite, order its elements as $n_0<n_1<n_2<\dots<n_k$. Now we define $f(n_i)=n_{i+1}$ for any $i<k$ and $f(n_k)=n_0$. It is clear that $f(n)\neq n$ for any $n\in B$. Furthermore, we let $f(n)=n$ for all $n\in A$.
On the other hand, if $B$ is infinite, order its elements as $n_0<n_1<\dots<n_k<\cdots$. In this case we set $f(n_i)=n_{i+1}$ for all even $i\in\Bbb N$ and $f(n_i)=n_{i-1}$ for all odd $i\in\Bbb N$. Once again we let $f(n)=n$ for all $n\in A$.
It is easy to see that in both cases $f$ is a bijection. Since the power set $\mathcal P(\Bbb N\setminus\{0,1\})$ has cardinality $2^{\aleph_0}=\frak c$, we see that there must be at least $\frak c$ many bijections from $\Bbb N$ to $\Bbb N$.