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

  • 4
    Maybe you might have a look at this question: [How does Cantor's diagonal argument work?](http://math.stackexchange.com/questions/39269/how-does-cantors-diagonal-argument-work)2012-05-04
  • 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})$.2012-05-04
  • 1
    A numerable set has measure $0$. $(0,1)$ has measure $1$, therefor $(0,1)$ can't be numerable.2012-05-04
  • 0
    @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.2012-05-04
  • 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$.2012-05-04
  • 0
    @leo: But you are using the fact that it is possible to define a sigma additive measure for which $m(A)=m(A+x\pmod 1)$ for all $x$. This is in fact a uniform measure when you consider singletons. It is easy to prove that such measure cannot be defined on a countable set unless it is the zero measure.2012-05-04
  • 0
    @leo, please show me an outer measure on $P(\mathbb N)$ which gives all the singletons zero; is sigma-additive and gives $\mathbb N$ a positive measure.2012-05-04
  • 0
    Let $(a,b)$ a finite no trivial interval. We can prove (though not very enjoyable) that if $\Delta\subseteq\mathbb{N}$ and $(a,b)\subseteq\bigcup_{k\in\Delta} (a_k,b_k)$ then $b-a\leq \sum_{k\in\Delta}b_k-a_k$. As consequence $(0,1)$ can't have measure $0$ with the above definition. In the other hand consider $\{x_k\}_{k\in\mathbb N}$, by taking the covering $\{(x_k-\epsilon/2^{k+1},x-k+\epsilon/2^{k+1})\}$ it is easy to see that $\{x_k\}_{k\in\mathbb N}$ has measure $0$ with the above definition.2012-05-04
  • 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

18

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
    This deserves a multiple vote, because it is so often missed or dismissed.2012-05-04
  • 0
    To deal with this, you can restrict to only infinite representations, [which are unique](http://math.stackexchange.com/q/30062/8271).2012-05-04
  • 1
    @MarkBennet: I agree. You can give him a second vote on the answer linked by Martin on the question.2012-05-04
  • 0
    @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.2012-05-04
  • 0
    @ArturoMagidin, in the post linked above, we consider $0.10000\ldots$ as a finite representation.2012-05-04
  • 0
    @leo: I **know**. Do you understand my point, or not? The number you *construct* by simply switching the diagonal digits may be a finite presentation; that means that *it could be on the list* with its infinite presentation. You have control over the representation of the numbers on the list, but if you specify your procedure as "just change the $k$th digit of the $k$th number", then you don't have a choice of presentation in the number you construct. In the example I write in the comment above, all numbers which I **choose** have their infinite presentation.2012-05-04
  • 0
    I see. Thanks for show me that.2012-05-04
  • 0
    Arturo, as a color blinded person I really cannot read the yellow(? the $b_5b_6$) font. Is it possible to use a different color please?2012-05-04
  • 0
    @Asaf: Is cyan any better?2012-05-04
  • 0
    @Arturo: Better, but far from great. It doesn't hurt my eyes, though. So I can live with that... thanks!2012-05-04
  • 0
    @Asaf: How about brown?2012-05-04
  • 0
    Bless you.${}{}$2012-05-04
  • 1
    @Asaf: That wasn't me sneezing... There's someone else in the room! Run!2012-05-04
  • 0
    I don't see what is the advantage of working with pairs of binary digits. The diagonalization argument will work using single digits in any base. (well, of course, a pair of binary digits **is** effectively a single digit in base 4).2012-05-04
  • 0
    @Kaz: If you try to use a single digit in base 2, you run the risk of producing a number that *is* on the list. It's the same risk that you run in the decimal case if you carelessly say you will make your number have a 9 in the $n$th position if the $n$th number does not have a $9$ in the $n$th position, an a $0$ otherwise. You could end up with a number that has two representation, and in that case it is not clear that your number is *not* on the list in its other representation. In base $b$, one usually tries to avoid $0$ and $b-1$, but this is not possible in base $2$.2012-05-05
  • 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
12

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.

  • 0
    Plus one for using Baire. : ) This is my favourite answer!2012-05-04
  • 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
5

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

  • 1
    I think this is as straightforward as it gets. But there are probably less straightforward alternative proofs.2012-05-04
  • 0
    Thank you, why +1 mod 2 of the diagonal?2012-05-04
  • 0
    @JustinCase: $+1$ so it's different; $\bmod 2$ so it is still in binary.2012-05-04
  • 1
    What Arturo said. : ) It's the same as doing $x := \lnot x$ for each $x$ on the diagonal.2012-05-04
  • 3
    Note that this runs into the problems of dual representations, same as with decimal digits.2012-05-04
  • 0
    Thanks, mod 2 makes the values in the diagonal different, but isn't the new value going down the diagonal listed somewhere else in the grid? As in, is this sort of a catch-22?2012-05-04
  • 0
    @JustinCase: If you are careful, no: because the number you construct is explicitly constructed to be different from *each* number on the list you are given.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.

3

$\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
    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$.2012-05-04
  • 0
    @AsafKaragila, fiked!2012-05-04
  • 1
    You mean **fixed**. :-)2012-05-04
  • 0
    @AsafKaragila yes ${}{}{}{}$2012-05-04