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

 

[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:
x_n=1/n
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:
x_n=1/n
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)[/color]
. 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)[/color]
. 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

<br /> r\langle n \rangle = \begin{cases}<br /> 4 &amp; f(n)\langle n \rangle \neq 4 \\<br /> 6 &amp; f(n)\langle n \rangle = 4<br /> \end{cases}<br />

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

r\langle n \rangle \neq f(n) \langle n \rangle

and therefore

r \neq f(n).

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.

 

[hachem]

everybody seems keen to restrict the meaning of enumerate to a specific form of enumerating. for me it means notning more than a way to assign a numeral in consecutive order of processing (the first you take out of box A gets the number 1, the second the number 2, etc). What you must do to get the items out of box A into box B is irrelevant, as long as you process them all. Now the point is that the procedure itself must ensure that we do not miss any item in box A. does my procedure ensure that, if not, what is wrong with it?
furthermore, speaking of aleph-null presupposes the validity of the diagonal argument, which, once again, is put here to the question.
more precisely, whether the diagonal argument, which is in itself a valid form of argumentation, is sufficient to sustain cantor's conclusion of the un-enumerability of reals (and therefore of the existence of different infinites).

 

[D H]

An non-finite enumerable set can be placed in one-to-one with the integers. You are assuming your algorithm generates an enumerable set. It does not. Your diagonalization step ensures that this is the case.

 

[hachem]

quote D H :"An non-finite enumerable set can be placed in one-to-one with the integers. You are assuming your algorithm generates an enumerable set. It does not. Your diagonalization step ensures that this is the case."
if you mean by that that being a form of diagonal argument is sufficient to sustain the conclusion that the algorithm is not producing an enumerable set, then i am afrais that you are only rehearsing the ad hominem or authority argument. you are also assuming what is exactly in question. that would make it a circular argumentation.
furthermore, i am not assuming my algorith generates an enumerable set, i am trying to prove it. that is what you must prove wrong.

 

[D H]

The burden of proof is on you, the proponent, not on me. That said, Cantor's diagonalization argument disproves your conjecture. Now let's look at your algorithm.

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

Both of these steps require an infinite amount of time. You can't use either recursively.

 

[hachem]

quote D H: Both of these steps require an infinite amount of time. You can't use either recursively.

Cantor's diagonal argument is based on infinite sequences. you either grant me the same right or disprove cantor. you cannot have it both ways.

 

[Hurkyl]

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.

You don't have an argument. You simply (imprecisely) state an algorithm, ask us if it provides an enumeration of the reals, and then complain when we prove that it does not. I have seen no attempt by you to actually prove your algorithm enumerates the reals.

 

[D H]

You are doing something entirely different than Cantor's diagonalization theorem. You are using nested recursion, i.e., transfinite recursion. End of story.

 

[Hurkyl]

DH: I have assumed (possibly incorrectly) that when hachem says "output an arbitrary infinite binary sequence", he means to output a real number. And by Cantor's other diagonal argument, (or equivalently, by introducing multitasking) an ordinary Turing machine is capable of outputting a (coutably) infinite sequence of (countably) infinite binary sequences.

(of course, it's still not capable of outputting all countably infinite binary sequences)

(and, of course, there exist infinite binary sequences that cannot be printed by a Turing machine)

 

[Hurkyl]

Cantor's diagonal argument is based on infinite sequences. you either grant me the same right or disprove cantor. you cannot have it both ways.

(1) The diagonal argument doesn't purport to be an algorithm that can be executed on a Turing machine. You, on the other hand, have presented an algorithm, and therefore suffer from that constraint.

(2) On the other hand, it is very easy to convert the diagonal argument into a computable function, since it doesn't need access to the entire infinite sequence of infinite sequences; in order to compute the n-th digit of its output, it simply needs to read the (n, n)-th digit of the input data.

 

[hachem]

well, that's it then. end of story. does not fit in what you have learned, therefore it must be wrong.
what the algorithm does is legitimate by cantorian standards. you are defending the same position his opponents were during his lifetime. In other words, you are setting back the history of mathematics by just a little more than a century.
The use of pseudo-code is a legitimate means of proof. i am not a programmer but even i can say that it would be very easy to write it in a computer language.
The problem of the infinite statements would remain though, for that i would advise you to (re) read cantor and/or follow a course in the philosophy of mathematics. i thank you for this discussion which has served to convince me that my algorithm is at least worth studying carefully. not being a mathematician either i am of course highly interested in the opinon of experts.

 

[Hurkyl]

well, that's it then. end of story. does not fit in what you have learned, therefore it must be wrong.

The claim that (given the traditional definitions) the reals are enumerable is in the same category as claims such as "1 = 0".

Unless you are just presenting yourself extremely poorly, you are not doing something that "doesn't fit in" with what I have learned; you are doing something that actually does fit in with what I have learned, but for some inexplicable reason insist on assuming a contradiction.

The use of pseudo-code is a legitimate means of proof.

Pseudocode can be used in a proof. However, by itself, it is not a proof, because it is a presentation of an algorithm, not a deductive argument that derives conclusions from hypotheses.

not being a mathematician either i am of course highly interested in the opinon of experts.

Funny; I am both a mathematician and a computer scientist, and you seem to be entirely disinterested in both my opinion and my expertise.

 

[hachem]

quote Hurkyl:
(1) The diagonal argument doesn't purport to be an algorithm that can be executed on a Turing machine. You, on the other hand, have presented an algorithm, and therefore suffer from that constraint.

(2) On the other hand, it is very easy to convert the diagonal argument into a computable function, since it doesn't need access to the entire infinite sequence of infinite sequences; in order to compute the n-th digit of its output, it simply needs to read the (n, n)-th digit of the input data.
__________________
i think it is wrong to turn it into a realizability issue. cantor's argument is based on the infinite, his whole philosophy is based on (the different forms of ) the infinite. once again, it makes no sense to apply his arguments to finite sequences, his position was so controversial exactly because he assumed the actual infinite in his argumentation.

 

[hachem]

as far as 1=0; i am sorry to say that all you offered me was the claim of authority. i am not even claiming that reals are enumerable, only saying that the diagonal argument as used by cantor is not conclusive, and that my algorithm is here to sustain this last claim. if you still want to stick to the non-enumerability of reals, as i expect you will, i say you should look for other, better arguments.

 

[gel]

In other words, you are setting back the history of mathematics by just a little more than a century.
The use of pseudo-code is a legitimate means of proof.

None of the other posters are setting anything back. Your pseudocode does not prove anything.

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.

If you did this, you can still construct a new number that isn't in your list by the diagonal argument. I'm not sure what step 3 is supposed to prove - on the n'th step all it does is give you a number not equal to the previous n-1 numbers.

 

[Hurkyl]

i am not even claiming that reals are enumerable, only saying that the diagonal argument as used by cantor is not conclusive

Cantor's argument is a fully rigorous, deductive proof that there is no bijection between the naturals and a reals. If you do not find that "conclusive", then I must conclude that you have no interest in doing or learning mathematics, and so there is no point in allowing this discussion to continue here.