Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
1  
@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
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.