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