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.

  • 1
    $\begingroup$ Hint: Use Cantor's diagonal argument. Assume the set of all function form $\mathbb{N}$ to $\{0,1\}$ is countable, and derive the contradiction. $\endgroup$ – Hanul Jeon Jan 26 '13 at 17:21
  • 1
    $\begingroup$ 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)\}$. $\endgroup$ – Hagen von Eitzen Jan 26 '13 at 17:22
  • $\begingroup$ @HagenvonEitzen: Find bijection between powerset and what ? $\endgroup$ – Idonknow Jan 26 '13 at 17:26
  • $\begingroup$ @Idonknow ... a bijection between the poswerset of $\mathbb N$ and the set of functions from $\mathbb N$ to $\{0,1\}$, cf. Asaf's answer. $\endgroup$ – 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}$.

  • $\begingroup$ What is binary representation? $\endgroup$ – Idonknow Jan 26 '13 at 17:39
  • 2
    $\begingroup$ 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. $\endgroup$ – Clayton Jan 26 '13 at 17:43
  • $\begingroup$ I still don know how to proceed. $\endgroup$ – Idonknow Jan 26 '13 at 17:49
  • $\begingroup$ I've edited my answer for hopefully a more-clear hint. $\endgroup$ – Clayton Jan 26 '13 at 17:56
  • $\begingroup$ Sorry, I'm still very blur. $\endgroup$ – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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