Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
Maybe you might have a look at this question: How does Cantor's diagonal argument work? –  Martin Sleziak May 4 '12 at 19:30
1  
Given a set $A$, it can't be a bijection between $A$ and $\mathcal{P}(A)$. In particular $\mathcal{P}(\mathbb{N})$ is not numerable. Construct a bijection between $(0,1)$ and $\mathcal{P}(\mathbb{N})$. –  leo May 4 '12 at 19:33
1  
A numerable set has measure $0$. $(0,1)$ has measure $1$, therefor $(0,1)$ can't be numerable. –  leo May 4 '12 at 19:35
    
@leo, but you define the Lebesgue measure to be translation invariant and sigma additive; if you do not know that $(0,1)$ is uncountable you cannot assume the definition is well. You use the fact that you aim to prove in that second comment. –  Asaf Karagila May 4 '12 at 19:40
1  
@AsafKaragila, We can construct the Lebesgue measure from the outer measure ussually defined as the inf taken over the sums of lengths of intervals that cover the set what we are measuring, that properties are deduced from the construction. However in this particular case, given a set $A$ of real numbers you can say that $m(A)=0$ if given $\epsilon\gt 0$, there exist a collection $\{(a_k,b_k)\}_{k\in\Delta}$, $\Delta\subseteq\mathbb{N}$ such that $$\sum_{k\in\Delta}b-k-a_k\lt\epsilon.$$ This is enough to sustain the above argument. Even we can avoid to say that $(0,1)$ has measure $1$. –  leo May 4 '12 at 19:55

5 Answers 5

up vote 18 down vote accepted

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.

share|improve this answer
    
This deserves a multiple vote, because it is so often missed or dismissed. –  Mark Bennet May 4 '12 at 19:39
    
To deal with this, you can restrict to only infinite representations, which are unique. –  leo May 4 '12 at 19:41
1  
@MarkBennet: I agree. You can give him a second vote on the answer linked by Martin on the question. –  Asaf Karagila May 4 '12 at 19:41
    
@leo: But you run into exactly the same problem: if we restrict to infinite representations, what is to stop the first number in the list form being $0.01111\ldots$, and for $n\gt 1$ the $n$th number having $0$ on the $n$th position; then the number you get is $0.10000\ldots$ which is a finite representation of a number which is on the list. Doesn't matter which representation you pick, if you are not careful when constructing the diagonal number you can end up with a different presentation for a number already on the list. –  Arturo Magidin May 4 '12 at 19:48
1  
@Asaf: That wasn't me sneezing... There's someone else in the room! Run! –  Arturo Magidin May 4 '12 at 20:45

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

share|improve this answer
1  
I think this is as straightforward as it gets. But there are probably less straightforward alternative proofs. –  Matt N. May 4 '12 at 19:22
    
Thank you, why +1 mod 2 of the diagonal? –  Minden Petrofsky May 4 '12 at 19:24
    
@JustinCase: $+1$ so it's different; $\bmod 2$ so it is still in binary. –  Arturo Magidin May 4 '12 at 19:25
1  
What Arturo said. : ) It's the same as doing $x := \lnot x$ for each $x$ on the diagonal. –  Matt N. May 4 '12 at 19:25
3  
Note that this runs into the problems of dual representations, same as with decimal digits. –  Arturo Magidin May 4 '12 at 19:26

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.

share|improve this answer

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.

share|improve this answer
    
Plus one for using Baire. : ) This is my favourite answer! –  Matt N. May 4 '12 at 21:26
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. –  Cihan May 4 '12 at 21:42

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

share|improve this answer
    
If you consider the infinite representation of $f(n)$, why stop at $n$ digits? Also you mean $y$ cannot be in the image of $f$. –  Asaf Karagila May 4 '12 at 20:54
    
@AsafKaragila, fiked! –  leo May 4 '12 at 21:03
    
You mean fixed. :-) –  Asaf Karagila May 4 '12 at 21:06
    
@AsafKaragila yes ${}{}{}{}$ –  leo May 4 '12 at 21:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.