A Bijection Between the Reals and Infinite Binary Strings

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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