Set of increasing functions from N to N is uncountable

663 Views Asked by At

I know it is uncountable. But what is wrong with this proof?

I use the lemma that a countable union of countable sets is countable.

Let $f(0)=0$. Then for each function $f$, construct $[a_0, a_1, a_2,\ldots]$ as following: $a_i$ is the number of times the function $f$ takes the value $i$. For example, for $x^2$ the set would be $[1,1,0,0,1,0,0,0,0,1,\ldots]$.

There's a 1 to 1 map from each function to such a set. Thus, the set is a countable union of natural numbers, so is countable.

Then we vary the value of $f(0)$ to $= 0,1,2,3\ldots$. There is a bijection from the set of increasing functions for which $f(0)=0$ and for which $f(0)=i$ (the latter just shifts to the right by ($i+1$)) so the number of functions for which $f(0) = 0,1,2,\ldots$ is just a countable union of the countable sets we made earlier, which is countable.

1

There are 1 best solutions below

0
On

Take a real number from in the range 0 to 1. Each number can be represented as a binary decimal '0.001100...' which in tern can be represented as a series [0, 0, 1, 1, 0, 0, ...]. So there is a bijection between the continuum and your representation raising functions.

Your problem is at the step 'Thus, the set is a countable union of natural numbers, so is countable' you haven't shown that it is a countable union.