Is the Cantor diagonal argument conclusive?

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