Countable and uncountable set. 
Which of the following sets of functions are uncountable?

*

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


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


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


*$\{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?

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.
