7
$\begingroup$

This question already has an answer here:

I need to prove that the set of all functions $\mathcal{F}:\mathbb{N}\rightarrow \left \{ 0,1 \right \}$ is uncountable.

I'm not too sure at all how to do this. My initial idea was to try and show that $\mathcal{F} \rightarrow \mathbb{N}$ was not a bijection but I'm not clear at all and need some big help.

Thanks!!!

$\endgroup$

marked as duplicate by Andrés E. Caicedo, Asaf Karagila set-theory Jan 13 '15 at 0:18

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ Use the Cantor diagonal argument. $\endgroup$ – André Nicolas Jan 13 '15 at 0:09
4
$\begingroup$

I will NOT make this a proof by contradiction.

Let $f_1,f_2,f_3,\ldots$ be any sequence of such sequences. Thus $f_1$ is the sequence $f_1(1),f_1(2),f_1(3),\ldots$.

Try to show that the sequence $(1-f_k(k))_{k=1}^\infty$ is not one of the sequences $f_1,f_2,f_3,\ldots$ although is is a member of $\mathcal F$.

$\endgroup$
2
$\begingroup$

You should try a diagonalisation argument, like Cantor's.

Suppose there were a complete countable list of functions, then it should be easy to give a construction of a new function that differs with each.

$\endgroup$
1
$\begingroup$

Your set $\mathcal F$ is equipotential to the power set of $\mathbb N$. Cantor's theorem then tells you that it must be of uncountable cardinality. You can check it here: https://en.wikipedia.org/wiki/Cantor%27s_theorem

$\endgroup$
1
$\begingroup$

Hint. You probably already know that $P(\mathbb{N})$ is uncountable. If so, it would be enough to show that there is a bijection between $P(\mathbb{N})$ and the set of functions from $\mathbb{N}$ to $\{0,1\}$. To find such a bijection, think about how you might encode a subset $A$ of $\mathbb{N}$ as an infinite sequence of zeros and ones.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.