Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Peter Webb on 19 Jun 2010 02:19 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1ol51.jrj.tim(a)soprano.little-possums.net... > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> Of course there exists a mapping from N to computable numbers. But >> Cantor's proof requires more than that; it requires the mapping to >> be recursively enumerable such that we can also explicitly list >> them. > > It does not. If you believe otherwise, feel free to show where in > Cantor's proof any requirement for recursive enumerability is stated > or implicitly used. > Its not. > The simple fact is that no such requirement exists. Cantor's diagonal > proof applies to *every* mapping from N to R, recursively enumerable > or not, showing that no such mapping is surjective. No. It requires that any listing be provided in advance, so that the anti-diagonal can be formed. > > Your introduction of recursive enumerability into Cantor's proof is > entirely your own fabrication. Well, I did say it was my interpretation of what was going on. The simple fact is that if insert the word "computable" in front of every reference to "Real" in Cantor's proof that there is no list of all Reals, you produce a proof that thye computable Reals cannot be listed either. yet they are known to be countable. Cantor's proved that the Reals cannot be listed. It is your incorrect assumption that this means they are also uncountable. Some countable sets cannot be listed either, such as the set of Computable Reals. This is because the set of computable Reals is not recursively enumerable, and hence cannot be listed by a terminating process. > > > - Tim
From: Peter Webb on 19 Jun 2010 02:37 "K_h" <KHolmes(a)SX729.com> wrote in message news:f9qdnUGYBZGX2YHRnZ2dnUVZ_hOdnZ2d(a)giganews.com... > > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message > news:4c1c3663$0$24370$afc38c87(a)news.optusnet.com.au... >> >> "K_h" <KHolmes(a)SX729.com> wrote in message >> news:RcCdndEvyKIquYHRnZ2dnUVZ_hWdnZ2d(a)giganews.com... >>> >>> "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message >>> news:4c1b2def$0$14086$afc38c87(a)news.optusnet.com.au... >>>> >>>> "Tim Little" <tim(a)little-possums.net> wrote in message >>>> news:slrni1m68o.jrj.tim(a)soprano.little-possums.net... >>>>> On 2010-06-18, Peter Webb <webbfamily(a)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. > http://en.wikipedia.org/wiki/Uncountable_set > > _ > >
From: Virgil on 19 Jun 2010 02:39 In article <4c1c6011$0$17176$afc38c87(a)news.optusnet.com.au>, "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Tim Little" <tim(a)little-possums.net> wrote in message > news:slrni1okg1.jrj.tim(a)soprano.little-possums.net... > > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > >> "Tim Little" <tim(a)little-possums.net> wrote in message > >>> Your "simple fact" is simply wrong. Look up the definition of > >>> "computable real" and get back to us. > >> > >> Why? > > > > Because you clearly don't know how a computable real is defined. > > > > > >> If you believe there is an error in what I have said, identify it. > > > > I have, many times now. > > > > > >> Or give me at least a hint. As a start, my argument rests on two > >> observations: > >> > >> 1. Cantor's diagonal construction, when applied to a purported list > >> of all computable Reals, will produce a computable Real not on the > >> list. > > > > The latter part is incorrect. It produces a real, but not a > > computable real. If you believe otherwise, provide a proof that the > > antidiagonal real is computable. > > > > Well, there are lots of definitions of a computable Real, I will use > Wikipedia's most intuitive definition: "computable reals, are the real > numbers that can be computed to within any desired precision by a finite, > terminating algorithm." > > 1. Given a list of computable Reals, we can identify the nth computable Real > on the list by simply counting down to the nth entry. > > 2. Given the nth computable Real on the list, we can count off and identify > the nth digit of this Real. > > 3. With the nth digit of the Real, we can use Cantor's construction to > identify the nth digit of the anti-diagonal. > > 4. As we can specify every digit in the anti-diagonal explicitly and to any > desired degre of accuracy, it is therefore computable. But that requires that the list be given in advance, so that "anti-diagonal" is not really a single number so much as a function from lists to numbers with value depending on the particular list being chosen. So I am not quite confident that that situation qualifies as a computable number, which should not, in my mind, be dependent on a particular list of numbers being given. > > 5. But the anti-diagonal number does not appear on the list. > > 6. Therefore, the list could not have included all computable Reals. > > Exactly the same as Cantor's proof that the Reals cannot be listed. The only > difference is that I have to prove that the anti-diagonal is also > computable, but because Cantor's proof explicitly constructs the > anti-diagonal it is clearly computable (as long as every item in the list is > computable, which is the starting assumption which we prove to be incorrect, > just like in Cantor's original proof). Actually not. The starting assumption had better be that list contains EVERY computable number if you are trying to prove something INcorrect. It is perfectly possible to have lists of computable numbers which are not complete in which case the anti-diagonal construction proves nothing. > > > > HTH > > Peter Webb
From: Virgil on 19 Jun 2010 02:42 In article <4c1c61ae$0$2162$afc38c87(a)news.optusnet.com.au>, "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Tim Little" <tim(a)little-possums.net> wrote in message > news:slrni1ol51.jrj.tim(a)soprano.little-possums.net... > > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > >> Of course there exists a mapping from N to computable numbers. But > >> Cantor's proof requires more than that; it requires the mapping to > >> be recursively enumerable such that we can also explicitly list > >> them. > > > > It does not. If you believe otherwise, feel free to show where in > > Cantor's proof any requirement for recursive enumerability is stated > > or implicitly used. > > > > Its not. > > > The simple fact is that no such requirement exists. Cantor's diagonal > > proof applies to *every* mapping from N to R, recursively enumerable > > or not, showing that no such mapping is surjective. > > No. It requires that any listing be provided in advance, so that the > anti-diagonal can be formed. > > > > > > Your introduction of recursive enumerability into Cantor's proof is > > entirely your own fabrication. > > Well, I did say it was my interpretation of what was going on. > > The simple fact is that if insert the word "computable" in front of every > reference to "Real" in Cantor's proof that there is no list of all Reals, > you produce a proof that thye computable Reals cannot be listed either. yet > they are known to be countable. > > Cantor's proved that the Reals cannot be listed. It is your incorrect > assumption that this means they are also uncountable. Some countable sets > cannot be listed either, such as the set of Computable Reals. This is > because the set of computable Reals is not recursively enumerable, and hence > cannot be listed by a terminating process. Ah! But that "listed by a terminating process" is not the same as merely "listed"
From: Peter Webb on 19 Jun 2010 02:59
"K_h" <KHolmes(a)SX729.com> wrote in message news:0radndv17q0_14HRnZ2dnUVZ_uydnZ2d(a)giganews.com... > > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message > news:4c1c3a11$0$18229$afc38c87(a)news.optusnet.com.au... >> >> "K_h" <KHolmes(a)SX729.com> wrote in message >> news:ALWdnQzHH6Fug4HRnZ2dnUVZ_gKdnZ2d(a)giganews.com... >>> >>> "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message >>> news:4c1b24ce$0$17177$afc38c87(a)news.optusnet.com.au... >>>> >>>> "Tim Little" <tim(a)little-possums.net> wrote in message >>>> news:slrni1m2q9.jrj.tim(a)soprano.little-possums.net... >>>>> On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> >>>>> wrote: >>>>>> "Tim Little" <tim(a)little-possums.net> wrote in message >>>>>>> Cantor's construction applied directly to lists of computable >>>>>>> numbers >>>>>>> shows almost nothing. Given any list of computable reals, you can >>>>>>> produce an antidiagonal real not on the list. Unfortunately the >>>>>>> construction says nothing about whether the antidiagonal is >>>>>>> computable >>>>>>> or not. >>>>>> >>>>>> Of course its computable. It is a trivial programming exercise to >>>>>> form a >>>>>> computable number not on the list, by simply doing digit >>>>>> substitutions. >>>>> >>>>> Only if the list itself is a computable function. Cantor's proof does >>>>> not depend on any such assumption. >>>>> >>>> >>>> If you give me a purported list of all computable numbers, I can >>>> explicitly >>> >>> QUESTION 1: >>> But ask yourself: is the list of all computable real numbers itself >>> computable? Each real in such a list is computable but can you find a >>> computable function that says which computable real is mapped to 0, >>> which computable real is mapped to 1, which computable real is mapped to >>> 2, and so on? >>> >> >> No. >> >>>> construct a Real not on the list. Of course this number is computable; >>>> there is a simple algorithm to compute it. >>> >>> But ask yourself: since the algorithm you use to compute it calls on the >>> "algorithm" I asked you about in QUESTION 1, is your algorithm depending >>> on another "algorithm" that is non-computable? >>> >> >> The algorithm does not exist. There can be no list of all computable >> Reals. > > No, there is no finite algorithm that can generate the list but that does > not mean that such lists don't exist. There are lists that contain all > computable reals. 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? If this were the case, then the Reals would be countable. 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? > >>>> No. And in fact Cantor's diagonal proof does not prove the Reals are >>>> uncountable, just that they cannot be listed. Which is all he claimed. >>> >>> No, because Cantor's diagonal argument applies to lists that are not >>> computable as well as to lists that are computable. >> >> So Cantor's proof when applied to computable Reals proves exactly what in >> your opinion? > > If I understand your question, all it shows is that the anti-diagonal > number is not computable. > Its easy to compute. Cantor's proof requires a purported list of all Reals, such that the nth digit of the nth item can be determined. My proof requires exactly the same thing. The computation to derive the nth digit of the anti-diagonal is simple and explicityly constructs the anti-diagonal number. Its hard to argue this number cannot be computed when Cantor provides an explicit means of computing it. >> So the computable Reals cannot be listed. >> Yet they are countable. >> So a proof that a set cannot be listed does not prove it is uncountable. > > The computable reals can be listed and so they are countable. > Sweet. Give me such a list, and I will *compute* a number not on the list. >>>> You give me that list. >>> >>> Yes, every real in the list is computable. But ask yourself: is the >>> function that maps each natural to each of these reals itself >>> computable? >> >> No. >> They cannot be listed. > > Yes they can but not by a finite algorithm. > And exactly where does the bit about a "finite algorithm" appear in Cantor's original proof? Cantor asks for a list of Reals - defined in advance - and then produces Real not on the list. The list he requires specifies each Real sufficiently to identify the nth decimal place of the nth item. I ask for a list of computable Reals - defined in advance - and produce a computable Real not on the list. My requirements on the structure of the list are *identical* to those used by Cantor - the list must identify each item sufficiently to identify the nth decimal place of the nth item. How is my proof different to Cantors? And if my proof does not demonstrate that the computable numbers are uncountable, why do you think that the same proof applied to all Reals proves that they are uncountable? |