# 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. – Hanul Jeon 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$.

• how do we show F(f) is injective ? – ಠ_ಠ Aug 21 '16 at 2:05