The set of all functions from integers to a finite set is uncountable

Question

Show that the set of functions from positive integers to the set $\{0,1,2,3,4,5,6,7,8,9\}$ is uncountable.

I suspect I should use the diagonalisation argument but I'm not sure how to approach it.

Answer 1

Following a comment above: if one is allowed to use the fact that the set of all subsets of $\mathbb{N}$, $\mathcal{P}(\mathbb{N})$, is uncountable, then it is enough to observe that the set of functions from $\mathbb{N}$ to $\{0,1,2,3,4,5,6,7,8,9\}$ contains the set $\{0,1\}^{\mathbb{N}}$ of functions from $\mathbb{N}$ to $\{0,1\}$ (via an injection). And there is a clear bijection between $\mathcal{P}(\mathbb{N})$ and $\{0,1\}^{\mathbb{N}}$.

Answer 2

So your space of functions $f: \mathbb{N}\rightarrow 10$ is referred to as $10^{\mathbb{N}}$ which contains $2^{\mathbb{N}}$. There is a canonical injection from $[0,1]$ to $2^{\mathbb{N}}$ by taking binary representations of $x\in [0,1]$.

So we have $\aleph_0<|[0,1]|\leq |2^{\mathbb{N}}|\leq |10^{\mathbb{N}}|$ so uncountable.

Answer 3

The classical diagonal argument works perfectly: for $f: \mathbb{N} \rightarrow 10^{\mathbb{N}}$, consider $g: \mathbb{N} \rightarrow \{0;..;9\}$ defined by $g(n) = 9 - f(n)(n)$ and prove $g$ isn't in the range of $f$ so $f$ is not surjective.