Proving a set is uncountable. 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!!!
 A: 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$.
A: 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.
A: 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
A: 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.
