# 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 = {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

-
Are you talking about the bijective functions? I don't use this "1-1" terminology. –  anon Oct 17 '10 at 19:04
The only increasing bijection from $\mathbf{N}$ to itself is the identity function. However there are uncountably many increasing injections. –  Robin Chapman Oct 17 '10 at 19:04
@Prometheus shoots self 1-1 != onto. Ok I need to sleep tonight. Haven't done that for a few weeks. –  mechko Oct 17 '10 at 19:06
@Prometheus come back! you were right! –  mechko Oct 17 '10 at 19:07
@muad, as was stated being 1-1 only means a map is injective. A 1-1 correspondence implies the map is 1-1 and onto. –  Joshua Shane Liberman Oct 17 '10 at 23:10

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.

-
Actually, I like that proof much better than mine. Consider the set of function pairs f_i, f_k, such that for all n, f_i (n) - f_k (n) = 1 or 0. It is trivial to see that for all f_i there exists at least 1 f_k that satisfies this condition. Hence, this partition of F is isomorphic to the set of all functions from N -> {0,1}, which we know to be uncountable. –  mechko Oct 17 '10 at 19:19

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

-
Thanks, but the proof itself is no problem for me. I was just having a moment of oh-god-I-just-disproved-mathematics-what-did-I-do-wrong-panic after re-reading the question definition. –  mechko Oct 17 '10 at 19:14