1
$\begingroup$

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.

$\endgroup$
5
  • 9
    $\begingroup$ You just avoid to choose $9$ as the next digit in the diagonal argument, there's plenty of other digits to choose from, namely $1,2,3,4,5,6,7,8$. $\endgroup$
    – egreg
    Commented Mar 17, 2018 at 12:11
  • 1
    $\begingroup$ Numbers ending with $999\cdots $ are equivalent to a number with a terminating decimal representation. Even $\frac{1}{3}$ has a unique representation in the sense of the intent of the question. $\endgroup$
    – Peter
    Commented Mar 17, 2018 at 12:16
  • 3
    $\begingroup$ And, in any case, $\Bbb Q$ is countable. $\endgroup$
    – Martín-Blas Pérez Pinilla
    Commented Mar 17, 2018 at 12:18
  • 3
    $\begingroup$ @MauroALLEGRANZA There's no assumption that the countable list contains every real in $(0,1)$; you just produce a number that's not contained in the list. Hence non countable list can contain all numbers in $(0,1)$. $\endgroup$
    – egreg
    Commented Mar 17, 2018 at 13:20
  • $\begingroup$ @MauroALLEGRANZA It seems that you're misunderstanding thhe objection. Has nothing to do with the list containing every real onlle once. The objection is this: Ok, the procedure produces a decimal sequence that's not on the original list of decimal sequences. But how do you know that it doesn't represent a real number that is on the list, via a different decimal representation? $\endgroup$
    – David C. Ullrich
    Commented Mar 17, 2018 at 15:13

3 Answers 3

Reset to default
7
$\begingroup$

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)

$\endgroup$
3
  • $\begingroup$ I agree. But does my argument at least make sense for the binary version of Cantor's proof? In the sense that, given the number made of flipped bits, Cantor would have no choice for the digits. Sure, he could convert the numbers to another base, construct another number not contained in my set, and convert it back to binary. But by simply flipping the bits, given my theorem above, it seems to me that the counter-proof is not enough. Or am I missing something? $\endgroup$
    – Reiza
    Commented Mar 17, 2018 at 12:19
  • $\begingroup$ @Reiza: Yes, multiple representations is a technical detail that needs to be dealt with for the specific application of the diagonal argument to the case of proving the real numbers are uncountable. My answer points out a couple different ways to deal with it. $\endgroup$
    – user14972
    Commented Mar 17, 2018 at 14:05
  • $\begingroup$ thanks! I have no doubt about the validity of your answer. My point is now simply that students of mathematics are being taught this theorem's proof incorrectly, and you have to be a bit more careful than simply flipping bits on the diagonal. $\endgroup$
    – Reiza
    Commented Mar 17, 2018 at 16:38
3
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ Of course this simply corresponds to working in base 4 instead. $\endgroup$
    – hmakholm left over Monica
    Commented Mar 17, 2018 at 13:28
  • $\begingroup$ That's a good point. I wanted to give an answer that doesn't require switching base. If we could, then we'd just go back to base $10$, and the whole thing is trivial $\endgroup$
    – Dylan
    Commented Mar 17, 2018 at 13:31
2
$\begingroup$

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. :)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .