Which of the following sets of functions are uncountable?

  1. $\{f|f:\Bbb N\to\{1,2\}\}$

  2. $\{f|f:\{1,2\}\to\Bbb N\}$

  3. $\{f|f:\{1,2\}\to\Bbb N, f(1)\le f(2)\}$

  4. $\{f|f:\Bbb N\to\{1,2\}, f(1)\le f(2)\}$

I think 1 and 4 are true. As cardinality of first option is $2^{\aleph_0}=c$ and the cardinality of the second option is $|\Bbb N^2|=\aleph_0$, the third option is a subset of the second option so it is also countable, the fourth option is a subset of the first option but I am not sure about this. Can anyone please explain this?

  • 1
    $\begingroup$ Hint: Find injections $1\to 4$ and $4\to 1$, and use Cantor-Bernstein. $\endgroup$ – Henning Makholm Jun 22 '15 at 2:00

It is a subset of the first, which does not show that it is uncountable. To show that it is uncountable you have to show that given any countable list of elements, you can construct an element not on the list. Alternatively, you can reduce the problem to a previous known result, because the condition $f(1) \le f(2)$ only restricts $f(1)$. What if we just fix/ignore $f(1)$? Then how many functions do we have? Remember that these functions are completely determined by their output on the naturals, and can thus be represented by a sequence. With the first element of the sequence fixed, the number of sequences is determined by the number of subsequences from the second onwards.

  • $\begingroup$ if we take f(1)=1 then f(2) can take any value, if we take f(1)=2 then f(2) can take any value except 1, in this way can we say it is same as infinite product of $\Bbb N$'s which is uncountable? $\endgroup$ – Chiranjeev_Kumar Jun 22 '15 at 2:14
  • $\begingroup$ i think, I'm in wrong way $\endgroup$ – Chiranjeev_Kumar Jun 22 '15 at 2:17
  • $\begingroup$ Infinite product of what? Each input gives only two choices of output. But the point is that if you fix $f(1) = 1$, then it is equivalent to ignoring what the function does on input $1$. Read my answer carefully, it tells you how to count such functions. $\endgroup$ – user21820 Jun 22 '15 at 2:31
  • $\begingroup$ @Chiranjeev: No problem. By the way, if $f(n) \le f(m)$ for all natural $m,n$, then $f$ must be constant. Now what about the following: How many functions $f \colon \mathbb{N} \to \{1,2\}$ are such that for any natural $m$ there is some natural $n > m$ such that $f(m) \ne f(n)$? $\endgroup$ – user21820 Jun 22 '15 at 3:01
  • $\begingroup$ Ok if we take $m=1,(f(1)=1$ then rest of naturals can be send 2. if we take $m=2,\{1,2\}\to 1$ and rest of naturals to 2. so it's like partition of naturals in two sets, also for each partition we have 2 maps. so my intuition says there will be uncountably many functions @user21820 $\endgroup$ – Chiranjeev_Kumar Jun 22 '15 at 3:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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