"Tim Little" <tim@little-possums.net> wrote in message news:slrni1qqov.jrj.tim@soprano.little-possums.net... > On 2010-06-19, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >> So using this logic and applying it to Cantor's original proof, >> there may also be lists of all Reals, but there is no finite >> algorithm which can generate the list? > > No, because the antidiagonal is always real and not on the list. It > need not be computable. >
Of course it is computable.
Cantor provides an explicit algorithm for computing it.
What part of "if the nth digit of the nth term is a 1, the nth digit of the antidiagonal is a 2, otherwise it is a 1" is not computable? Sounds like about three lines of Java.
> >> How do you know that Cantor's proof that that there can be no list >> of all Reals is simply because there is no finite algorithm to >> produce the list, and not because they are uncountable? > > For the simple reason that Cantor's proof makes no assumption of any > finite algorithm and still concludes that the list does not contain > all reals. Hence it works even for uncomputable lists. >
Well, Cantor's proof does require that the nth digit of the nth item on the list is known. Exactly as my proof does.
> >> Cantor's proof requires a purported list of all Reals, such that the >> nth digit of the nth item can be determined. > > "Can be determined"? By what, a finite algorithm? Cantor's proof > requires on such thing. All it supposes it that the nth digit of the > nth item *exists*. >
However you want to determine the rules for the list that Cantor uses to show the Reals cannot be listed, I will accpet exactly the same rules for my list of computable Reals.
Many of the objections raised to my proof that the uncomputable Reals cannot be listed apply equally to Cantor's proof. nless you can tell me what the ifference is between my proof and Cantor's, its eem to me thatif you accpet Cantor's proof you have to accept mine. It is, after all, exactly the same.
> >> And exactly where does the bit about a "finite algorithm" appear in >> Cantor's original proof? > > Nowhere at all, which is exactly the point you keep missing! *Your* > proof of computability of the antidiagonal requires a finite > algorithm. Cantor's proof uses no such assumption. >
No. My proof does not require anything different to Cantor's at all. I make no mention of finite algorithms. I just do *exactly* the same construction, but applied to a purported list of all computable Reals instead of a purported list of all Reals.
> >> Cantor asks for a list of Reals - defined in advance > > No, nothing need be "defined in advance". The proof is that if any > mathematical object happens to be a list of reals, then it fails to be > a complete list of reals. >
Same as mine, in fact.
Cantor: Lets assume that a list of all Reals exists.
Peter: lets assume that a list of all computable Reals exist.
Cantor: Lets form an anti-diagonal using this explicit construction based upon the nth digit of the nth Real on the list. It is obviously a Real, and it is obviously missing.
Peter: Lets form an anti-diagonal using this explicit construction based upon the nth digit of the nth computable Real on the list. It is obviously a computable Real, and it is obviously missing.
Cantor: Therefore the Reals cannot be listed.
Peter: Therefore the computable Reals cannot be listed.
Yet this does *not* prove the Reals are uncountable, because the computable Reals aren countable.
