Why can no one in sci.math understand my simple point?
in [Math]
|
Prev: power of a matrix limit A^n
Next: best way of testing Dirac's new radioactivities additive creation Chapt 14 #163; ATOM TOTALITY
From: Peter Webb on 20 Jun 2010 10:20 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1r04q.jrj.tim(a)soprano.little-possums.net... > On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> "Tim Little" <tim(a)little-possums.net> wrote in message >>> That is only a "finite, terminating algorithm" if the list is finite. >>> Since the only input to the algorithm is the desired precision, your >>> recipe only works if you can embed the list into the algorithm. >> >> No. You could level the same argument against Cantor's original proof. > > No you couldn't, as it makes no assumption of any finite algorithm. > Only *your* alteration of Cantor's proof assumes any sort of finite > algorithm, as it is required for the definition of "computable real". > I don't say anything about finite algorithms. I just ask for a list of computable Reals, in the same form a Cantor asks for a list of Reals. > >> For a number to be computable, it must be able to be calculated to >> any required degree of accuracy (according to the definition we have >> just both agreed on). This is obviously true of the anti-diagonal. > > Only if the list is computable, which Cantor's proof does not require. > Exactly how are my requirements for the list different from Cantor's, excepting that my list contains computable Reals and his requires any Real? > >> Cantor provides an explicit algorithm for constructing (computing) >> the anti-diagonal. > > No, the proof only provides an algorithm fragment. A full algorithm > for a computable real must take the precision as input, and nothing > else. The constructive portion of Cantor's proof takes an infinite > list of real numbers as "input", and so is not a valid algorithm for a > computable real. > No, if you want to use this definition of a computable Real (slightly different to the one we have been using, but equivalent), to determine the anti-diagonal to n places only requires the first n items on the list be examined, and hence is finite. > >>> If not, how does this differ from "suppose L is a list of real >>> numbers. Is antidiag(L) computable?" >> >> Because there is an algorithmic procedure for calculating the >> anti-diagonal to any required degree of accuracy. > > If you are given L, you say you can compute antidiag(L) regardless of > what L is. Yep. Easy. The nth digit of L is "1" if the nthe digit of the nth term is "2", otherwise it is "1". As I can easily specify every digit in its decimal expansion, it is of course computable. > If you are given x, can you not compute x+1 regardless of > what x is? By your argument, does this not mean that x+1 is always a > computable real? > As long as x is computable. And the input list by definition only contains computable Reals. > > - Tim You remind me of one of those anti-Cantor cranks who keep trying to find a flaw in Cantor's proof. My proof and his are virtually identical. Cantor proved the set of Reals is not recursively enumerable, and my proof shows the set of computable Reals is not recursively enumerable. This is not quite the same thing as being uncountable.
From: Newberry on 20 Jun 2010 10:33 On Jun 19, 6:06 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > Newberry <newberr...(a)gmail.com> writes: > >> Because every infinite sequence of digits represents a real number? And > >> the antidiagonal is one such sequence? > > > If it does not exist then it does not represent anything let alone a > > number. > > > Now it is clear that it does not exist. Since all the reals are on the > > list and the anti-diagonal would differ from any of them. This > > violates the assumption. Hence the anti-diagonal does not exist. > > Wow. Are you saying that the *sequence of digits* specified by the > anti-diagonal does not exist? That's right. There is no formula or algorithm to construct the list. It means that you would have to flip each and every digit one by one. And that is impossible. > Anyway, in a sense, you're right. If we assume that every real is > represented by a sequence on the list, then we can prove that every > sequence occurs on the list (ignoring the issue of multiple > representations). And yet, we can also show that a particular sequence > is not on the list. Which sequence is that? > This is a contradiction and hence *our assumption* > that every real is represented by a sequence on the list must be false. > > You've never seen proof by contradiction in your life? How remarkable. > > -- > Jesse F. Hughes > > "Of course, I don't need any more education." > -- Quincy P. Hughes (age 7)
From: Peter Webb on 20 Jun 2010 10:52 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1r0ra.jrj.tim(a)soprano.little-possums.net... > On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> Explain to me how my requirements for the input list of all >> computable Reals is different to Cantor's requirements for the input >> list of all Reals, other than the requirement that every item on the >> list is computable? > > It is not. Your error comes later. > > Cantor's proof includes a construction taking a list L and defining an > antidiagonal real antidiag(L) from it. Your error is supposing that > this construction is a finite algorithm fitting the definition of > "computable real". It is not. By stretching the definition of > "algorithm" somewhat, it can be supposed to be an algorithm accepting > finite input n and infinite input L, and producing the n'th > antidiagonal digit. This is a stretch since algorithms are normally > not supposed to have infinite inputs. The calculation of the nth digit only requires the first n digits to n decimal places, and hence it is clearly a finite algorithm. Its simply ludicrous to suggest that the antidiagonal is not computable given that a very simple algorithm will explicitly churn it out. > > However, there is no way that you can then prove the existence of a > finite algorithm accepting only the *finite* input n and producing the > n'th antidiagonal digit. > Of course I can prove the existence of a finite algorithm. I can produce it. To produce the nth decimal of the anti-diagonal, look at the first n items on the purported list of all computable Reals. Then substitute "1" for "2" blah blah. How is that not a finite algorithm? I can produce the nth decimal place of the anti-diagonal purely by counting down to the nth Real on the list and looking at the nth digit. I can code it in Java in 3 lines. Exactly as per Cantor's proof. > >> (in more modern terminology) that there is no recursively enumerable >> mapping > > Once again, "recursively enumerable" is an introduction purely of your > own invention. As I said when I introduced it. It does not appear in Cantor's proof or mine. It is an explanation of why this somewhat paradoxical result applies, that Cantor's form of proof applied to computable Reals also produces the conclusion that any such list cannot be complete. Not that it is much of an explanation; not being recursively enumerable means pretty much the same thing as having no explicit mapping from N. As somebody else pointed out, computable Reals are enumerable but not recursively enumerable. Cantor's form of proof applied to computable Reals shows only that they are not recursively enumerable, not the stronger condition that they are uncountable. Similarly, Cantor's proof really only shows that the Reals are not recursively enumerable, not that they are also denumarable (uncountable). > It is not present in Cantor's proof, it is not present > in a modern recasting of Cantor's proof, it has no relevance at all to > Cantor's proof. Well, I think I am making a pretty good hand of my case. But yes, I know what I am saying is not accepted. I am genuinely confused by this - the fact that my opinions are unique, and I would expect therefore to be almost certainly wrong (with probability 1). On the other hand my argument seems pretty solid to me. > Cantor's proof applies to *every* mapping from N to R. > Ummm ... mine applies to every mapping from N to computable Reals. > > - Tim Really, if you have some list of computable Reals to give me, I would be happy to provide the anti-diagonal. And lets remember what a "computable Real" is, it is a Real which can be specified to any arbitrary degree of accuracy. As a practical matter, you don't have to list every one in full; I only require the first n digits.
From: WM on 20 Jun 2010 11:10 On 20 Jun., 16:33, Newberry <newberr...(a)gmail.com> wrote: > On Jun 19, 6:06 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > > > Newberry <newberr...(a)gmail.com> writes: > > >> Because every infinite sequence of digits represents a real number? And > > >> the antidiagonal is one such sequence? > > > > If it does not exist then it does not represent anything let alone a > > > number. > > > > Now it is clear that it does not exist. Since all the reals are on the > > > list and the anti-diagonal would differ from any of them. This > > > violates the assumption. Hence the anti-diagonal does not exist. > > > Wow. Are you saying that the *sequence of digits* specified by the > > anti-diagonal does not exist? > > That's right. There is no formula or algorithm to construct the list. > It means that you would have to flip each and every digit one by one. > And that is impossible. Well, there are some lists defined by finite definitions like 0.1 0.11 0.111 .... But the number of these lists and the number of their diagonals is countable. > > > Anyway, in a sense, you're right. If we assume that every real is > > represented by a sequence on the list, then we can prove that every > > sequence occurs on the list (ignoring the issue of multiple > > representations). And yet, we can also show that a particular sequence > > is not on the list. > > Which sequence is that? O, don't be unfair. Matheolgicians "prove" their claims. They are not used to give examples. Remember Zermelo who "proved" that every set can be well ordered. Although every sober mind today knows that hisproof is wrong, set theory is built upon this lie. Otherwise the hierarchy of infinities cannot exist. Set-cranks suffer from selective damage of perception. There is no use to discuss with them. (Nevertheless we should go on as if they could understand - mainly to save those who have not yet become "mentally challenged zealots of abstract mathematics" (V.I. Arnol'd)) Regards, WM
From: Peter Webb on 20 Jun 2010 11:43
>> 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. > Yes. > 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. > Well, it does work. > 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. > OK. I an specify it to n places for all n using the following simple algorithm. Change the nth digit of the nth term from a 1 to a 2 and else to a 1. Thus if your list contained say: ..1111111 ..2222222 ..1111222 The antidiagonal is 0.212... Notice that I computed this quite easily? Every item on the list is computable. So every item is known to at least n decimal places of accuracy, and Cantor gives us a very easy way to compute the first n terms on the anti-diagonal given the first n items on the list to n decimal places. > >> 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. > No, to calculate the first n terms of the anti-diagonal you require only te first n items on the list to n places of accuracy. Cantor's anti-diagonal is computable because the first n items on the list are computable, and he provides an explicit contruction for his number which is very easy to compute indeed. > >> 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. Well, no. Cantor actually provides an explicit construction for the anti-diagonal. He does have to prove its a computable number; he actually computes it. If every item on the list is computable, every item can be specified to any required degree of accuracy (in decimal, in this case), and we can "compute" the nth decimal place of each. Clearly we can compute the Cantor substitution to explicitly construct another number, the anti-diagonal. Simply substituting a "1" fo a "2" etc is still computable. > > 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. > I am having a bit of trouble computing even the first term of that. I am also wondering how Cantor would have felt about that. I can't see that he can change a "1" to a "2" etc if he doesn't know what the value is. But you have made an excellent point in your example. When Cantor is confronted with some digit as poorly defined your Chaitan's number example, it can simply say "I don't care what the number actually is". There is not the same luxury with computable Reals; this act of arbitrary/random choice can make them uncomputable, as your example shows. > Both members of range(L) are very obviously computable - they're even > rational! But the decimal antidiagonal is not computable. > Well, yes, but I am failing to see how you are providing a list of computable Reals when you won't actually tell me even what is the first computable Real on the list. Cantor's algorithm requires slightly more than a set of Reals, it also demands they are ordered for us - there is a mapping from N to that set. He asks for and uses in his proof a "list" of numbers. What number does 1 map to in your example? > > - Tim That's still a nice example, that every item in a list can be computable but the anti-diagonal is not. But I still don't think you are really playing fair with this one. You have to tell me what the first, second, third etc items are on the list. I mean, that's what a list is after all, a mapping from N, and that is what Cantor's proof requires as input. |