Simple Question on 1-1, Increasing integer functions So my brain is frazzled which is probably why this seems like a big deal to me right now, but I just can't get over this reasoning:
Suppose you have $$F = \{\text{all }  1\text{-}1, \text{increasing functions } \Bbb N \to \Bbb N\}$$
$1$-$1$: means that every value of the domain maps to some unique value of the range and every value of the range is equal to $f(n)$ for some $n$.  Hence, since $f$ is $1$-$1$ and increasing, the only function that exists is the trivial function, $f(n) = n$.
Please tell me why that is wrong.
(ftr, this isn't the homework question.  I am proving uncountability of $F$, which is why my brain-fart is bothering me more)
Answer: @Prometheus left this as a comment and then deleted it, probably because he didn't wish to be associated with stupidity as great as mine.  The error is that I'm assuming one-to-one => onto, which it clearly doesn't. huddles in a ball and cries
 A: First, a theorem: $|P(\mathbb{N})| > \aleph_0$ (this is Cantor's theorem applied to the natural numbers. I will not go through the proof here.)
Now a second theorem: Let $A$ be the set of all finite or co-finite (that is - the complement is finite) subsets of the natural numbers, then $A$ is countable.
Proof: The set of all subsets of size $n$ can be mapped to a subset of $\mathbb{N}^n$ (as images of functions from $n \to \mathbb{N}$), since this is a countable set itself, and we have countably many $n$ then we have countably many finite subsets of the natural numbers, and since every one of those can be mapped to its complement - we have the needed proof.
Corollary: There are uncountably many subsets of $\mathbb{N}$ which are infinite and their complement is also infinite.
For each of these subsets we know that we can order it, and thus have a 1-1 function from $\mathbb{N}$ onto it, which is also increasing.
Therefore, the set of all functions 1-1 and increasing from $\mathbb{N}$ to itself is uncountable.
(I hope this is clear, if not - let me know which points needs further expansion.)
A: The question has been answered in the comments.  The functions are not assumed to be onto.
Here's a hint for an approach that is different from Asaf's: You could consider the sequences of differences $f(n+1)-f(n)$.  It is enough to restrict to functions that only increase by 1 or 2 at each integer.
