Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|cite|improve this question
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

2 Answers 2

up vote 6 down vote accepted

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

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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