Cardinality of the set of bijective functions on $\mathbb{N}$?

I learned that the set of all one-to-one mappings of $\mathbb{N}$ onto $\mathbb{N}$ has cardinality $|\mathbb{R}|$.

What about surjective functions and bijective functions?


The same. It suffices to show that there are $2^\omega=\mathfrak c=|\Bbb R|$ bijections from $\Bbb N$ to $\Bbb N$. Let $P$ be the set of pairs $\{2n,2n+1\}$ for $n\in\Bbb N$. (My $\Bbb N$ includes $0$.) For each $S\subseteq P$ define

$$f_S:\Bbb N\to\Bbb N:k\mapsto\begin{cases} k+1,&\text{if }k\in p\text{ for some }p\in S\text{ and }k\text{ is even}\\ k-1,&\text{if }k\in p\text{ for some }p\in S\text{ and }k\text{ is odd}\\ k,&\text{if }k\notin\bigcup S\;; \end{cases}$$

the function $f_S$ simply interchanges the members of each pair $p\in S$. Clearly $|P|=|\Bbb N|=\omega$, so $P$ has $2^\omega$ subsets $S$, each defining a distinct bijection $f_S$ from $\Bbb N$ to $\Bbb N$. Thus, there are at least $2^\omega$ such bijections. And each function of any kind from $\Bbb N$ to $\Bbb N$ is a subset of $\Bbb N\times\Bbb N$, so there are at most $2^\omega$ functions altogether. Thus, there are exactly $2^\omega$ bijections.


Both have cardinality $2^{\aleph_0}$. Note that the set of the bijective functions is a subset of the surjective functions.

To see that there are $2^{\aleph_0}$ bijections, take any partition of $\Bbb N$ into two infinite sets, and just switch between them. It is not hard to show that there are $2^{\aleph_0}$ partitions like that, and so we are done.