How does the Cantor's diagonal argument that $(0,1)$ is uncountable deals with the fact some real numbers have two different decimal expansions?

Question

I recently learnt Cantor's argument that proves $(0, 1)$ is uncountable. Basically, the argument goes: first assume the contrary, therefore there is a bijection $$f: \mathbb{N} \rightarrow (0, 1)$$ that $$f(1) = 0.a_{11}a_{12}a_{23}...$$ $$f(2) = 0.a_{21}a_{22}...$$ and in general $$f(n) = 0.a_{n1}a_{n2}...$$ where $a_{nm} \in \mathbb{N}, 0 \le a_{nm} \le 9$. Then we construct a number $$s = 0.b_{11}b_{12}...$$ where each $b_{1n} \ne a_{nn}$. The argument then goes that since the new number $s$ differs with any $f(n)$ with at least one digit, it cannot equal to any $f(n)$, therefore this function $f$ is not surjective, leads to a contradiction.

However, there are cases that even if two numbers $a$ and $b$ in $(0, 1)$, when written in decimal form, differs in some digits, they can still be equal to each other. For example: $$0.1000000... = 0.0999999...$$ How, then, can this argument still hold then?

Answer 1

To be a useful bijection, $f$ needs to be $f: \mathbb{N} \rightarrow (0,1)$. Note that, since $f$ is assumed to be bijective, each value of $f(n)$ is unique, regardless of how it is represented.

Assuming we are using base $10$, the $b_{nn}$ can be chosen so they are not equal to $0$ or $9$. Then, no matter how the list is represented, it will not include the new number.

Answer 2

Suppose you consider just the subset of $(0, 1)$ that consists of numbers whose decimal representation does not include an infinite suffix of identical repeating digits. Even this subset cannot be placed into a bijection with the natural numbers, by the diagonal argument, so $(0, 1)$ itself, whose cardinality is at least as large as this subset, must also be uncountable.

Answer 3

You can choose every digit $b_j$ to lie in $\{1,2\}$ say, and so avoid a decimal ending in a string of zeroes or nines.

Alternatively there are countably many decimals ending in all zeroes or all nines, so you can insert them in your original list of decimals. Then your $s$ is also guaranteed no to end in all zeroes or all nines.

Answer 4

"How, then, can this argument still hold then?" Because you learned a misrepresentation of it. Nothing is overtly incorrect in what you learned, but it is incomplete. And there are several parts of it that raise more questions than they solve, and your question is one of them.

The proposition Georg Cantor wanted to prove (from a translation at http://www.logicmuseum.com/cantor/diagarg.htm) was "there is an infinite manifold, which cannot be put into a one-one correlation with the totality of all finite whole numbers". In modern terminology, that means "There is an infinite set that has no bijection with $\mathbb N$".

Cantor's first attempt to prove this proposition used the real numbers at the set in question, but was soundly criticized for some assumptions it made about irrational numbers. Diagonalization, intentionally, did not use the reals. "There is a proof of this proposition that is much simpler, and which does not depend on considering the irrational numbers."

Wikipedia calls the set he used $\mathbb T$, which is the set of all functions of the form $$t: \mathbb{N} \rightarrow \mathbb \lbrace '0', '1' \rbrace.$$These are infinite-length strings of '0's and '1's. Yes, they can be used to represent real numbers in [0,1] in binary. But "0111..." is different than "1000...", while 0.0111...=0.1000... .

Cantor assumed the existence of a function of the form$$s: \mathbb{N} \rightarrow \mathbb T.$$ He did not assume that this function was an injection, although this is mostly irrelevant. He also did not assume that this function was a surjection. What diagonalization proves, directly and not by contradiction, is that any such function cannot be a surjection.

Answer 5

Cantors argument was not originally about decimals and numbers, is was about the set of all infinite strings.

However we can easily applied to decimals.

The only decimals that have two representations are those that may be represented as either a decimal with a finite number of non-$9$ terms or as a decimal with a finite number of non-$0$ terms. If we use the replacement scheme so that $9$s go to something other that $0$ and $0$s go to something other than $9$s then the resulting value that is "not on the list" will not be one of these numbers with two representations. So that is not an issue.

Example: If our replacement scheme is to replace everything with $5$s except we replace $5$ with $6$. The resulting number will 1) contain only $5$s and $6$ and thus have only one representation and 2) will not "be on the list".