Find a countable set of functions from an uncountable set? I'm a uni student doing a real analysis course and am finding it very interesting, but at the same time very confusing.
One question that has me stumped is how to get a countable set of functions from a set $S$, where $S$ is a set of all functions $u: \mathbb{N} → \{ 0,1,2 \}$. They also tell us that a function $v(n)$ is equal to $1$ if $n=1$ and equal to 2 if $n \ne 1$ and is an element of $S$. But isn't this getting a countable subset from an uncountable set? How is this possible?
And if $T$ is the set of functions found above can $T$ = $S$ ?
Thanks.
 A: I think you may be confusing a few things here.
First you speak of the set of all functions $\mathbb N \to \{0,1,2\}$, in other words sequences with values in $\mathbb N$, since such a function can be seen as the sequence
$$ f(0) , f(1) , f(2), f(3),\dots $$
(I'm assuming $0\in\mathbb N$, unaware of the convention you may use.)
For instance, one such function may be $0,1,0,1,0,1,...$ where $f(n)$ is $0$ if $n$ is even and $f(n)=1$ if $n$ is odd.  Let's call the set of all these functions $S$. Indeed  $S$ is uncountable as can be seen with the standard diagonal argument: if we had a list $f_1,f_2,f_3,...$ containing each and every of these functions /sequences once, we could create a new function/sequence not on the list, by making it differ from $f_1$ in the first position, from $f_2$ in the second and so on.
The other thing you are talking about are functions that map $1$ to $1$ and all others to $2$. This means the only choice you have left when creating such a function is it's value at $0$, which can be $0$, $1$ or $2$. So we find $3$ such functions:
$$ 0,1,2,2,2,2,\dots $$
$$ 1,1,2,2,2,2,\dots $$
$$ 2,1,2,2,2,2,\dots $$
So the cardinality of the set $T$ equals $3$, which is a finite number. $T$ fits in $S$ nicely, so there's no problem here.
Either way, it's no contradiction to have a countable subset in an uncountable set. For instance, the natural numbers are a countable subset of the real numbers.
-- edit: In fact, one can show that every infinite set,  has a countable subset. On the other hand, a countable set cannot have an uncountable subset. 
A: In general it is impossible to get a countable subset of an uncountable set without using the (countable) axiom of choice. 
But in the case of functions $f:\mathbb{N}\to\{0,1,2\}$ you can find a countable subset of these functions without any use of the axiom of choice, using for example the fact that the natural numbers are countable: Let $f_n(m)=0$ if $m\neq n$ and $f_n(n)=1$. These functions are countable (there is a bijection from the natural numbers to these functions) and are functions from $\mathbb{N}$ to $\{0,1,2\}$. You can make these functions be onto $\{0,1,2\}$ if you want by letting $f_n(0)=2$ for every $n>0$ and letting $f_0(0)=1$, $f_0(1)=2$ and $f_0(m)=0$ for $m>1$.
