# Is the set of all functions from $\mathbb{N}$ to $\{0,1\}$ countable or uncountable?

Is the set of all functions from $\mathbb{N}$ to $\lbrace 0,1\rbrace$ countable or uncountable ? I have no idea on how to start. Any hint or guide will be much appreciated.

-
Hint: Use Cantor's diagonal argument. Assume the set of all function form $\mathbb{N}$ to $\{0,1\}$ is countable, and derive the contradiction. –  tetori Jan 26 '13 at 17:21
Hint: Find a bijection with the powerset. For any set $S$ and any map $f\colon S\to P(S)$, $f$ fails to be onto because it misses $\{x\in S\mid x\notin f(S)\}$. –  Hagen von Eitzen Jan 26 '13 at 17:22
@HagenvonEitzen: Find bijection between powerset and what ? –  Idonknow Jan 26 '13 at 17:26
@Idonknow ... a bijection between the poswerset of $\mathbb N$ and the set of functions from $\mathbb N$ to $\{0,1\}$, cf. Asaf's answer. –  Hagen von Eitzen Jan 27 '13 at 11:08

Hint: You can think of each function as a binary representation; then use Cantor's diagonal argument to show that it can't be countable.

Set up a table like \begin{align}&a_{11}a_{12}a_{13}\ldots\\ &a_{21}a_{22}a_{23}\ldots\\ &a_{31}a_{32}a_{33}\ldots \end{align} where each $a_{ij}\in\{0,1\}$, and use the diagonal argument with the $a_{jj}$.

-
What is binary representation? –  Idonknow Jan 26 '13 at 17:39
You can think of the function as assigning a position, so for example, you could have $$1_10_20_30_4\ldots$$ as possible representation (the binary says that only zeroes and ones are present). Here, the subscripts represent what number mapped to that image, i.e., $1\mapsto 1$, $2\mapsto 0$, and so on. –  Clayton Jan 26 '13 at 17:43
I still don know how to proceed. –  Idonknow Jan 26 '13 at 17:49
I've edited my answer for hopefully a more-clear hint. –  Clayton Jan 26 '13 at 17:56
Sorry, I'm still very blur. –  Idonknow Jan 26 '13 at 18:10

Hint: Show that the function $F\colon\{0,1\}^\mathbb N\to\mathcal P(\mathbb N)$ defined by $F(f)=\{n\in\mathbb N\mid f(n)=1\}$ is a bijection.

Use Cantor's theorem to show that $\mathcal P(\mathbb N)$ is uncountable and deduce the same on $\{0,1\}^\mathbb N$.

-