5
$\begingroup$

Is the set of all functions from $\mathbb N$ to $\mathbb Q$ uncountable?

$\endgroup$
  • 6
    $\begingroup$ Try this: Is the set of all functions from $\mathbb{N}$ to $\{0,1\}$ uncountable? There is a bijection between these functions and what? $\endgroup$ – ThePortakal Jun 17 '14 at 12:47
  • $\begingroup$ ThePortakal is right! If you prefer decimals over binary you could consider all maps from $\mathbb N$ to $\{0,1,2,3,4,5,6,7,8,9\}\subset\mathbb Q$ and whether these are countable or not. $\endgroup$ – String Jun 17 '14 at 12:53
3
$\begingroup$

Hint For any real number $x$ you can define a function $f_x : \mathbb N \to \mathbb Q$ by

$$f_x(n) =\frac{\lfloor nx \rfloor}{n} \,.$$

Now, the mapping $x \to f_x$ is a one to one function from $\mathbb R$ to your set.

$\endgroup$
  • $\begingroup$ Very nice argument. $\endgroup$ – Martin Sleziak Jun 18 '14 at 12:13
2
$\begingroup$

The cardinality of the set of all functions from $\mathbb N$ to $\mathbb Q$ is $$|\mathbb Q^{\mathbb N}|=|\mathbb Q|^{|\mathbb N|}=\aleph_0^{\aleph_0} = 2^{\aleph_0} = \mathfrak c > \aleph_0.$$ So this set is uncountable.

See also:

Some of the above links are taken from: Overview of basic results on cardinal arithmetic


If you do not want to compute the cardinality of this set, just show that it is not countable, you can use diagonal argument. See, for example, some answers in these questions:

(You should think a little bit about why showing this for functions $\mathbb N\to\mathbb N$ and $\mathbb N\to\mathbb Q$ is equivalent.)

$\endgroup$
1
$\begingroup$

Yes, in fact you can see it in this way: split the set $A=\{f\colon \mathbb N\to \mathbb N\}$ into $B=\{f\colon \mathbb N\to \mathbb N\colon f(n)=9 \mbox{ eventually}\}$ and $C=A\setminus B$. Then you can map bijectively $C$ to $[0,1)$ by sending $f$ to $0,f(1)f(2)f(3)\ldots$ On the other hand, $B$ is countable because it is a countable union of countable sets.

$\endgroup$
  • 2
    $\begingroup$ Do you mean yes? $\endgroup$ – William Jun 17 '14 at 12:54
  • 1
    $\begingroup$ @William No, I meant no because I read countable instead of uncountable... Thanks, I'll edit! $\endgroup$ – Ferra Jun 17 '14 at 12:59

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.