# Cantor diagonal argument-?

1. May 14, 2007

### phyti

Cantor diagonal argument-???

The following eight statements contain the essence of Cantor's argument.

1. A 'real' number is represented by an infinite decimal expansion, an unending sequence of integers
to the right of the decimal point.

2. Assume the set of real numbers in the interval[0,1] (which excludes 0 and 1)
is countably infinite, (can be paired 1 to 1 with the set of integers).

3. Assume a list exists containing all the numbers in that set.

4. The list begins with these sequences (in random order),

.4075501...
.9240732...
.2110208...
.0345678...
.5161705...
.8978675...
.3000333...

5. Select a diagonal sequence from the list as shown, .4215773... and
substitute a different integer for all positions, e.g. (.5326884...), call the altered sequence x.

6. If x is different at the position of intersection with each successive number,
it is not included in the list.

7. If the list does not include x it is incomplete which contradicts statement 3.

8. If a complete list does not exist, statement 2 if false.

Statement 1 is a definition.
Statement 2 is Cantor's postulate.
Statement 3 is his prop.
Statement 4 is a continuation of the assumptions.
Statement 5 is an acceptable algorithm.
Statement 6 is in error.

Cantor assumes in using his algorithm that the number of positions equals the number of elements,
or intentionally omits this fact.
The list is never square because the columns increase at a linear rate and the rows increase at an exponential rate.
The altered diagonal sequence can only be new if it differs in at least one position for all numbers listed.
By using only a square portion of the list in the algorithm, the diagonal is by definition always incomplete.
You cannot make 10^n comparisons with a diagonal containing n elements,
therefore the algorithm cannot determine statement 6 as true or false, nor the dependent statements 7 and 8.

2. May 14, 2007

### Hurkyl

Staff Emeritus
He assumed that in step #2: the number of positions is countably infinite by definition of decimal notation. In step #2, he assumes that the set [0, 1] (i.e. the number of rows) is also countably infinite.

Therefore, the number of rows is equal to the number of columns: they are both aleph null.

I don't see anything in this argument that varies in size.

And it does. By its very construction, the n-th entry in the list differs from the altered sequence in the n-th position.

The list is square. What "portion" are you talking about? Cantor never restricts his attention to a portion of the rows nor to a portion of the columns.

3. May 15, 2007

### matt grime

And, if you don't like the argument then just think of it as showing that for any countable set of real numbers, there exists another different from all of them, hence the real numbers are not countable.

Now, your criticisms are fairly common misconceptions. There is also nothing logical in them. Nothing increases at any rate. Where does anyone mention rates of anything? (Apart from you.)

4. May 15, 2007

### EnumaElish

So how do we know that the new number is not already in the list? E.g.,
0.912...
0.040...
0.948...
..........
So the new number is 0.948..., which is included in the list.

Edit: Never mind, I see that I missed the "altered sequence" step.

Last edited: May 16, 2007
5. May 15, 2007

### d_leet

Why is the new number 0.948...? The new number is chosen to differ from the nth entry of the list in the nth place past the decimal, this doesn't satisy those criteria.

6. May 15, 2007

### phyti

Who decides what is logical and what is not?

7. May 15, 2007

### Hurkyl

Staff Emeritus
When a formal argument is presented, anyone capable of executing the algorithm for verifying a deductive argument.

When a formal argument is not presented, then someone trained in the subject matter and in the art of logic would be the most qualified to make such a judgement.

8. May 16, 2007

### NateTG

Wow. I must have been gone for a long time. The first thing that I though when I saw this was 'hey, I haven't seen one of these in a while'.

Phyti, there are plenty of good explanations out there for the cantor diagonal argument, and plenty of silly threads about it here. (Unless they've been sensibly purged.)

Bork! Bork! Bork!
:zzz:

9. May 16, 2007

### JustinLevy

While I agree that the set of real numbers is not countably infinite, this diagonal arguement has always bothered me. It no doubt is due to some misunderstanding I have, but I'd appreciate any explanations you may have.

The problem that always nagged at me with this argument is that there seems to be an implicit assumption that decimal representation is unique... it is not. For instance:
0.200000...
0.199999...
represent the same number but EVERY digit differs.

Is there some way to uniquely represent any real number with a string of integers? If so, it would make me feel more comfortable thinking about this proof.

Last edited: May 16, 2007
10. May 16, 2007

### matt grime

Yes. Declare that you only ever use expansions that do not end in an infinite number of 9s. That is suffcient. Or just do the argument on decimal expansions which consist entirely of 0s and 1s. Or imagine that those are base 11 expansions but we never use any numbers with the A in them (base 11 digits being 0-9 and A). In any of those cases all decimal strings are unique.

11. May 16, 2007

### NateTG

Another option is to specify that the counter-example is created by taking the example, and replacing each digit with $d+2 \rm{(mod 10)}$. Since the $\bar{9}$ equivalence will only change a digit by 1 mod 10 this is sufficient to guarantee that there is no alternative expression of the counter-example in the list.

12. May 17, 2007

### phyti

Doesn't the decimal expansions use the base 10, not base 2?

13. May 18, 2007

### matt grime

I'll repeat myself: use the decimal expansions of numbers that consist only of 0s and 1s. This is a subset of all real numbers, and an uncountable one at that.

14. May 18, 2007

### JustinLevy

I like that answer. Very very simple.

Thanks!

15. May 19, 2007

### fopc

The message is pretty clear.
Either remove the nonuniqueness (suggested in post 10),
or state an air-tight rule for producing each decimal in the altered sequence, s (suggested in post 11).
There are many air-tight rules. But here's one that isn't.

Rule: For each digit d encountered along the diagonal, increment it by 1 (or set it to 0, if d=9);
put the result in the appropriate slot of s.

Surprisingly, this is essentially the same rule given by Whitehead and Russell (Vol.1 p.64).
I suspect both gentlemen, at the time, knew about the nonuniqueness problem.
Probably just an oversight; as I said, the rule is flawed.

Here's just a few lines of an example:

0.29999999...
0.79111111...
0.77911111...
0.77791111...
0.77779111...
...
...
...

The stated rule will generate 0.30000..., which
equals the the first line. It can be done for
any number that has 2 decimal representations because
one of them will have a string of trailing 9's.

Last edited: May 19, 2007
16. Dec 19, 2007

### hachem

I am sure I am overlooking some simple logical point but could you
please tell me what you think of the following argumentation?
The objective is to enumerate all possible reals, that is to prove
that there is an alternative to Cantor's diagonal argument. I do
this by construeing as it were the diagonal of the diagonal.
In pseudocode (and only the main lines):
1- ouput an arbitrary infinite binary sequence
2- output a second, different from the first, infinite binary sequence
3- infinite loop: construe and output the diagonal of the preceding
sequences.
Would that not, in an actual infinite, enumerate all possible combinations? And by numbering each output sequence, starting with one, we would be putting in a one-to-one-correspondance the reals with the natural numbers.

Last edited: Dec 19, 2007
17. Dec 19, 2007

### HallsofIvy

What do you mean by "an actual infinite"? In any case, if you could do that, you would be proving that the set of all real numbers is countable and the whole point is to prove that it is not countable!

18. Dec 19, 2007

### hachem

the whole point for me is to prove that reals are countable, or at least that the diagonal argument as used by Cantor is not sufficient to prove otherwise
As for ther actual infinite. maybe it is best if i drop it. it is not necessary for the argumentation.

19. Dec 25, 2007

### mathwonk

or just restrict to decimals whose expansion only contains zeroes and 1's.

20. Dec 26, 2007

### HallsofIvy

Then you are faced with a serious problem!

21. Dec 26, 2007

### hachem

that is not much of an argument, is it? you care to elaborate?

22. Dec 26, 2007

### CRGreathouse

No, because there is no such enumeration. If you think there is, try to construct such an arbitrary sequence. Here is one arbitrary sequence which meets you rules, but does not contain all reals:
$$x_n=1/n$$
Cantor's argument shows that no matter what arbitrary sequence you choose, it can't enumerate the reals.

23. Dec 26, 2007

### hachem

that there are enumerations that do not contain all reals is beyond doubt. the question is whether there is not a single enumeration that contains them all. could you show me that mine doe not either?

24. Dec 26, 2007

### Hurkyl

Staff Emeritus
CRG already did -- that sequence is something your pseudocode could output. Therefore, you cannot show that your pseudocode enumerates of all reals.

And, as CRG said, Cantor's argument shows that any enumerated lists of real numbers cannot contain all real numbers. Do you understand what that statement says? It is a theorem, and it implies that if you have an enumerated list of real numbers, then it cannot be an enumeration of the reals.

Last edited: Dec 26, 2007
25. Dec 26, 2007

### hachem

or that the theorem is false. you should check your definition before putting bold assertions.