I (0,1) is uncountable using binary expansions?

[psie]

TL;DR Summary

I have opened up my old lecture notes from set theory, and the author in there proves that $(0,1)$ is uncountable with the help of decimal expansions not ending with infinite $9$s (aka the diagonal argument, see below). Naively, can we just replace decimal expansions with binary expansions not ending with infinite $1$s, say?

In the proof, we assume $(0,1)$ to be countable and we write \begin{align*}a_0&=0.a_{00}a_{01}a_{02}\ldots \\ a_1&=0.a_{10}a_{11}a_{12}\ldots \\ a_2&=0.a_{20}a_{21}a_{22}\ldots \\ &\vdots\end{align*}and so on for the elements $a_0,a_1,\ldots$ in $(0,1)$ (and where the expansions do not end in infinite $9$s). Then we define the real number $b=0.b_0b_1\ldots$ where $$b_k=\begin{cases}1&\text{if } a_{kk}\neq 1\\ 2&\text{if }a_{kk}=1.\end{cases}$$ This number is in $(0,1)$, but is not included in the enumeration. Contradiction.

I'm wondering, does this argument also work if we use that every real in $(0,1)$ has a unique binary expansion not ending in infinite $1$s, say? Since we only have two digits in base $2$, I imagine it gets a little tight. Somewhere I overheard that this should work in any base.

The reason why I'm asking in the first place is because after Theorem 2.14 in Rudin's PMA, he claims that those readers familiar with binary representations of a real number will notice that the set of binary sequences being uncountable implies the reals being uncountable. I don't see how to go about this implication without first showing a subset of $\mathbb R$ being uncountable (in this case $(0,1)$), and then constructing a bijection from $(0,1)$ to $\mathbb R$, which is fairly easy.

 

[PeroK]

I'm wondering, does this argument also work if we use that every real in $(0,1)$ has a unique binary expansion not ending in infinite $1$s, say? Since we only have two digits in base $2$, I imagine it gets a little tight. Somewhere I overheard that this should work in any base.

It's trickier in binary. Because you don't have the flexibility of digits.

Cantor's original diagonal argument actually showed that the power set of $\mathbb N$ was uncountable, using binary strings. Rather than showing that $\mathbb R$ was uncountable directly.

You can show that the cardinality of $\mathbb R$ is equal to the cardinality of the power set of $\mathbb N$ by noting that only a countable subset of $(0,1)$ have two distinct binary expansions.

 

[FactChecker]

Good question. You are correct.
One thing I prefer about using the decimal version is it makes clear there are a LOT of ways to identify numbers not on the list. For every digit, you have a choice of 9 other digits. To me, it motivates the understanding that there are massively more reals than natural numbers (or even rational numbers).

 

[PeroK]

Good question. One thing I like about using the decimal version is it makes clear there are a LOT of ways to identify numbers not on the list. For every digit, you have a choice of 9 other digits. To me, it motivates the understanding that there are massively more reals than natural numbers (or even rational numbers).

For example, this proof from a guy at MIT shows the set of real numbers between 0 and 1 whose decimal expansion contains only the digits 3 and 4 is uncountable. And, that is clearly a very "small" subset of all the real numbers in that interval.

 

[WWGD]

TL;DR Summary: I have opened up my old lecture notes from set theory, and the author in there proves that $(0,1)$ is uncountable with the help of decimal expansions not ending with infinite $9$s (aka the diagonal argument, see below). Naively, can we just replace decimal expansions with binary expansions not ending with infinite $1$s, say?

In the proof, we assume $(0,1)$ to be countable and we write \begin{align*}a_0&=0.a_{00}a_{01}a_{02}\ldots \\ a_1&=0.a_{10}a_{11}a_{12}\ldots \\ a_2&=0.a_{20}a_{21}a_{22}\ldots \\ &\vdots\end{align*}and so on for the elements $a_0,a_1,\ldots$ in $(0,1)$ (and where the expansions do not end in infinite $9$s). Then we define the real number $b=0.b_0b_1\ldots$ where $$b_k=\begin{cases}1&\text{if } a_{kk}\neq 1\\ 2&\text{if }a_{kk}=1.\end{cases}$$ This number is in $(0,1)$, but is not included in the enumeration. Contradiction.

I'm wondering, does this argument also work if we use that every real in $(0,1)$ has a unique binary expansion not ending in infinite $1$s, say? Since we only have two digits in base $2$, I imagine it gets a little tight. Somewhere I overheard that this should work in any base.

The reason why I'm asking in the first place is because after Theorem 2.14 in Rudin's PMA, he claims that those readers familiar with binary representations of a real number will notice that the set of binary sequences being uncountable implies the reals being uncountable. I don't see how to go about this implication without first showing a subset of $\mathbb R$ being uncountable (in this case $(0,1)$), and then constructing a bijection from $(0,1)$ to $\mathbb R$, which is fairly easy.

Well, if you show the set of binary sequences is uncountable and you can biject it into the set of Reals in some interval, isn't that enough?

 

[psie]

Well, if you show the set of binary sequences is uncountable and you can biject it into the set of Reals in some interval, isn't that enough?

Yes, that would be enough. For instance the interval $[0,1)$. You would then have to remove all the binary sequences from $\{0,1\}^\mathbb{N}$ that represent some rational in $[0,1)$ that terminates with infinitely many $1$s.

 

[mathwonk]

1) a set having an uncountable subset is itself uncountable.
2) all those real numbers between 0 and 1 and having a decimal expansion involving only 0's and 1's is uncountable. (diagonal method proof.)
3) hence the set of all reals is uncountable.

(i.e. as presumably shown in the MIT video using 3's and 4's, wishing to restrict to 0's and 1's does not require using binary expansions, and it also avoids worrying about the occurrence of infinitely many 1's.)

This is WWGD's argument, I believe.

 

[jbriggs444]

One can cheat and use binary expansions where the digits are grouped in pairs. You go down the diagonal grabbing two digits from each row. As you grab each pair, you modify "00" and "01" to "10". And you modify "10" and "11" to "01". This gives you an infinite binary string guaranteed not to be present on the original list of binary strings. Further, this string is sure not to end in infinitely many 1's. No danger of multiple representations.

Of course, this is equivalent to using base 4 and modifying each "0" and "1" digit to "2" and each "2" and "3" digit to "1".

 

[mcastillo356]

Hi PF, @psie

In the proof, we assume $(0,1)$ to be countable and we write \begin{align*}a_0&=0.a_{00}a_{01}a_{02}\ldots \\ a_1&=0.a_{10}a_{11}a_{12}\ldots \\ a_2&=0.a_{20}a_{21}a_{22}\ldots \\ &\vdots\end{align*}and so on for the elements $a_0,a_1,\ldots$ in $(0,1)$ (and where the expansions do not end in infinite $9$s). Then we define the real number $b=0.b_0b_1\ldots$ where $$b_k=\begin{cases}1&\text{if } a_{kk}\neq 1\\ 2&\text{if }a_{kk}=1.\end{cases}$$ This number is in $(0,1)$, but is not included in the enumeration. Contradiction.

Fine, I understand. The decimal expansions biject $\mathbb{N}$? Why not ending in infinite $9$ or $1$ as a premise? I don't naively see any problem in that fact.

I'm wondering, does this argument also work if we use that every real in $(0,1)$ has a unique binary expansion not ending in infinite $1$s, say? Since we only have two digits in base $2$, I imagine it gets a little tight. Somewhere I overheard that this should work in any base.

@PeroK has provided video; I also understand it.
This post is full of questions without attempt. But it has attracted my attention.

Greetings

 

[jbriggs444]

Fine, I understand. The decimal expansions biject $\mathbb{N}$?

The set of decimal expansions do not biject $\mathbb{N}$. The point of the proof is that they cannot.

The set of digit positions in the decimal expansions do biject $\mathbb{N}$. This is crucial so that a diagonal can be formed. There must be a bijection between the set of rows and the set of digit positions. Else we cannot perform a diagonal construction.

Why not ending in infinite $9$ or $1$ as a premise? I don't naively see any problem in that fact.

We do not want to go carefully through the diagonalization process and successfully construct a digit sequence that is not on the original list of digit sequences only to discover that it is an ending-in-all-9's alias for a real number that was on the original list of decimal expansions in its ending-in-all-0's form.

In decimal, it is easy to be sure that our "anti-diagonal" digit string ends in neither all 0's nor all 9's.

In binary, it is not easy to avoid the all 1's case. If, for instance, we have the list (expressed in base 2):

0.100000000...
0.001000000...
0.000100000...
0.000010000...
0.000001000...
...

The diagonal is 0.100000000...
The anti-diagonal is 0.011111111...

As a digit string, the result is not present on the original list. However, as a real number, we have found the all 1's alias for $\frac{1}{2}$. That real number is already in the list. Right there at the top.

 

[mcastillo356]

Thanks @jbriggs444 !
I will review the thread
Marcos

 

[mcastillo356]

Hi PF, once understood Cantor's diagonalization proof (originally for $[0,1]$), and regarding there is an algorithm to get from decimal to bynary expansion, it is easy to perform the proof in both fashions. At the same time, it is difficult; the essential doubt I have is to comprehend why the denumerable infinite rows of infinite decimal expansions can be so effortless proven not to exhaust all the real numbers in that interval.

Well, now I get to think that the number obtained by diagonalization unambiguously detects the fact of the existence of cardinals far beyond the natural numbers.

There is a lack of mathematical reasoning in this post; neither intention to give a try; just an introductory fascination for Cantor's Paradise.

Greetings, Marcos.

 

[FactChecker]

Hi PF, once understood Cantor's diagonalization proof (originally for $[0,1]$), and regarding there is an algorithm to get from decimal to bynary expansion, it is easy to perform the proof in both fashions. At the same time, it is difficult; the essential doubt I have is to comprehend why the denumerable infinite rows of infinite decimal expansions can be so effortless proven not to exhaust all the real numbers in that interval.

Well, now I get to think that the number obtained by diagonalization unambiguously detects the fact of the existence of cardinals far beyond the natural numbers.

There is a lack of mathematical reasoning in this post; neither intention to give a try; just an introductory fascination for Cantor's Paradise.

Greetings, Marcos.

I don't know if it has been mentioned in the thread, but it is a standard proof by contradiction. Other threads probably explain it more but this one started with a more advanced understanding.

 

[jbriggs444]

I don't know if it has been mentioned in the thread, but it is a standard proof by contradiction. Other threads probably explain it more but this one started with a more advanced understanding.

The diagonal proof can be phrased as a proof by contradiction:

Assume that one has a complete list.
Construct an item not present on the list.
Contradiction.
So no list can be complete.

It can also be phrased as a direct proof:

Let L be an arbitrary list.
Construct an item not present on the list.
So L was not a complete list.
But L was arbitrary, so every list is incomplete.

If one is aiming to demonstrate that there is an entire array of cardinalities beyond that of the naturals then the real numbers are a waste of time. One should concentrate on the easier fact that the power set $P(S)$ has a cardinality strictly greater than the cardinality of the base set $S$.

So one has the cardinality of $\mathbb{N}$, the cardinality of $P(\mathbb{N})$, the cardinality of the power set of that. And so on, each strictly larger than the last.

 

[mathwonk]

and of course those are the same argument. I.e. the set of all binary sequences is equivalent to the power set of the natural numbers N, where a given sequence corresponds to the subset of N where zero occurs. Thus the "diagonal" argument that the set of these sequences is uncountable, i.e. that there is no surjection N-->P(N), translates to an argument there is no surjection f:S-->P(S). To wit, given any candidate map f, the subset T of S consisting of those elements x such that x does not belong to f(x), cannot be in the image of f. In the case of S=N, this says given any map f:N-->P(N), the sequence having 0 in position n if and only if 0 is not in position n of the sequence corresponding to f(n), is not in the image of f.

note this same argument shows the identity map from the set S of "all sets", to itself, is not surjective as well, "Russell's paradox"; thus no set contains all sets. I.e., the argument that P(S) is always larger than S, as jbriggs444 observes, shows that for every set there is a larger set, hence no largest set exists.

 

[PeroK]

As a postscript, here is a proof of the uncountability of any compact , Hausdorff set where no singleton is an open set. That includes the interval $[0, 1]$.



The proof is quite technical and relies on a couple of theorems about compact sets.