"K_h" <KHolmes@SX729.com> wrote in message news:f9qdnUGYBZGX2YHRnZ2dnUVZ_hOdnZ2d@giganews.com... > > "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".
Typo, sorry.
My whole argument is that they cannot be listed in their entirety, or we could use a Cantor construction to produce a computable Real not on the list.
> 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. >
Umm ... they can be listed, but the list is not computable?
How are you going to give me a list of all computable Reals if you cannot compute what the first, second, third etc items in the list are?
In Cantor's diagonal proof, the list of Reals is provided in advance, such that the nth digit of the nth item is known.
All I am asking for in my proof that the computable reals cannot be listed is exactly the same thing as Canor's proof requires - a list of (computable) Reals provided in advance, such that the nth digit of the nth item is known.
Its easy to prove that no such list can exist. Yet this does *not* prove the computable Reals are uncountable.
>> 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.
OK, give me a list of all computable Reals. In exactly the same form as Cantor requests that a list of Reals be produced, such that I can identify the nth digit of the nth term. Exactly as per Cantor's proof that the Reals cannot be listed.
> The diagonal argument applied to such a list gives an anti-diagonal > number that is not computable.
Given the list, its trivially easy to explicitly compute the anti-diagonal. Cantor provides an explicit construction.
> 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. >
You cannot give me a list of all computable numbers.
Try, if you like.
The only requirement I place on the list is the requirement in Cantor's original proof, that the nth digit of the nth entry can be determined. I am copying Cantor's proof exactly.
I am happy to take that list and form its anti-diagonal and hence produce a computable Real not on the list.
This is *exactly* the same form of argument that Cantor used to show that the Reals cannot be listed. Yet the computable reals are countable.
