0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Brian Tung Mar 22 '18 at 19:46
  • $\begingroup$ Send $f$ to $\sum_{n\in\mathbb{N}}(f(n)-4)3^{-n}$ $\endgroup$ – SphericalTriangle Mar 22 '18 at 19:49
  • $\begingroup$ 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? $\endgroup$ – Patrick Stevens Mar 22 '18 at 19:51
  • $\begingroup$ Compare the answers to this question. $\endgroup$ – Dietrich Burde Mar 22 '18 at 20:31
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.