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

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

• Try this: Is the set of all functions from $\mathbb{N}$ to $\{0,1\}$ uncountable? There is a bijection between these functions and what? – ThePortakal Jun 17 '14 at 12:47
• 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. – String Jun 17 '14 at 12:53

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.

• Very nice argument. – Martin Sleziak Jun 18 '14 at 12:13

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.

(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.)
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.