Why is my proof incorrect for showing set of all increasing functions $f:\Bbb N\to\Bbb N$ is uncountable? Basically, my reasoning is: we can demonstrate a bijection between the set of all functions $f(x)=x+a$ and natural numbers by mapping each natural number to the function using the corresponding a value. ($1\mapsto x+1$... etc) From there, we can easily show that there are more increasing functions aside from just the $x+a$ set, and thus the cardinality of increasing functions is greater than that of natural numbers.
My friend pointed out this is faulty, using the fact that we can form bijections with $\Bbb N$ for both $\Bbb Z^+$ and $\Bbb Z$.
I was modeling my proof after Cantor Diagonalization, which shows a bijection with a set of real numbers and then demonstrates we can create new real numbers outside of our original bijection. Why is this correct but my proof isn't? 
 A: The critical idea here is that Cantor's diagonalization argument hinges on the fact that it works no matter which proposed enumeration of the reals you start with. It's not enough to simply provide a listing that misses some things - if it were, we could show that the naturals were uncountable! In order to show that a set $S$ is uncountable, you must show that there is no way of assigning a different natural number to each member of $S$, not that the one you happened to choose doesn't work.
Importantly, Cantor's diagonalization does not show a bijection between $\mathbb{N}$ and $\mathbb{R}$; it says "suppose that a bijection exists" and then derives a contradiction. Or, if you phrase the argument slightly differently, it says "pick any function from $\mathbb{N}$ to $\mathbb{R}$" and shows that no matter which function you picked, that function is not surjective.
A: I think the part you missed is that when you apply Cantor diagonalisation, you can't specify what your alleged listing of elements is, because the point is to prove that regardless of how the list is constructed, it will always miss an element. You usually only construct a list when you want to prove that such a list exists (which is the case when you're trying to show a bijection between sets, e.g. to show that the rationals are countable).
So instead of "Let the list be the functions $x$, $x+1$, $x+2$, ..." you have to say "Suppose there is a list. Let the elements of the list be $f_1, f_2, f_3, \ldots$" and work from there.
A: $\newcommand{\Natl}{\mathbf{N}}\newcommand{\Incr}{\mathcal{I}}$Let $\Incr$ denote the set of increasing functions from $\Natl$ to itself.


*

*Your goal is to show either of:
There does not exist a surjection $\Phi:\Natl \to \Incr$.
Contrapositively, if $\Phi:\Natl \to \Incr$ is an arbitrary mapping, then $\Phi$ is not surjective.

*You have shown:
A particular mapping $\Phi:\Natl \to \Incr$ is not a surjection. (Specifically, the mapping $a \mapsto \Phi_{a}$, with $\Phi_{a}(x) = x + a$ for all natural numbers $x$ is not a surjection.)
The gap is, perhaps some other mapping $\Phi:\Natl \to \Incr$ is surjective. In other words, you did not consider an arbitrary mapping $\Phi:\Natl \to \Incr$.

What may help in your situation is to show that:


*

*An increasing function $f:\Natl \to \Natl$ is uniquely associated with an infinite subset of $\Natl$ (namely, its image).

*The set of infinite subsets of $\Natl$ is uncountable.
A: The error is assuming that "there are more". The concept "there are more" must be shown proving that exists a bijection to some uncountable set or, equivalently, that doesnt exists a countable bijection (as the diagonalization theorem does).
Observe that, in the same sense, we can say that the set defined by $\Bbb N_{\ge0}\cup\{\sqrt 2\}$ "have more elements" than $\Bbb N_{\ge 0}$. But the cardinality of a set is defined through bijection with other set. In our case the function $f(n):=\delta_{0,n}(\sqrt2+1)+n-1$ is a bijection from $\Bbb N_{\ge 0}$ to $\Bbb N_{\ge 0}\cup\{\sqrt2\}$, thus both sets have the same cardinality (where $\delta_{j,k}$ is the Kronecker delta).
