"Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote in message news:4c1c3663$0$24370$afc38c87@news.optusnet.com.au... > > "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.
You have contradicted yourself. I wrote "All computable reals can be listed,..." and your reply was "Agreed". Now you write "...the computable Reals cannot be listed". Let's be clear. The computable reals can be listed. Cantor's ideas, applied to such a list, shows that the anti-diagonal of such a list is not computable. That's all.
> 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.
All computable reals CAN be listed. The diagonal argument applied to such a list gives an anti-diagonal number that is not computable. If that anti-diagonal number was computable then the set of all computable reals would be uncountable. But that is not the case. The diagonal argument applied to a list of reals gives another real that is nowhere in the list. So the reals cannot be listed. By definition, a set that cannot be listed is uncountable. The computable reals can be listed so they are countably infinite. The reals cannot be listed so they are uncountably infinite.
