Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Peter Webb on 19 Jun 2010 23:12 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1qqsn.jrj.tim(a)soprano.little-possums.net... > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> Of course it is computable. Cantor provides a simple construction >> for the number. > > Only if the list itself is a recursively enumerable function. > Cantor's proof makes no such assumption. > Yes it does. It requires that the nth digit of the nth term can be calculated. This is not quite as strong as being re, but it is close. In any event, it is exactly the same restriction as I place on the purported list of all computable Reals. > > - Tim
From: Peter Webb on 19 Jun 2010 23:16 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1qrf2.jrj.tim(a)soprano.little-possums.net... > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> You haven't specified the list. I have to guess at some of the >> entries in the list, as I don't actually know and cannot determine >> which TMs halt. > > I have explicitly specified the list (which is actually a lot more > than Cantor's proof requires). It is not my problem whether you are > incapable of determining which TM's halt. It is a well-defined > mathematical function with all the properties assumed in Cantor's > proof. > No. Cantor's proof requires that the nth digit of the nth term can be determined. > Likewise the following is a valid list of binary digits: f(n) = 1 if > there are infinitely many prime pairs of the form (p, p+n), f(n) = 0 > otherwise. It doesn't matter whether or not you personally know the > value of f(2), or even whether there exists an algorithm to find out: > it is still a well-defined mathematical object. > > > Are you now starting to see the difference between the term "list" (as > used in Cantor's proof) and "recursively enumerable list" (as you are > using in yours)? > I am not using the term "recursively enumerable list" in my proof. Re-read it. I am asking for a list in *exactly* the same way as Cantor asks for a list, excepting that it contains only computable Reals and not just any Real. > - Tim
From: Peter Webb on 19 Jun 2010 23:17 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1qrip.jrj.tim(a)soprano.little-possums.net... > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> Take the list, determine the nth digit of the nth item, blah >> blah. Remember, just as in Cantor's proof, you have to provide the >> list first. > > You don't get to "take the list" to compute the diagonal, as the list > is an infinite object in contradiction to the requirement of "finite > algorithm" in the definition of "computable real". > The anti-diagonal can be computed to any required degree of accuracy. There is an explicit construction for every digit in its decimal expansion. Try and tell me how it is uncomputable. > > - Tim
From: Peter Webb on 19 Jun 2010 23:24 "Daryl McCullough(" <stevendaryl3016(a)yahoo.com> wrote in message news:hvic840ge3(a)drn.newsguy.com... > Peter Webb says... > >>"Tim Little" <tim(a)little-possums.net> wrote > >>Hmmm. But you cannot provide me with a list of all Computable numbers, can >>you? Which is what Cantor's diagonal proof requires. > > Cantor's proof assumes the *existence* of such a list. It doesn't > assume that you know how to compute it. > If that is what you believe, then I am happy for the same rules to be applied to the purported list of all computable Reals. >>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. > > No, it doesn't. If f is any mapping from N to computable numbers, > then antidiag(f) is a new real that is not in the image of f. > It doesn't matter whether f is recursively enumerable or not. > >>That a set cannot be listed is not the same as it is uncountable, > > I would say it this way: That a set is not recursively enumerable > does not imply that it is not enumerable. > Bingo. > The set of computable reals is enumerable, but not recursively > enumerable. The set of *all* reals is not enumerable. > Correct. >>You cannot give me a list of all Computable numbers, >>because I can use a diagonal construction to form a >>computable Real not on the list. > > If the list is computable, that's correct. If the list > is not computable, then that's not correct. > Cantor proved that you cannot compute a list of Real numbers. As you point out, this is not the same as being uncountable. >>Cantor's proof applied to Reals does *not* prove they are >>uncountable; > > It certainly does. If you assume that the set of reals is > countable, then that means that there is a bijection f from > the naturals to the reals. Cantor's proof shows that there > is no such bijection. > No. Exactly the same construction can be applied to a purported list of all computable Reals, but these are countable. >>> If that doesn't answer your question, you'll have to clarify what you >>> mean by it. >>> >> >>What I mean is that Cantor proved you cannot provide a list of all Reals. > > He proved that there is no bijection between the naturals and the reals. > By definition, that means that the reals are uncountable. > No, he proved that any purported list of all Reals must miss at least one Real. Which is exactly the same as what I prove for computable Reals. Yet the computable Reals are countable. Clearly his proof (in its orginal and common form) does not prove the Reals are uncountable. > -- > Daryl McCullough > Ithaca, NY >
From: Tim Little on 19 Jun 2010 23:27
On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > Cantor's proof requires the purported list of all Reals to be > provided. That is your fantasy, not part of Cantor's proof. Cantor proved a closed-form proposition, which means that there are no free variables that can be "required to be provided". > No idea what you are talking about. Then perhaps you should read a reasonable reference on predicate logic and mathematical proof. > Perhaps if you could explain how my proof differs from Cantor's > proof, that would be a start. I have done already, but perhaps I can explain it in different terms for you. > You seem to accept Cantor's proof, but not mine. Yet they are almost > identical, the only difference being I have inserted the word > "computable" in front of "reals". > > I can't see how you can accept one and not the other. Cantor's proof shows that for any mapping L:N->R, antidiag(L) is real and not in range(L). Cantor's proof does include a proof that antidiag(L) is real. It does not show that antidiag(L) is a computable real. You cannot just drop "computable" in there and suppose that the logic works, just as you cannot drop "rational" in there and suppose that the logic works. If you want to prove that for any mapping L:N->R, antidiag(L) is computable, you need to include a proof that antidiag(L) satisfies the mathematical definition for a computable real. > It is extremely easy to compute. > > Take the nth decimal place of the nth term. The nth decimal place of the nth term of what? The list L? That's fine if you permit infinite lists of reals as input to the algorithm, but the definition of "computable real" permits no such thing. > I am using Cantor's proof exactly, except for inserting the word > "computable" before every use of the word "real". That is the whole > point. That doesn't work because Cantor's work does not include any proof that antidiag(L) is computable: only that it is real. Hence there is a gaping hole in the validity of your modified text. You will not be able to fill that hole, because there are well-defined functions L for which antidiag(L) is *not* a computable real. There are even explicitly-definable such lists, and furthermore there are such lists where there are only two values in the range: for example, let L(n) = 0 if the n'th digit of Omega is 0, L(n) = 1/9 otherwise. Both members of range(L) are very obviously computable - they're even rational! But the decimal antidiagonal is not computable. - Tim |