Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Whenever possible, I like to present Cantor's diagonal proof of the uncountability of the reals to my undergraduates. For simplicity, I usually restrict to showing that the subset $$ A = \{x \in [0,1) \mid \text{ the decimal representation of $x$ uses only 0's and 1's} \} $$ is already uncountable. I was thinking recently that it would be nice to add a quick proof that $A$ is actually of precisely the same cardinality as $\mathbb{R}$. That is, I would like to:

Demonstrate a bijection between $A$ and $\mathbb{R}$.

My first instinct was to use find an injection from $A$ into $\mathbb{R}$ and vice versa, then appeal to Cantor-Bernstein to say that a bijection exists (even if we don't know how to construct it). The identity map suffices from $A$ into $\mathbb{R}$. For the other direction, I thought of something like "for $x \in \mathbb{R}$, map $x$ to its binary representation, disregarding the decimal point". I'm afraid this function fails to be injective, however. For example, 1 (base 10) can be represented as $.\overline{1}$ (base 2), and so 2 (base 10) can be represented as $1.\overline{1}$ (base 2). Thus, 1 and 2 (base 10) will have the same image under my map.

Any methods (not necessarily the one I've attempted to start here) are most welcome. I will accept as "correct" the method which demonstrates the bijection with the greatest level of clarity.

share|improve this question
1  
A nice argument goes by seeing that there is an injection ${\mathbb R}\to{\mathcal P}({\mathbb Q})$ (identify reals with left sides of Dedekind cuts). –  Andres Caicedo May 14 '11 at 19:42
1  
How about just encoding the non-terminating decimal expansion as a sequence of 0s and 1s digit by digit? –  gowers May 14 '11 at 19:53
1  
To expand on gowers comment, just encode digit $x$ by a string of $x$ consecutive 1's, and place a single 0 between each string of 1's. For the digit before the decimal place and the one after put two 0's instead of one. –  Tony Huynh May 14 '11 at 20:08
1  
Also, the proof of Cantor-Bernstein does not require the Axiom of Choice, so this is constructive. –  Tony Huynh May 14 '11 at 20:11
2  
Correction: Encode each digit $x$ in base 10 as a string of $x+1$ consecutive 1's, and use a 0 as a place holder between digits except use a 00 instead of 0 as a place holder for the decimal point. –  Tony Huynh May 14 '11 at 20:28
show 7 more comments

4 Answers

Just for the fun, we can use continued fractions to map the sequences of positive integers injectively to [0,1] the sequence may end with $\infty$ meaning that we get a finite fraction (a rational number). Now, the mapping 01010111100110110... to 001010111100110110... to 2,1,1,1,1,4,2,2,1,2,... is a clear bijection (add zero to the beginning and start counting group lengths). This can, probably, be upgraded to get $\mathbb R$ as the image but, IMHO, $[0,1]$ is good enough too and we have no problem with multiple decimal representations.

share|improve this answer
    
There is a mild problem with the fact that a continued fraction ending $n, 1$ is the same as a continued fraction ending $n+1$, but it's not hard to fix. –  Qiaochu Yuan May 15 '11 at 3:32
add comment

How about Cantor's own argument as on page 488 of Part 1 of his Beiträge?

share|improve this answer
add comment

Unfortunately I cannot access KP's link from home and I don't know Cantor's original argument. However, my favourite argument for $|A|=|\mathbb R|$ is as follows (your non-injective argument actually, just looked at more carefully):

Every number $0.x_1x_2\dots\in A$ gets mapped to $\sum_{n=1}^\infty x_n2^{-n}$, i.e., we consider $0.x_1x_2\dots$ as the binary representation of a number. This map is not 1-1. However, it fails to be 1-1 on only countably many places, namely, a number $0.x_1\dots x_n0\overline 1$ is mapped to the same real number as $0.x_1\dots x_n1\overline 0$. But there are only countably many pairs like that.
So, your map fails to be 1-1, but only at countably many places, and at each failure of injectivity, only two numbers are identified.

Hence, after removing countably many points from $A$, your suggested map embeds the rest of $A$ into $\mathbb R$ in a 1-1 way. The countable set of exceptions can be mapped outside the unit interval, in a 1-1 way.

share|improve this answer
    
Since I do not have edit permissions, \sum should be in low case, rather than \Sum. –  Asaf Karagila May 14 '11 at 22:22
    
Stefan: that is exactly what Cantor did. Odd that you couldn't get to Gottingen from home ... –  KP Hart May 15 '11 at 12:58
    
You are right KP, I have no idea what my problem was with that link. –  Stefan Geschke May 15 '11 at 14:12
add comment

A more concrete way to fix the OP's idea (which is similar to Stefan's but avoids Cantor-Bernstein) is to simply delete $\mathbb{Q}$ from $A$ to produce a new set $B$. Split $B$ into a countable family of sets $B_k$ where $B_k$ consists of all the elements of $B$ with $k$ leading zeros. There is now an obvious bijection between any $B_k$ and any set of the form $[n,n+1)-\mathbb{Q}$ by simply viewing elements of $B_k$ as sequences in binary instead of decimal and ignore the leading zeros and first 1. There is no need to worry about the OP's original concern since $B$ only consists of irrationals. Since there are countably many $B_k$'s and countably many $[n,n+1)-\mathbb{Q}$, pick your favorite way to match them up. The remainder, $A\cap\mathbb{Q}$, is obviously countably infinite, so biject it with $\mathbb{Q}$.

share|improve this answer
add comment

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.