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?
Best Answer
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!