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

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.

• Just one remark on your edit: this requires some choice. Without the axiom of choice one can construct a set which is not finite, but has no two disjoint subsets which are both infinite. – Asaf Karagila Mar 19 '11 at 8:29
• @Asaf Karagila: When you say "without the axiom of choice", is what you mean "with the negation of the axiom of choice"? Because since you can't construct such a set in ZFC, I guess it can only get worse if you leave out another axiom. – Myself Mar 19 '11 at 8:37
• @Myself: You start with a model of ZFC and construct a new model in which there exists such set, which contradicts AC (clearly). – Asaf Karagila Mar 19 '11 at 9:07
• @Asaf Karagila: What? All I'm saying is that your sentence "without the axiom of choice you can ..." sounds as if you could construct such a set just by not using some axiom, which you cant. So it should probably be "with the negation of the axiom of choice ...". In other words, ZF won't work, ZF + $\lnot$ AC will. – Myself Mar 19 '11 at 9:35
• @Myself: Oh, I'm sorry I misread and even worse - I wrote something which is badly inaccurate (where the inaccuracy serves no point). You are absolutely right. – Asaf Karagila Mar 19 '11 at 9:38

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