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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.