"K_h" <KHolmes@SX729.com> wrote in message news:RcCdndEvyKIquYHRnZ2dnUVZ_hWdnZ2d@giganews.com... > > "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote in message > news:4c1b2def$0$14086$afc38c87@news.optusnet.com.au... >> >> "Tim Little" <tim@little-possums.net> wrote in message >> news:slrni1m68o.jrj.tim@soprano.little-possums.net... >>> On 2010-06-18, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >>>> Because Cantor's proof requires an explicit listing. This is a very >>>> central concept. >>> >>> Cantor's proof works on any list, explicit or not. >>> >> >> Really? >> >> How do you apply Cantor's proof to a list constructed as follows: >> >> "Define a list L such that the n'th entry on the list >> consists of all 1's if the n'th digit of Omega is 1, otherwise it is >> all 0's." >> >> (Your example). >> >>> The rest of your misconception snipped. >>> >>> >>> - Tim >> >> Perhaps if you could point out to me why you believe Cantor's proof that >> not all Reals can be listed (as it appears you do) but you don't believe >> my proof that not all computable Reals can be listed. They appear >> identical to me. > > All computable reals can be listed, but there is no finite algorithm for > doing so. An "infinite algorithm" could list every computable real. An > anti-diagonal, then, could be generated from this list but the algorithm > creating the anti-diagonal is implicitly relying on the "infinite > algorithm" underlying the list. In that sense the anti-diagonal is not > computable.
Agreed.
> The set of all reals are a different story. Even with an "infinite > algorithm" generating a list of reals, there is no way such a list could > contain every real. For a proof, do a google search on Cantor's theorem. >
No, Cantor's diagonal construction does not prove this, and nor is any of this machinery part of his proof.
Cantor's proof applied to computable Reals proves that the computable Reals cannot be listed. Cantor's proof applied to all Reals proves all Reals cannot be listed. That a set cannot be listed does not prove it is uncountable; computable Reals cannot be listed, but they are countable.
