Disproving Cantor's diagonal argument

Question

I am familiar with Cantor's diagonal argument and how it can be used to prove the uncountability of the set of real numbers. However I have an extremely simple objection to make. Given the following:

Theorem: Every number with a finite number of digits has two representations in the set of rational numbers.

Proof: It follows from the fact that 0,9999... = 1, that any integer $n$ can be represented as $(n-1),9999...$ This similarly works for rational numbers with finite digits, as follows: let $n_i$ be the $i$-th digit after the comma of a rational number with a finite number of digits $k$. Then $n,n_1n_2...n_k = n,n_1n_2...(n_k-1)999...$.

Now, going through Cantor's diagonalization argument, assume that I built what I claim to be an exhaustive list of all real numbers in binary representation. Then, Cantor would claim that the number created by concatenating the negated $i$-th digit of the $i$-th number is not contained in my list. To which I would reply: "Yes, but can you prove that your number is not the alternative representation of one already present in the list?", following the theorem above.

How does my remark not disprove or at least require further efforts in Cantor's proof? Has this point already been made?

EDIT:

The point is invalid if the base is different from 2, giving Cantor the choice of avoiding the more "offending" decimals 9 and 0. However, in the case of binary representation, which is the most commonly thought in universities, how could he make sure that happens by simply flipping bits as described above? It seems to me that he would have to go through the rather complex process of converting the binary number to another base, flipping its digits avoiding 0s and 9s, and converting back.

Answer 1

There is a simple fix to this particular technicality. The only cases of multiple representations are numerals that:

• End in repeated $9$'s
• End in repeated $0$'s

To avoid these, when using the diagonal argument to construct a new numeral, we could decide to use only the digits $3$ and $6$. Even with this restriction we still have enough freedom to make the diagonal argument work and construct a numeral not appearing on the given list.

But by making this restriction, the numeral constructed by the diagonal argument is guaranteed to represent a real number that has only one decimal representation.

---

Note, however, that somewhere in the theory you have (or are going to) show that the set of real numbers have the same cardinality $2^{\mathbb{N}}$; that is, there is a bijection between the set of real numbers and the set of binary sequences. In my opinion, the most efficient way to develop the overall theory is:

• Deal with this whole multiple-representation issue when showing that the reals are in bijection with binary sequences.
• Apply Cantor's argument to binary sequences.

(actually, the first bullet point is probably best done in the contest of general cardinal arithmetic)

Answer 2

The new number should ideally has only one single representation. In binary, this means you'd need to avoid an arbitrarily long sequence of $1$s or $0$s. One way to work around this restriction is to pick the digits in pairs: The first 2 digits are different from those of the first number, the 3rd and 4th digits (as a pair) are different from those of the second number, and so on.

The rules are as follows

• If the current digit pair is $01$, pick $10$ for the new number
• If the current digit pair is $10$, pick $01$ for the new number
• If the current digit pair is $00$ or $11$, pick either $01$ or $10$

This way, the most a digit can repeat is two times, since you actively avoid the sequences $00$ and $11$.

Answer 3

Most people who think they are familiar with Cantor's Diagonalization argument, are not. They are familiar with a simplification of it for High School students. Chief among the simplifications are the facts that it was never about real numbers, and it isn't a proof by contradiction (it doesn't assume that the entire set it uses can be enumerated).

Following Wikipedia's outline, but correcting the simplifications:

1. What I call a Cantor String is an infinite-length string of 0's and 1's.
2. Let T be the set of all possible Cantor Strings.
3. Let s(n) be a function that produces a Cantor String for all n>=1, and S be the set of all the Cantor Strings it produces.
4. Let D be the string made by taking the nth character of s(n) and reversing the 0's and 1's.
5. D is a Cantor String, so it is a member of T.
6. D can't be a member of S, since it differs from every s(n) in the nth character.
7. This proves "If S can be enumerated, then S is not all of T."
8. The two statements "If A, then B" and "If not B, then not A" are logically equivalent. So proving one proves the other.
9. If S is all of T, then S can not be enumerated. QED.

Now, you can interpret each Cantor String as the binary representation of a real number between 0 and 1. Your issue is that two different Cantor Strings can represent the same number, making step 6 invalid. This is only a problem if use that interpretation. So don't. :)