1
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ Where is the uncountable collection of countable sets that you mentioned? $\endgroup$
    – awllower
    Feb 9, 2018 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, 2018 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$ Feb 9, 2018 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, 2018 at 9:40
  • 1
    $\begingroup$ "... union of uncountably many set of countable sets should be uncountable... " Yes, but your notation is hideous. $\endgroup$ Feb 9, 2018 at 9:42

2 Answers 2

4
$\begingroup$

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.

Edit:

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

$\endgroup$
3
  • 2
    $\begingroup$ Here the Domain is all real Numbers between 0 - 1 $\endgroup$
    – Bhaskar
    Feb 9, 2018 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$ Feb 9, 2018 at 9:45
  • $\begingroup$ @beast_f5 I've edited my answer. Maybe now it's in your sense. $\endgroup$ Feb 9, 2018 at 10:12
1
$\begingroup$

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]}$)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .