Is the Cantor diagonal argument conclusive?

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