2
$\begingroup$

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

  • 1
    Are you talking about the bijective functions? I don't use this "1-1" terminology.2010-10-17
  • 0
    The only increasing bijection from $\mathbf{N}$ to itself is the identity function. However there are uncountably many increasing injections.2010-10-17
  • 1
    @Prometheus *shoots self* 1-1 != onto. Ok I need to sleep tonight. Haven't done that for a few weeks.2010-10-17
  • 0
    @Prometheus come back! you were right!2010-10-17
  • 0
    @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.2010-10-17

2 Answers 2

3

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.

  • 0
    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.2010-10-17
4

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

  • 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.2010-10-17