Is the Cantor diagonal argument conclusive?

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

any comments?

 

[Hurkyl]

Cantor assumes in using his algorithm that the number of positions equals the number of elements,
or intentionally omits this fact.

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.

The list is never square because the columns increase at a linear rate and the rows increase at an exponential rate.

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

The altered diagonal sequence can only be new if it differs in at least one position for all numbers listed.

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

By using only a square portion of the list in the algorithm, the diagonal is by definition always incomplete.

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.

 

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

 

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

 

[d_leet]

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.

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.

 

[phyti]

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

Who decides what is logical and what is not?

 

[Hurkyl]

Who decides what is logical and what is not?

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.

 

[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:

 

[JustinLevy]

While I agree that the set of real numbers is not countably infinite, this diagonal argument 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.

 

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

 

[NateTG]

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.

Another option is to specify that the counter-example is created by taking the example, and replacing each digit with [itex]d+2 \rm{(mod 10)}[/itex]. Since the [itex]\bar{9}[/itex] 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.

 

[phyti]

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.

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

 

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

 

[JustinLevy]

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.

I like that answer. Very very simple.

Thanks!

 

[fopc]

While I agree that the set of real numbers is not countably infinite, this diagonal argument 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.

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.

 

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

 

[HallsofIvy]

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.

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!

 

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

 

[mathwonk]

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

 

[HallsofIvy]

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

Then you are faced with a serious problem!

 

[hachem]

Then you are faced with a serious problem!

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

 

[CRGreathouse]

Would that not, in an actual infinite, enumerate all possible combinations?

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:
[tex]x_n=1/n[/tex]
Cantor's argument shows that no matter what arbitrary sequence you choose, it can't enumerate the reals.

 

[hachem]

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:
[tex]x_n=1/n[/tex]
Cantor's argument shows that no matter what arbitrary sequence you choose, it can't enumerate the reals.

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?

 

[Hurkyl]

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?

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.

 

[hachem]

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.

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

 

[Hurkyl]

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

I will give you the benefit of the doubt and assume you simply misread what I wrote. I will state it with more precision, and add an annotation in blue:


. Suppose you have a list of real numbers. (which may or may not contain all of the real numbers)
. Suppose you have an enumeration of said list.
. Applying Cantor's diagonal argument gives you a number not in the list.
. Therefore, said list cannot be a list of all real numbers.


You claim to have enumerated a list of real numbers. Therefore, your list does not contain all real numbers.

 

[hachem]

I will give you the benefit of the doubt and assume you simply misread what I wrote. I will state it with more precision, and add an annotation in blue:


. Suppose you have a list of real numbers. (which may or may not contain all of the real numbers)
. Suppose you have an enumeration of said list.
. Applying Cantor's diagonal argument gives you a number not in the list.
. Therefore, said list cannot be a list of all real numbers.


You claim to have enumerated a list of real numbers. Therefore, your list does not contain all real numbers.

i will grant you the same benefit and point out that the construction i propose is based on the diagonal argument. every new sequence is the diagonal of the preceding sequences.

 

[Hurkyl]

Does your construction enumerate a list of reals? If so, then it's missing one.

 

[hachem]

i am getting tired of authoritarian assertions, bold or blue. could somebody please come with a rational, logical argument?
By the way, i will grant you this: my construction does not enumerate the reals in an ordered sequence. but it still seems to me that any real would be eventually enumerated. as far as the syntax is concerned, binary sequences were used by Cantor himself as expression of real numbers.

"eventually" here is misleading. You can put reals in a one to one correpondence with the natural numbers, (in an unordered sequence) butyou cannot reach the end of an infinite sequence be it of reals or natural numbers. what counts is that in this construction you can not point at a real which will not be eventually output by the program.

 

[Hurkyl]

i am getting tired of authoritarian assertions, bold or blue. could somebody please come with a rational, logical argument?

Cantor already did. It's not my fault of you refuse to understand it.

By the way, i will grant you this: my construction does not enumerate the reals in an ordered sequence.

Just what do you think the word "enumerate" means? The simplest meaning to use is that an "enumeration of a set X" is a function that assigns to each natural number an element of X, such that each element of X is assigned to exactly one natural number. (i.e. a bijective function N->X)

In terms of computer science, an algorithm enumerates a set X if and only if every output the algorithm prints is an element of X, and every element of X is eventually printed.

Because an algorithm prints things one after another, they can be indexed by natural numbers. In particular, an algorithm cannot output an infinite collection of things, and then still do more stuff.

There are ways to generalize the notion of "algorithm" to allow it to proceed for a transfinite ordinal number of steps. However, the number of steps has to be uncountable if your "algorithm" is to print every real number. (and for the most natural generalizations I can imagine, it is known that the "algorithm" cannot be written explicitly)

 

[hachem]

to enumerate means to every member of a set assign a natural number in such a way as not to miss any member of the set. it does not mean that the set should already be ordered, just that your procedure does not miss any member.
the simplest way of not missing any member of the set (let us say they are all in box A) is to take them in an arbitrary fashion and put them one by one in a box B, and while doing so, assigning a (consecutive) number to each.
The question is therefore: does my construction ensure that no real will be left over in box A? Once they are in box B they will be enumerated even if the numeral assigned to each real will be completely arbitrary.

 

[hachem]

Cantor already did. It's not my fault of you refuse to understand it.


Just what do you think the word "enumerate" means? The simplest meaning to use is that an "enumeration of a set X" is a function that assigns to each natural number an element of X, such that each element of X is assigned to exactly one natural number. (i.e. a bijective function N->X)

In terms of computer science, an algorithm enumerates a set X if and only if every output the algorithm prints is an element of X, and every element of X is eventually printed.

Because an algorithm prints things one after another, they can be indexed by natural numbers. In particular, an algorithm cannot output an infinite collection of things, and then still do more stuff.

There are ways to generalize the notion of "algorithm" to allow it to proceed for a transfinite ordinal number of steps. However, the number of steps has to be uncountable if your "algorithm" is to print every real number. (and for the most natural generalizations I can imagine, it is known that the "algorithm" cannot be written explicitly)

you should really read Cantor. The diagonal argument is only valid for infinite sequences. a finite sequence is by definition incomplete.

 

[Hurkyl]

to enumerate means to every member of a set assign a natural number in such a way as not to miss any member of the set. it does not mean that the set should already be ordered

The meaning of the adjective "ordered" refers to the fact that if we swap two of the labels, we consider that a different sequence.

e.g. the ordered sequences (1,2,2,3) and (2,1,3,2) are different. But the unordered sequences {1, 2, 2, 3} and {2, 1, 3, 2} are the same. (I'm using {..} to denote a multiset here, not an ordinary set)

The question is therefore: does my construction ensure that no real will be left over in box A? Once they are in box B they will be enumerated even if the numeral assigned to each real will be completely arbitrary.

You have labelled countably many real numbers. Therefore, there are uncountably many real numbers without label. Cantor's diagonal argument explicitly constructs a real number that fails to be labelled.

For any natural number n, let f(n) denote the real number that you labelled with n.

For any real number s, let s<n> denote the n-th digit to the right of the decimal expansion of s. (If a number has two decimal expansions, use the one that ends in all 0's instead of the one that ends in all 9's)

Define a real number r whose n-th digit is given by

[tex]
r\langle n \rangle = \begin{cases}
4 & f(n)\langle n \rangle \neq 4 \\
6 & f(n)\langle n \rangle = 4
\end{cases}
[/tex]

Observe that, for every n, we have the following fact:

[tex] r\langle n \rangle \neq f(n) \langle n \rangle[/tex]

and therefore

[tex]r \neq f(n)[/tex].

In other words, r is unlabelled.

 

[hachem]

we are turning in circles. I am questioning the validity, or at least the universality, of Cantor's argument. you reply by explaining to me what cantor's argument means. i wish you were less didactic and more to the point.
i am using the diagonal argument to show that cantor's conclusion is not universally valid. you can chose to restrict the definition of the concepts involved in such a way as tp preserve the conclusion, but that is surely not satisfactory.
So please, show me if and where i am wrong, not in general because everybody thinks cantor is right, but because somewhere in my argumentation there is something that does not add up. i am still waiting.
in short, my argumenation is itself a diagonal argument> i use the form used by cantor to prove him wrong.

 

[D H]

There are ways to generalize the notion of "algorithm" to allow it to proceed for a transfinite ordinal number of steps.

This is what hachem has done with his algorithm. The diagonalization step is itself an infinite loop. What his algorithm does in essence is to generate the power set of aleph-null. In other words, it does not generate an enumerable list.