Show that the set of functions $\mathbb{N}\to\{0,1\}$ is not countable

Recall that a countable set $S$ implies that there exists a bijection $\mathbb{N}\to S$. Now, I consider (0,1). I want to prove by contradiction that $(0,1)$ is not countable.

First, I assume the contrary that there exists a bijection $f$, and I can find an element in $S$, but not in the range of $f$. But I can't find such element. How can you construct such $f$?

1. The question in the title. Let $S=\{f\colon\mathbb{N}\to\{0,1\}\}$ be the set of all functions from $\mathbb{N}$ to $\{0,1\}$, and let $g\colon\mathbb{N}\to S$ be any function. We show that $g$ is not onto (in particular, $g$ is not bijective).

   Define $f_g\colon\mathbb{N}\to\{0,1\}$ as follows: $$f_g(n) = \left\{\begin{array}{ll} 0 &\text{if }(g(n))(n) = 1,\\ 1 &\text{if }(g(n))(n) = 0. \end{array}\right.$$ Note that this makes sense: $g(n)\in S$, so $g(n)$ is a function $\mathbb{N}\to\mathbb{S}$. Hence, we can evaluate $g(n)$ at any natural number, and obtain either $0$ or $1$. So $(g(n))(n)$ is either $0$ or $1$.

   Show that $f_g\in S$ and that $f_g\neq g(m)$ for every $m\in\mathbb{N}$. Conclude that $f_g$ is not in the image of $g$, so $g$ is not onto.

2. The question in the body. Let $g\colon\mathbb{N}\to(0,1)$ be any function. We show that there is a number $x_g\in(0,1)$ that is not in the image of $g$, hence $g$ is not onto, hence not surjective.

   We define $x_g$ via its decimal expansion: for those numbers in $(0,1)$ that have two decimal expansions, pick one once and for all; for example, pick the one with a tail of $0$s instead of a tail of $1$s. We let $$x_g = \sum_{i=1}^{\infty}\frac{x_i}{10^i}$$ where $$x_n = \left\{\begin{array}{ll} 5 & \text{if the }n\text{th decimal of }g(i)\text{ is not }5;\\ 6 & \text{if the }n\text{th decimal of }g(i)\text{ is }5. \end{array}\right.$$ Show that $x_g$ is a number in $(0,1)$, and that it is not equal to $g(m)$ for any $m$.

You may notice the similarity in both constructions. In fact, they all involve the same idea, called "Cantor's Diagonal Argument."

I'll assume you want to show that $(0,1)$ is uncountable. There are various ways to do this, using different areas of mathematics. I'll show you the most intuitive one:

If it is countable, then there is a bijection from $N$ to $S$. This allows you to enumerate all the elements in $(0,1)$ like this:

$1 \leftrightarrow 0.d_{11} d_{12}\ldots$

$2 \leftrightarrow 0.d_{21} d_{22}\ldots$

$3\ldots$

where $d_{ij}$ are the "digits", i.e. numbers from 0 to 9

Can you construct a new number in (0,1) that is different from all these listed numbers? If so, you've found a number in (0,1) which is not "mapped to" by the bijection. Thus a contradiction.

Here's a proof that relies on the fact that a nested sequence of closed intervals is nonempty. While this relies on completeness, so do the decimal expansion proofs as existence of a decimal expansion also relies on completeness. The proof using infinite binary sequences doesn't have this problem, but using that result to show $(0,1)$ is uncountable still requires a way to identify infinite binary sequences with reals in $(0,1)$.

Proof. Suppose $(0,1) = \{x_k:k<\omega\}$. For $n=0$, pick some closed interval $I_0\subseteq (0,1)$ that doesn't contain $x_0$. In general, for $n\ge 0$, suppose we've defined closed intervals $I_0\supseteq I_1 \supseteq \ldots \supseteq I_n$ so that $I_n$ doesn't contain any of the points $x_0 \ldots, x_n$. We then choose a closed interval $I_{n+1}\subseteq I_n$ that doesn't contain any of the points $x_0,\ldots , x_n, x_{n+1}$. This completes the construction.

The intersection $\bigcap_n I_n$ contains a point of $(0,1)$ because it's the intersection of a nested collection of closed intervals, but on the other hand the intersection contains no $x_k$ for any $k<\omega$,. This is a contradiction. Therefore $(0,1)$ isn't countable.

Edit: Another benefit of this proof is that it works just as well with $\mathbb{R}$ in place of $(0,1)$. Hence there's no need to identify $(0,1)$ with $\mathbb{R}$ via some bijection which is the usual approach to show that $\mathbb{R}$ is uncountable.