2
$\begingroup$

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.

2 Answers 2

3

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.

  • 0
    @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.2011-03-19
1

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