10
$\begingroup$

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

  • 6
    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?2012-04-10

4 Answers 4

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

  • 0
    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.2012-04-10
  • 1
    @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".2012-04-10
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.

  • 0
    Hint: Consider the element of $(0,1)$ whose $i$th digit is $d_{ii} + 1$ (mod 10).2012-04-10
  • 2
    @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$.2012-04-10
1

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.

0

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

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:

  • 0
    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.2012-04-10
  • 1
    I've added a "later note" to my answer; see above.2012-04-10