In class, my professor mentioned that $\mathbb{N} \rightarrow \{0,1\}$ was uncountable, and I completely understand the argument. However, I am confused because others online gave a similar proof of $\mathbb{N} \rightarrow (0,1)$ which are the numbers between 0 and 1.
What I really need to know is isn't the codomain of $\mathbb{N} \rightarrow \{0,1\}$ only $0$ and $1$? So shouldn't it only map to a single element $0$ or $1$? In that case wouldn't this be countable?
Please explain!
On
A function $f\colon A\to B$ is a function that for each element of $A$ outputs an element of $B$, but of course not necessarily the same output for all inputs. Hence a function $\Bbb N\to \{0,1\}$ outputs either $0$ or $1$ for a given natural number $n$, but the value may of course depend on $n$.
Also note that it is not (a single function) $\Bbb N\to \{0,1\}$ that is uncountable, but rather the set of all such functions.
Btw, the set of function $\Bbb N\to (0,1)$ is already uncountable because $(0,1)$ itself is; so even the constant maps $\Bbb N\to(0,1)$ are an uncountable set.
Yes, for any function $\mathbb{N} \rightarrow \{0,1\}$, the codomain is just the set of two elements $0$ and $1$.
However, a function in and of itself is not uncountable ... or even countable. That's just a category mistake. Sets are countable or uncountable.
So, what set are we dealing with here? I see $\mathbb{N}$, which is obviously countable. I see $\{ 0,1 \}$, which is obviously countable. And I see $(0,1)$, which is not countable.
But, what your professor probably meant is that the set of all functions that map natural numbers to $\{ 0,1\}$ (i.e. the set of all functions of the form $\mathbb{N} \rightarrow \{0,1\}$) is an uncountable set.
And why exactly is that set uncountable? Here you can use the standard diagonal argument that I assume you were given by your professor as well. But let me give the argument myself; maybe I present it in a way that's a little different from your professor.
OK, so the proof is a proof by contradiction. Let's assume the set of all functions of the form $f : \mathbb{N} \to \{ 0,1 \}$ is countable. Well, that means that you can number them, i.e. you have a $f_1$, $f_2$ .. etc., and every function is supposed to be on that list. That is, for every function $g : \mathbb{N} \to \{ 0,1 \}$, we have that $g = f_i$ for some $i \in \mathbb{N}$.
Now, that's all a little abstract, so let's think of some actual functions that map $\mathbb{N}$ to $ \{0,1\}$. Here is one: the function that maps every number to $0$. Another one is one that maps all numbers to $1$. Another one is one that maps all even numbers to $0$, and all odd numbers to $1$. Etc. etc. Anyway, maybe in our enumeration of all functions, the first three functions I mention here end up in the first three positions. That is, maybe we have $f_1(n)=0$ for all $n$, $f_2(n)=1$ for all $n$, and $f_3(n) = n \mod 2$ for all $n$.
Now, we can represent these functions on an infinite table like so:
\begin{array}{c|ccccc} n&0&1&2&3&4&...\\ \hline f_1&0&0&0&0&0&...\\ f_2&1&1&1&1&1&...\\ f_3&0&1&0&1&0&...\\ ...\\ \end{array}
OK, but now consider the function $g: \mathbb{N} \to \{ 0,1 \}$ defined as $g(n) = 1 - f_n(n)$. Clearly $g$ is a function from $\mathbb{N}$ to $\{ \{ 0,1 \}$, and so it should be $f_k$ for some $k$. However, you then get $f_k(k) = g(k) = 1-f_k(k)$, a contradiction, given that $f(n) \not = 1 - f(n)$ for any $f$ or $n$.
This is called the diagonal method, because the 'new' function $g$ is constructed by taking the diagonal of the above table, and systematically changing each entry to something different:
\begin{array}{c|ccccc} n&0&1&2&3&4&...\\ \hline f_1&\color{red}1&0&0&0&0&...\\ f_2&1&\color{red}0&1&1&1&...\\ f_3&0&1&\color{red}1&1&0&...\\ ...\\ \end{array}
And so, since the $k$-th element of this new function $g$ is different from the $k$-th element from $f_k$, it cannot be any of the $f_k$'s.