1
$\begingroup$

Possible Duplicate:
How does Cantor's diagonal argument work?

It seems to me that if you have an infinite list of unending decimal numbers between $(0,1)$:

0.xxxxxxxxx... 0.xxxxxxxxx... ... 

and you want to generate a number in $(0,1)$ that is not on the list, then Cantor's diagonalization does not work. For example, consider

0.xxy..... 

where each x can be any value, and y, being the third, must be different from the the third digit in the third number, is any number except the third digit in the third number.

In this case, we know our number is different from the third number, and because of how we have been writing it (first two digits are appropriately distinct from the first two numbers), we know it is unique so far on the list. However, because this is an infinite list which claims to contain all real numbers between 0 and 1, the number we have written exists somewhere further down the list.

So we continue. We add a fourth digit, which differentiates it from the fourth number in the list. Facing the same problem, we continue to the fifth, then the sixth, and so on...

The point of this, as I understand it, is to show that we can write a number which is not already in this list. However, at any point, there are an infinite number of numbers left in the list, one of which is equal to what we have written. So we must continue on to infinite...

Since we will never reach a point where there are 0 numbers left in the list, we will never finish writing a number which is not on the list. Every digit we add makes it different from more and more numbers on the list, but never from EVERY number on the list. So, in practice, we CAN'T generate a number which is not on the list.

This seems to make perfect sense to me, but it also seems to be incorrect. Can someone please explain why?

  • 1
    The classic [An Editor Recalls Some Hopeless Papers](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.27.6154&rep=rep1&type=pdf) by W. Hodges contains a remarkably (for its title) respectful analysis and discussion of this fallacy.2011-09-01

3 Answers 3

3

Perhaps it is better to think of the Cantor diagonalization as defining a number rather than constructing one. Let me explain what I mean.

If one defines a function $f(x) = x^2$, you presumably have no objection to the fact that a graph of this function exists (a parabola). There are, however, a vast infinity of possible values for $x$. If you bring your complaint about diagonalization to bear on the function $f$, then you would have to conclude something along the lines of "There are an infinite number of possible inputs, so I can't ever graph them all. Thus, no such graph exists."

There is a way to describe the function without listing each of its ordered pairs, however. Given any value of $x$, one can quickly compute the output of the function by squaring it. Thus, one never needs to graph the entirety of the parabola to demonstrate its existence. It is simply defined as "that function whose output is the square of its input".

In the same way, the number defined by the Cantor diagonalization process never need be written out in its entirety to exist. It is simply defined as "that number whose $n^\text{th}$ digit is obtained by adding 1 (mod 10) to the $n^\text{th}$ digit of the diagonal".

0

What you show is that if you stop diagonalization after a finite number of steps it doesn't show that the list is incomplete. This is correct; you need an infinite number of steps to obtain the result.

  • 0
    @Jim: The procedure doesn't say what the next thing on the list is because it's not defining a list but rather showing a property of any list: that is does not contain all numbers in [0, 1].2011-09-01
0

Diagonalization defines a real number, which is an infinite object. You seem to be doubting the existence of numbers with nonterminating decimal expansions (such as 1/3).

  • 0
    Yes, yes, I understand these issues, and they are beside my point. I'm merely pointing out that regardless of how much joe blow might know about the real numbers, he is probably comfortable with the idea that an infinite decimal, periodic or not, can represent a real number.2011-09-01