# Proving that the set of all functions from $\mathbb{N}$ to $\{4, 5, 6\}$ is uncountable

I'm having trouble proving that $\{ f \mid f: \mathbb{N} \rightarrow \{4, 5, 6\} \}$ is uncountable. I'm trying to use Cantor's diagonalization argument.

$f_1 = a_{11}, a_{12}, a_{13}, ..., a_{ij}$

$f_2 = a_{21}, ...$

$f_3 = a_{31}, ...$

...

$f_n = a_{n1}, ...$

I started of by creating a set of functions that have the values 4, 5, 6 for all values of $a_{ij}$. Then, I argued if I took the diagonal I would get I new function not on the list, and that proves it is uncountable. Is that a good enough line arguement? I don't really understand why Cantor's diagonal works for sets of functions.

• A list of reals (in decimal form) is essentially a list of functions from $\mathbb{N}$ to $\{0, 1, \ldots, 9\}$. (I say "essentially" because different decimal expansions can denote the same value, but this only happens on a set of measure $0$.) If you were to subtract $4$ from each of the function values, you would have a list of ternary expansions of real values. – Brian Tung Mar 22 '18 at 19:46
• Send $f$ to $\sum_{n\in\mathbb{N}}(f(n)-4)3^{-n}$ – SphericalTriangle Mar 22 '18 at 19:49
• I don't suppose $3^{\aleph_0} \leq \aleph_0^{\aleph_0} \leq (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 \times \aleph_0} = 2^{\aleph_0} \leq 3^{\aleph_0}$ is an acceptable answer? – Patrick Stevens Mar 22 '18 at 19:51
• Compare the answers to this question. – Dietrich Burde Mar 22 '18 at 20:31

For each $f$ in your set, let $A_f\in\mathcal{P}(\mathbb{N})$ be the set $\{n\in\mathbb{N}\,|\,f(n)=4\}$. The map$$\begin{array}{ccc}\{f\,|\,f\colon\mathbb{N}\rightarrow\{4,5,6\}\}&\longrightarrow&\mathcal{P}(\mathbb{N})\\ f&\mapsto&A_f\end{array}$$is surjective. Therefore, your set is uncountable.

Hint: It suffices to show that the set of all functions from $\Bbb N$ to $\{4,5\}$ is uncountable, for that set is in bijection with a subset of your set.

You idea can works.

Consider the function $f_\alpha=a_{\alpha 1},a_{\alpha 2},a_{\alpha 3},\cdots$ with:

$a_{\alpha i}=4 \quad$ if $\quad a_{ii}=6$

$a_{\alpha i}=5 \quad$ if $\quad a_{ii}=4$

$a_{\alpha i}=6 \quad$ if $\quad a_{ii}=5$

This function is not in the list.

Define $f :\mathbb{N} \to \{4,5,6\}$ as $$f(n) = \begin{cases} 10 - f_n(n) &\text{if f_n(n) \in \{4,6\}} \\ 6& \text{if f_n(n) =5} \end{cases}$$

and notice that $f \ne f_n, \forall n \in \mathbb{N}$ because $f(n) \ne f_n(n), \forall n \in \mathbb{N}$.

This is a contradiction with the fact that $(f_n)_{n=1}^\infty$ are all the functions in $\{4,5,6\}^\mathbb{N}$. Therefore, the set $\{4,5,6\}^\mathbb{N}$ is uncountable.

1) Consider the set of all functions from $\mathbb{N } \rightarrow${$4,5$} (User Shaun's hint).

This is a subset of the original set stated in the problem.

2) {$4,5$} $\sim$ {$0,1$}.

It suffices to show that the set of all functions from $\mathbb{N} \rightarrow$ {$0,1$} is uncountable.

$f_1= a_{11} a_{12}a_{13}.......$

$f_2= a_{21}a_{22}a_{23}..........$

$f_3=a_{31}.........$

$..........$

Note: $a_{ij} =0,1$, for $i,j \in \mathbb{Z^+}$.

So any function would look like: $010011010$......

Now follow Cantor's diagonalization argument.