How do we know that Cantor's diagonalization isn't creating a different decimal of the same number?

Question

Edit: As the comments mention, I misunderstood how to use the diagonalization method. However, the issue I'm trying to understand is a potential problem with diagonalization and it is addressed in the answers so I will not delete the question.

Cantor's diagonalization is a way of creating a unique number given a countable list of all reals.

I can see how Cantor's method creates a unique decimal string but I'm unsure if this decimal string corresponds to a unique number. Essentially this is because $1 = 0.\overline{999}$.

Consider the list which contains all real numbers between $0$ and $1$:

$0.5000 \mathord\ldots \\ 0.4586 \mathord\ldots \\ 0.3912 \mathord\ldots \\ 0.3195 \mathord\ldots \\ 0.7719 \mathord\ldots\\ \vdots$

The start of this list produces a new number which to four decimal places is:

$0.4999 \mathord\ldots$

But $0.5$ was the first number and $0.4\overline{999} = 0.5$ so this hasn't produced a unique number.

Of course my list is very contrived, I admit that it's hard to imagine a list of the reals where numbers would align nicely to give a problem like this (since some numbers have no nines). However, I can't see a good reason why such an enumeration of numbers would be impossible.

Answer 1

This is in fact a potential problem if the proof is carelessly stated, but it’s easily avoided: if the $n$-th decimal digit of the $n$-th number on the list is $7$, we replace it by $6$, and if it’s not $7$, we replace it by $7$. The only numbers in $(0,1)$ with two decimal representations are those with one representation ending in an infinite string of nines and the other in an infinite string of zeroes, and this version of the argument clearly doesn’t produce a number of either of those forms.

Answer 2

Let's talk about numbers (which are numbers) and their representation (which are a list of digits).

You says:

Cantor's diagonalization is a way of creating a unique number given a countable list of all reals.

Not exactly, Cantor's diagonalization is a way of creating a unique representation given a countable list of representations of real number. (not all number).

I can see how Cantor's method creates a unique decimal string but I'm unsure if this decimal string corresponds to a unique number. Essentially this is because $1 = 0.\overline{999}$

The method create an unique decimal string (ie. representation). And a representation match only one number.

• You may have 2 representation of 1 number.
• But from 1 representation, you only have 1 number.

Let add a theorem (this one is hard):

• If the representation doesn't end with an infinite string of 9 or 0, the representation is unique.

Now, you present an hypothetical list of representations of all real numbers between 0 and 1.

You use Cantor diagonalization to extract an unique diagonal representation that represent an unique diagonal number.

You say:

But 0.5 was the first number and $0.5 = 0.4\overline{999}$ so this hasn't produced a unique number.

This has produced a unique representation $0.4\overline{999}$ so it match an unique number which is $1/2$. Yes this number has two representation but there is only one unique number here.

It appears that the diagonal representation ($0.4\overline{999}$) and the first representation of the list ($0.5\overline{000}$) represent the same number ($1/2$ is another way to represent it).

In other word, you find out that the diagonal number (which is a real number in (0, 1)) is represented in your list of representation of all real numbers in (0, 1).

That's coherent and fine.

Now you want to build a number that is not represented in the list. And you will build a representation of it from the diagonal representation.

You will use @BrianM.Scott method and build a representation of a number that:

• Doesn't contains any 0 or 9. So it's the unique representation of a given number.
• Doesn't match any representation present in the list.
• Represent a number in (0, 1)

That it, you find a number that has a unique representation and this representation is not in the list.

And you prove that your hypothetical list doesn't exist.

Answer 3

As Henning Makholm stated in his comment, you're supposed to select digits that are different from the diagonal you look at, not the diagonal digits themselves. Make sure you also select digits different from $9$ and $0$, and the problem is avoided

Answer 4

Cantor's Diagonal proof was not about numbers - in fact, it was specifically designed to prove the proposition "some infinite sets can't be counted" without using numbers as the example set. (It was his second proof of the proposition, and the first was criticized because it did.)

What Cantor actually used, were infinite length strings that combine only two different characters. He used "m" and "w." But modern High School and Middle School students have experience with infinite decimal expansions, and it is easier to teach new concepts to them in terms of what is already familiar. The point is, that there is no ambiguity in saying that two strings are different if they have different characters in at least one position.

Another point that is taught poorly, is that the proof doesn't have to be a proof-by-contradiciton. Many people have a justifiable objection to assuming statement A, and then proving that not(A) follows from it. All it really proves is that there is something wrong in the circle that leads from A to not(A), not that it has to be the assumption of A. Which is why so many people try to invalidate one of the steps - what you claim here one of the ways they try (and yes, it can be gotten around easily, as stated in other answers).

Cantor only assumes that you have a countably infinite set of some of these strings. Diagonalization proves that there is a string not in your set. Since "If A then B" is logically equivalent to "If not(B) then not(A)," this proves that if you have a set of all such strings, then it can't be counted.

Elegant, no?