Simple Question on 1-1, Increasing integer functions

Question

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 = {All 1-1, increasing functions from N to 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 :-p

(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

Answer 1

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.

Answer 2

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