80
$\begingroup$

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.

$\endgroup$
  • 11
    $\begingroup$ Brian's answer correctly answers the question in the title -- but beware that you're not implementing the diagonalization process correctly in your example. The main diagonal if your list has digits $5, 5, 1, 5, \ldots$, whereas you're just taking the digits from the diagonal below that. First, here, the first number in your list is not being used at all (so there's be no reason you would expect to avoid that). Second you're forgetting that you're supposed to select digits that are (in a deterministic way) different from the diagonal you look at, not the diagonal digits themselves. $\endgroup$ – Henning Makholm Jan 12 '17 at 11:13
  • 2
    $\begingroup$ @pjc50 I think avoiding this issue is harder in binary. just consider the list where the diagonal goes 1,0,0,0,0,... - Of course it suffices that there is a base in which we can create a number that is not in the list. $\endgroup$ – Taemyr Jan 12 '17 at 13:16
  • 1
    $\begingroup$ I think "diagonalization" is used not the right term, since nothing is being made diagonal; instead this is about Cantors diagonal argument. It is a pretty common abuse though, the tag description (for the tag I will remove) explicitly warns against this use. $\endgroup$ – Marc van Leeuwen Jan 12 '17 at 14:11
  • 3
    $\begingroup$ What is with this huge influx of questions on the diagonal argument in the last two days? $\endgroup$ – Asaf Karagila Jan 12 '17 at 16:25
  • 1
    $\begingroup$ @AsafKaragila I thought of this question a while ago and when I saw another diagonal argument question it pushed me to ask this. $\endgroup$ – Hugh Jan 12 '17 at 17:00
94
$\begingroup$

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.

$\endgroup$
  • 29
    $\begingroup$ +1. This is also an advantage of developing Cantor's argument on $2^\omega$, rather than $\mathbb{R}$, and then separately exhibiting a bijection between the two. $\endgroup$ – Noah Schweber Jan 12 '17 at 0:18
  • 1
    $\begingroup$ It took me a while to get my head around the 6 and 7 replacement but I get it now, thanks! $\endgroup$ – Hugh Jan 12 '17 at 0:26
  • $\begingroup$ @Hugh: You’re welcome! $\endgroup$ – Brian M. Scott Jan 12 '17 at 0:26
10
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I realise now that I remembered the proof incorrectly from lectures a few years ago $\endgroup$ – Hugh Jan 12 '17 at 16:58
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.