How can I prove that the set of all functions from $(0,1) \to \mathbb N$ is countable or uncountable?

Here the domain is all real numbers between 0 and 1 while the range is set of natural numbers.

Edited :- This answer came to mind. Is it correct?

For every element of domain their is $\mathbb N$ number of functions. So the set of functions for one element of domain is countable. By this logic we can say total number of functions is $ \mathbb N * \mathbb N *\mathbb N \ldots$.

And we all know that countable collection of countable sets is countable and uncountable collection of countable sets is uncountable. We all know that to get collection we need to use sum + operator. My intuition(only for this particular case) is If for sum operator it is uncountable then also for the multiplication operator it should be uncountable.

By this can we say that set of all functions from $(0,1) \to \mathbb N$ is uncountable.

But I doubt about the correctness of this logic "uncountable collection of countable sets is uncountable" but intuitively this logic seems correct.

  • $\begingroup$ Where is the uncountable collection of countable sets that you mentioned? $\endgroup$ – awllower Feb 9 '18 at 9:07
  • 1
    $\begingroup$ Are you trying to say that the set $\{0,1\}$ is uncountable? Or did you confuse it with the interval $(0,1)$ (or maybe $[0,1]$)? Note $\{0,1\}$ is a 2-element set, having $0$ and $1$ as its elements. $\endgroup$ – user491874 Feb 9 '18 at 9:08
  • 1
    $\begingroup$ !!!! In any reasonable interpretation of your "infinite sum" $\Bbb N + \Bbb N + \Bbb N + \cdots$ you have a countable number of copies of $\Bbb N$. $\endgroup$ – Martín-Blas Pérez Pinilla Feb 9 '18 at 9:34
  • 2
    $\begingroup$ Your logic fails you even in the finite case. All the functions from a finite set with three elements $A$ into a finite set with two elements is not just a sum of 2+2+2. It is the exponentiation $2^3$. $\endgroup$ – Asaf Karagila Feb 9 '18 at 9:40
  • 1
    $\begingroup$ "... union of uncountably many set of countable sets should be uncountable... " Yes, but your notation is hideous. $\endgroup$ – Martín-Blas Pérez Pinilla Feb 9 '18 at 9:42

Let $A=\lbrace f\colon \lbrace 0,1\rbrace\to\mathbb{N}\rbrace$.

Each $f\in A$ has two values; it's just $f(0)$ and $f(1)$ and each of them is in $\mathbb{N}$. Consequently the set $A$ has the same cardinality as $\mathbb{N}\times\mathbb{N}$, but this is countable, since $\mathbb{N}$ is countable.


Now let $B=\lbrace f\colon (0,1)\to\mathbb{N}\rbrace$.

Since $x\mapsto \tan(\pi(x-\frac{1}{2}))$ is a bijection of $(0,1)$ and $\mathbb{R}$, we know $(0,1)$ is uncountable. Now there are uncountable many $z\in (0,1)$. Consider now $$\chi_{\lbrace z\rbrace}(x)=\begin{cases} 1& x=z\\ 0 & x\neq z\end{cases}$$ This is indeed a function into $\mathbb{N}_0$, which isn't a problem here since $|\mathbb{N}_0|=|\mathbb{N}|$. Otherwise define $\chi_{\lbrace z\rbrace}(x)=2$ for $x\neq z$. But now there are uncountable many $z\in (0,1)$, so we have "at least" uncountable many functions in $B$.

  • 2
    $\begingroup$ Here the Domain is all real Numbers between 0 - 1 $\endgroup$ – Bhaskar Feb 9 '18 at 9:33
  • $\begingroup$ @beast_f5 A few minutes ago in the orignal post it was $\lbrace 0,1\rbrace$ and not $(0,1)$ $\endgroup$ – Fakemistake Feb 9 '18 at 9:45
  • $\begingroup$ @beast_f5 I've edited my answer. Maybe now it's in your sense. $\endgroup$ – Fakemistake Feb 9 '18 at 10:12

I go from a very particular approach:

Let $A\subset [0,1]$, the characteristic function $\chi_A:[0,1]\to\Bbb N$ is defined by $$\chi_A(x)= \begin{cases} 1 & \text{if } x\in A\\ 0 & \text{if }x\notin A \end{cases}$$

Therefore such $\chi_A$ is a member of the set $\{f:[0,1]\to \Bbb N\}$. There are uncountably many such $\chi_A$.(Choice for $A=2^{[0,1]}$)


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.