5
$\begingroup$

Prove that the open interval $(0, 1)$ contains uncountably infinite numbers.

Apparently, there is a way to prove this proposition using Cantor's diagonalization argument.

How does that work? How does looking at the diagonal of a big grid of numbers help? Is there a more straightforward proof?

  • 0
    @AsafKaragila, my last comment was not in response to your comment. It is an attempt to sustain a variant of the above comment without measure theoretic considerations.2012-05-04

5 Answers 5

19

We can take a small twist of Matt N.'s hint to make sure we don't run into trouble with dual representations. To see what the problem is, note that, for example, there are two ways of writing $\frac{1}{2}$ in binary: $0.100000\ldots\quad\text{and}\quad 0.011111\ldots$ In principle, it would be that your list begins with $0.1000\ldots$, and then the numbers in position $n$ all have $n$th digit equal to $0$ for all $n\gt 1$. Then the straight "change the digit" process leads to $0.01111\ldots$, which is on the list (it's a different representation of the first number on the list).

So the first thing we need to do is specify that we will use one particular representation in our "list"; usually the one that terminates if there is a choice.

That done, instead of looking at the single diagonal digit, work with diagonals in blocks of $2$; that is, look at the digits in position $1$ and $2$ first, then the digits in positions $3$ and $4$ for the second number, and so on, looking at the digits in position $2k+1$ and $2k+2$ for the $k$th number. Then make the "switch" ensuring that the number you construct does not have two different representations. For instance, if the $k$th number in the list has $00$, $01$, or $11$ in the $2k+1$ and $2k+2$ positions, then put $10$ in your number on those positions; if the $k$th number in the list has $10$, then put $01$ on your list. Then the number you construct does not have two representations, so you can test that it is not on the list by simply comparing the $2k+1$ and $2k+2$ digits with the $k$th number on the list.

So if your list looks like: $\begin{align*} &0.{\color{red}{a_{11}a_{12}}}a_{13}a_{14}a_{15}a_{16}\cdots a_{1,2k+1}a_{1,2k+2}\cdots\\ &0.a_{21}a_{22}{\color{red}{a_{23}a_{24}}}a_{25}a_{26}\cdots a_{2,2k+1}a_{2,2k+2}\cdots\\ &0.a_{31}a_{32}a_{33}a_{34}{\color{red}{a_{35}a_{36}}}\cdots a_{3,2k+1}a_{3,2k+2}\cdots\\ &\vdots\\ &0.a_{k1}a_{k2}a_{k3}a_{k4}a_{k5}a_{k6}\cdots {\color{red}{a_{k,2k+1}a_{k,2k+2}}}\cdots\\ &\vdots \end{align*}$ You then take each red block and construct a new number $0.\color{blue}{b_{1}b_{2}}\color{green}{b_3b_4}\color{brown}{b_5b_6}\cdots\color{magenta}{b_{2k+1}b_{2k+2}}$ where $\color{blue}{b_1b_2}$ is chosen so that it is different from $\color{red}{a_{11}a_{12}}$; $\color{green}{b_3b_4}$ is chosen so that it is different from $\color{red}{a_{23}a_{24}}$; $\color{brown}{b_5b_6}$ is chosen so that it is different from $\color{red}{a_{35}a_{36}};\ldots,\color{magenta}{b_{2k+1}b_{2k+2}}$ is chosen so that it is different from $\color{red}{a_{k,2k+1}a_{2k+2}}$, etc. So you are "going down the diagonal" and changing things so that the resulting number is not on the list: it's not the first number on the list, because it differs from it in the first two entries and your number has only one representation. It's not the second number on the list because it differs from that one in the third and fourth digits; given any $k$, the number constructed is not the $k$th number on the list because it differs from it in the $2k+1$ and $2k+2$ positions. Etc.

  • 0
    @Kaz: (Cont) So you may end up constructing a number that can be expressed in two different ways. If so, then it is not enough to know that it differs from the $n$th number in the $n$th digit to be able to conclude that it is not the $n$th number. Like I say in my examples: say you end up with the "diagonal number" 0.10000000000.... and the first number on your list is 0.01111111111.... (in binary). Then the diagonal number's expansion differs from the first on the list in its first digit, but the two expressions represent the same number, so your "diagonal number" *is* on the list.2012-05-05
13

There have already been posted a few really good answers explaining how to prove this by diagonalization. Just for your awareness, here is an alternative way to show it.

Look at $[0,1]$ as a metric space (a subspace of $\mathbb{R}$ with the usual Euclidean distance). It is complete since $\mathbb{R}$ is complete and $[0,1]$ is closed. But we may write $ [0,1] = \bigcup_{x \in [0,1]}\{x\}. $

Singletons are closed and have empty interior, so it follows that $[0,1]$ must be uncountable, otherwise this would contradict the Baire Category Theorem. From here, we have that $(0,1)$ is obtained by removing two elements from an uncountable set, and so $(0,1)$ is uncountable.

  • 2
    I find metric space / topology arguments like this more enlightening than decimal representations, although they might need more machinery. Another way is to show that every compact Hausdorff space without isolated points is uncountable. This is actually how Munkres proves that $[0,1]$ is uncountable in his Topology.2012-05-04
6

Hint: Represent a number in $(0,1)$ in base $2$. Write the numbers below each other line by line. Then take $+1$ mod $2$ of the diagonal...

  • 0
    @Justi$n$Case: If you are careful, $n$o: because the number you construct is ex$p$licitly constructed to be different from *each* number on the list you are given.2012-05-04
4

$\newcommand{\N}{\mathbb N}$ Let $f:\N\to (0,1)$ a function. Given $n\in\N$ consider the infinite representation of $f(n)$, $f(n)=0.a^n_1a^n_2\ldots a_n^n\ldots$ in base $10$. This infinite representation is unique.

For each $n\in\N$ define $b_n=\begin{cases} 5 & \text{if} &a_n^n\neq 5\\ 7 & \text{if} & a_n^n=5\end{cases}$ we will see that $y=0.b_1b_2b_3\ldots$ can not be in the image of $f$.

Suppose that there is an $l\in\N$ such that $y=f(l)=0.a_1^la_2^l\ldots a_l^l\ldots$ Then $a_l^l=b_l$, i.e. $a_l^l=\begin{cases} 5&\text{if}& a_l^l\neq 5\\ 7&\text{if}&a_l^l=5\end{cases}$ you can see that such an $l$ is not possible.

Therefore $f$ is not surjective and $(0,1)$ is not numerable.

  • 0
    @AsafKaragila yes ${}{}{}{}$2012-05-04
3

Cantor diagonal argument says: Suppose there is any countable collection of numbers, then there is another number which is not in the collection.

To use it, assume that $\{a_n\mid n\in\mathbb N\}$ is a countable collection of numbers from $(0,1)$, let $a_n^i$ be the $i$-th digit in the decimal representation of $a_n$, let $a$ be a number such that $a^i\neq a_i^i$ for all $i$ (if you also ensure that $a^i\neq0,9$ then you have ensured that you do not run into problems of numbers having two representations), this number is between $0$ and $1$ and is definitely not on the list. We have shown that there cannot be a surjective function from $\mathbb N$ onto $(0,1)$.

Another way is to use Cantor's theorem that $\aleph_0<2^{\aleph_0}$. Define the following injection from $P(\mathbb N)$ into $(0,1)$:

$A\mapsto\sum_{n\in A}\frac2{3^{n+1}}$

Show that this is an injective function, and therefore $|(0,1)|\geq2^{\aleph_0}>\aleph_0$, as wanted.