Is the set of surjective functions from $\mathbb{N}$ to $\mathbb{N}$ uncountable? I want to use Cantor's diagonalisation argument to prove that the set S of surjective functions of the form $\Bbb{N} \to \Bbb{N}$ is uncountable. The normal procedure is creating a matrix and filling it with elements of S and introducing a new surjective function $p$.The problem that I'm having is that I don't know in which way to change the diagonal elements so that $p$ should, but cannot be in the matrix.
Can someone help me, or at least give me some tips?
 A: Here is an idea for how to use the diagonalization method after all.
Suppose $f_n$ is a list of surjections. We define $g$ in the following way:
$$g(k)=\begin{cases}\frac k2 & k\text{ is even}\\1+\sum_{m\leq k}f_m(k) &\text{otherwise}\end{cases}$$
So $g$ is clearly surjective (its restriction to the even numbers is surjective). To see that $g$ is not one of the $f_n$'s, we need to show that whenever $n\in\Bbb N$ there is some $k$ such that $f_n(k)\neq g(k)$.
Let $n\in\Bbb N$, and let $k$ be any odd number such that $n\leq k$, then we have that $$f_n(k)\leq\sum_{m\leq k}f_m(k)<1+\sum_{m\leq k}f_m(k)=g(k).$$
Therefore $f_n(k)\neq g(k)$ so $f_n\neq g$, and so we have that $g$ is not on the list.

If you are willing to use something other than diagonalization then we can give the following argument:
For every infinite subset of $\Bbb N$, we can write the following surjection:
$$f_A(n) =|\{a\in A\mid a<n\}|$$
Then $f_A$ is surjective because $A$ is infinite, so for every $n$ we can find $k$ such that $f_A(n)=k$.
Note that if $A\neq B$ then $f_A\neq f_B$: if $n=\min A\triangle B$, and suppose that $n\in A$, then $f_A(n+1)>f_B(n+1)$. 
Therefore there are at least $2^{\aleph_0}$ surjections. Moreover all of them are non-decreasing!
A: Among the surjections $\mathbb N\to\mathbb N$ you have the maps
$$f(n)=\begin{cases}k&\text{if }n=2k\\g(k)&\text{if }n=2k-1\end{cases}$$
where $g\colon\mathbb N\to\mathbb N$ is one of the uncountable arbitrary maps $\mathbb N\to\mathbb N$.
A: The following is essentially Asaf's construction except that I think it's a little closer to the standard "diagonal" method.  I assume that, as in the usual picture of the diagonal method, we're given an infinite matrix and that we want a new sequence that differs from every row of that matrix, but that we also want our new sequence to contain every natural number at least once.  Let me start by producing every second term of my new sequence; I'll fill in the omitted terms later.  The key idea is to use a slightly different "diagonal".  Instead of the "main diagonal", consisting of the $n$-th entry of the $n$-th row for all $n$, I'll use a "diagonal" of half the "slope".  That is, in the $n$-th row, I'll concentrate on the $2n$-th entry, and I'll make sure my new sequence differs from all these.  To be specific, I'll define the $2n$-th entry of my new sequence to be $1$ plus the $2n$-th entry in the $n$-th row.  (So I'm defining the even-numbered terms of my new sequence here; the odd-numbered ones will be defined later.)  Notice that, by doing this for every $n$, I've already ensured that my new sequence will differ from every row in the given matrix; specifically, it differs from row $n$ in position $2n$, and this difference is guaranteed no matter what I do with the odd-numbered positions in my new sequence.  But now it's easy to finish the job and take care of the surjectivity requirement; just put $k$ into the $k$-th odd-numbered position (i.e., into position $2k+1$) for every $k$.
A: $\begin{array}{ccc}
f_1(1) && f_1(2) && f_1(3)...\\
f_2(1) && f_2(2) && f_2(3)...\\
f_3(1) && f_3(2) && f_3(3)...\\
\vdots
\end{array}
$
Form a function $g$ with $g(1)$ the least natural number other than $f_1(1)$, $g(2)$ the least natural number other than $f_2(2)$ which is not already used for $g(1)$ and so on. 
If $g$ is a surjection, done. If $g$ is not a surjection, then there exist constants $k,c$ such that for all $n \geq k$, $f_n(n)=c$. All functions with exactly one member that maps to $c$ are in the sequence, and for any $n>k$ there are infinitely many such functions with $f(n)=c$, but only one can go in the $n$th place. Contradiction.      
A: I'll show the set of bijections of $\mathbb N$ to $\mathbb N$ is uncountable, which is a stronger result.
Let $B$ denote the set of binary sequences, i.e., the set of sequences $(b_k)$ where $b_k\in \{0,1\}$ for each $k.$ It is well known that $B$ is uncountable.
Divide $\mathbb N$ into "couples" $C_k=\{2k-1,2k\},k=1,2,\dots$ We will be looking at bijections of $\mathbb N$ to $\mathbb N$ that for eack $k$ either equals the identity on $C_k$ or switches $2k-1$ with $2k.$
Here's how we do it: Let $b=(b_k)\in B.$ Define $f_b:\mathbb N\to \mathbb N$ as follows: For $k=1,2,\dots,$ if $b_k=0$ we let $f_b$ be the indentity on $C_k;$ if $b_k=1$ we let $f_b$ be the switching map on $C_k.$
Then each $f_b$ is a bijection of $\mathbb N$ to $\mathbb N$. Furthermore, the map $b\to f_b$ is injective. Since $B$ is uncountable, so is $\{f_b:b\in B\}.$ It follows that the set of bijections from $\mathbb N$ to $\mathbb N$ is uncountable.
