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

-
The title of your question and the body ask two different things. Do you want to show the set of all functions from $\mathbb{N}$ into $\{0,1\}$ is uncountable or the open interval $(0,1)$ is uncountable? –  Austin Mohr Apr 10 '12 at 0:54

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

-
Of course, if you'd dealt with binary expansions (and considered one fixed expansion for dyadics) instead of decimal ones, then the two arguments would be the same. –  Quinn Culver Apr 10 '12 at 1:28
@Quinn: There's a bit of an issue with the multiple representations of binary expansions: the most elegant way I know of doing it is by taking the binary digits two by two, and replacing, say, $00$, $01$, and $11$ with $10$, and replacing $10$ with $01$. But that makes the technical issues obscure the similarity, in my experience, since instead of taking about the $n$th "binaral", we would be talking about the $2n-1$st and $2n$th "binarals". –  Arturo Magidin Apr 10 '12 at 1:31

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.

-
Hint: Consider the element of $(0,1)$ whose $i$th digit is $d_{ii} + 1$ (mod 10). –  Austin Mohr Apr 10 '12 at 1:17
@Austin: That might actually fail, thanks to non-unique representations. Better: the $i$-th digit is $1$ unless $d_{ii}=1$, in which case it’s $2$. –  Brian M. Scott Apr 10 '12 at 1:22

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.

-

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:

-
I've been looking for this proof in Cantor's writings for over a year now. Do you happen to have a reference? I do have a couple of his articles about transfinite numbers from the 1880's or so. –  Patrick Apr 10 '12 at 2:43
I've added a "later note" to my answer; see above. –  Michael Hardy Apr 10 '12 at 2:59