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

Solution 1:

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.

Solution 2:

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.

Solution 3:

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

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

Solution 5:

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.