6
$\begingroup$

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.

$\endgroup$
12
  • 1
    $\begingroup$ 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). $\endgroup$ May 14, 2011 at 19:42
  • 1
    $\begingroup$ How about just encoding the non-terminating decimal expansion as a sequence of 0s and 1s digit by digit? $\endgroup$
    – gowers
    May 14, 2011 at 19:53
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    May 14, 2011 at 20:08
  • 1
    $\begingroup$ Also, the proof of Cantor-Bernstein does not require the Axiom of Choice, so this is constructive. $\endgroup$
    – Tony Huynh
    May 14, 2011 at 20:11
  • 2
    $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    May 14, 2011 at 20:28

4 Answers 4

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ May 15, 2011 at 3:32
5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Since I do not have edit permissions, \sum should be in low case, rather than \Sum. $\endgroup$
    – Asaf Karagila
    May 14, 2011 at 22:22
  • $\begingroup$ Stefan: that is exactly what Cantor did. Odd that you couldn't get to Gottingen from home ... $\endgroup$
    – KP Hart
    May 15, 2011 at 12:58
  • $\begingroup$ You are right KP, I have no idea what my problem was with that link. $\endgroup$ May 15, 2011 at 14:12
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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