# Proving a set is uncountable. [duplicate]

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!!!

## marked as duplicate by Andrés E. Caicedo, Asaf Karagila♦ set-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jan 13 '15 at 0:18

• Use the Cantor diagonal argument. – André Nicolas Jan 13 '15 at 0:09

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$.

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.

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

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.