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

Question

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

Answer 1

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

Answer 2

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.

Answer 3

Instead of doing this by contradiction, let's just suppose $c_1,c_2,c_3,\ldots$ is a sequence of members of $(0,1)$ and seek to prove that in every open subinterval of $(0,1)$ there are points that are not in the sequence. Set $i=1$ and increment $i$ until $c_i$ is in the subinterval, and call the point you reach $d_1$. (If that never happens then pick any point in the subinterval and we're done.) Then keep incrementing $i$ until you reach a point in the subinterval that is greater than $d_1$, and call it $e_1$. Then continue incrementing $i$ until you reach a point in $(d_1,e_1)$ and call it $d_2$. Then continue incrementing $i$ until you reach a point in $(d_1,e_1)$ that is greater than $d_2$ and call it $e_2$. Keep going in that way. Then $d_1<d_2<d_3<\cdots <e_3<e_2<e_1$. Consider $a=\sup_n d_n$. I claim $a$ is not in the original sequence $c_1,c_2,c_3,\ldots$. If it were, it would have eventually been excluded from the successively narrowing interval.

That is actually how Cantor original proved the set of all reals is uncountable, about three years before he came up with his first diagonal argument.

Later note:

• http://en.wikipedia.org/wiki/Cantor%27s_first_uncountability_proof
• Cantor, Georg (1874), "Über eine Eigenschaft des Ingebriffes aller reelen algebraischen Zahlen", Journal für die Reine und Angewandte Mathematik 77: 258–262

Answer 4

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.