A Bijection Between the Reals and Infinite Binary Strings

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.

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

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

-

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.

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