Is the set of surjective functions from $\mathbb{N}$ to $\mathbb{N}$ uncountable?

Solution 1:

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!

Solution 2:

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$.

Solution 3:

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$.