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 19 Jun 2010 22:48 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1qq8p.jrj.tim(a)soprano.little-possums.net... > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> After all, I am trying to make my proof exactly the same as >> Cantor's, but with the only difference being the word "computable" >> in front of the word "Real". > > If you intend your proof to be "exactly the same as Cantor's, but with > the only difference being the word "computable" in front of the word > "Real"", it must start with a conditional introduction. In other > words, something like: > > "Suppose that L is a list of computable Reals. That is, L is a > function from N to R and for all n in N, there exists a Turing > Machine T_n such that when provided with k as input, T_n halts and > outputs the k'th decimal digit of L(n)." > That's not how Cantor's proof starts. It starts with a list of Real numbers where the nth digit of the nth term is known for all n. > You can continue the proof from here if you like. > Or, I could use exactly the same logic as used by Cantor. Indeed, if I want to prove that Cantor's proof does not in of itself prove that Reals are uncountable, I have to follow his proof exactly. Which is what I have done. > > - Tim
From: Tim Little on 19 Jun 2010 22:56 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. 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. > (in more modern terminology) that there is no recursively enumerable > mapping Once again, "recursively enumerable" is an introduction purely of your own invention. 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. Cantor's proof applies to *every* mapping from N to R. - Tim
From: Peter Webb on 19 Jun 2010 23:01 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1qqov.jrj.tim(a)soprano.little-possums.net... > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> 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? > > No, because the antidiagonal is always real and not on the list. It > need not be computable. > Of course it is computable. Cantor provides an explicit algorithm for computing it. What part of "if the nth digit of the nth term is a 1, the nth digit of the antidiagonal is a 2, otherwise it is a 1" is not computable? Sounds like about three lines of Java. > >> 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? > > For the simple reason that Cantor's proof makes no assumption of any > finite algorithm and still concludes that the list does not contain > all reals. Hence it works even for uncomputable lists. > Well, Cantor's proof does require that the nth digit of the nth item on the list is known. Exactly as my proof does. > >> Cantor's proof requires a purported list of all Reals, such that the >> nth digit of the nth item can be determined. > > "Can be determined"? By what, a finite algorithm? Cantor's proof > requires on such thing. All it supposes it that the nth digit of the > nth item *exists*. > However you want to determine the rules for the list that Cantor uses to show the Reals cannot be listed, I will accpet exactly the same rules for my list of computable Reals. Many of the objections raised to my proof that the uncomputable Reals cannot be listed apply equally to Cantor's proof. nless you can tell me what the ifference is between my proof and Cantor's, its eem to me thatif you accpet Cantor's proof you have to accept mine. It is, after all, exactly the same. > >> And exactly where does the bit about a "finite algorithm" appear in >> Cantor's original proof? > > Nowhere at all, which is exactly the point you keep missing! *Your* > proof of computability of the antidiagonal requires a finite > algorithm. Cantor's proof uses no such assumption. > No. My proof does not require anything different to Cantor's at all. I make no mention of finite algorithms. I just do *exactly* the same construction, but applied to a purported list of all computable Reals instead of a purported list of all Reals. > >> Cantor asks for a list of Reals - defined in advance > > No, nothing need be "defined in advance". The proof is that if any > mathematical object happens to be a list of reals, then it fails to be > a complete list of reals. > Same as mine, in fact. Cantor: Lets assume that a list of all Reals exists. Peter: lets assume that a list of all computable Reals exist. Cantor: Lets form an anti-diagonal using this explicit construction based upon the nth digit of the nth Real on the list. It is obviously a Real, and it is obviously missing. Peter: Lets form an anti-diagonal using this explicit construction based upon the nth digit of the nth computable Real on the list. It is obviously a computable Real, and it is obviously missing. Cantor: Therefore the Reals cannot be listed. Peter: Therefore the computable Reals cannot be listed. Yet this does *not* prove the Reals are uncountable, because the computable Reals aren countable. > > - Tim
From: Peter Webb on 19 Jun 2010 23:10 "Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> wrote in message news:NNqdnTtg2LuExoDRnZ2dnUVZ8lKdnZ2d(a)brightview.co.uk... > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message > news:4c1c6be3$0$17177$afc38c87(a)news.optusnet.com.au... >> >> "Tim Little" <tim(a)little-possums.net> wrote in message >> news:slrni1om15.jrj.tim(a)soprano.little-possums.net... >> > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> >> So Cantor's proof when applied to computable Reals proves exactly >> >> what in your opinion? >> > >> > That there is a real not on the list. >> > >> > >> >> I might remind you that as the form of proof is identical to that >> >> used by Cantor for all Reals, whatever you believe that Cantor's >> >> proof applied to computable Reals proves, his proof applied to all >> >> Reals must prove the same thing. >> > >> > It does prove exactly the same thing: in both cases, all such lists >> > omit at least one real. >> > >> > >> >> Its the same proof, after all, except limitting the set to just >> >> computable Reals. >> > >> > No, there is a slight difference: the antidiagonal is a real number. >> > It does not necessarily produce a computable real number. >> > >> >> Of course it is computable. Cantor provides a simple construction for the >> number. > > No, you're misunderstanding the meaning of computable. > > Hopefully you will be OK with the following definition: > > A real number r is computable if there is a TM (Turing machine) > T which given n as input, will produce as output > the n'th digit of r. > > So let us suppose there is a list L (not a "computable list", just a > "list") > of computable numbers in [0,1], covering all computerable numbers. > > [You have your own strange definition of "list", but I am using the term > with it's standard mathematical meaning: L is just a function mapping N > (natural numbers) to CR (computable reals). Perhaps we should also insist > that lists are injections (no duplicates) - that's fine. YOU seem to want > to define "list" to only include "computable" functions from N to CR, but > that is NOT what everybody else (including Cantor) means by "list"!] > > L : N --> CR > > so we have the sequence (=list) of computable reals: > > ( L(0), > L(1), > L(2), > ....) > > Each computable real has it's digital representation, so this list can be > written: (using d(m,n) for n'th digit of L(m) > > L(0) digits : d(0,0), d(0,1), d(0,2), ... > L(1) digits : d(1,0), d(1,1), d(1,2), ... > L(2) digits : d(2,0), d(2,1), d(2,2), ... > ... > > Now, given m and n, is there necessarily a TM that can take m and n as > inputs, and ouput d(m,n)? > > Well, each L(m) individually is computable: there is a corresponding TM, > TM_m such that given n as input it will compute d(m,n). We could say: > > TM_m (n) = d(m,n) > > But all the TMs can be different and completely unrelated to each other. > > Can we say there will always be a *single* TM TM_ALL_m, which "subsumes" > all > the TM_n, i.e. if given m and n as input, will compute d(m,n)? I.e. > > for all m,n: TM_ALL_m (m,n) = d(m,n) ????? > > Unfortunately for your argument, the answer is NO. > > But that is exactly what you would need to argue that the anti-diagonal is > computable: You need a TM that could calculate d(m,m), but this needs the > TM TM_ALL_m, and we do not have that! > > I know what you want to say at this point! :) You want to say that I have > "explicitly given you" d(m,n), and I can only do this if d(m,n) is > computable. (Right?) And you want to tell me that Cantor's diagonal > proof > is the same? > > Well, this is a misreading of Cantor's proof! Look closely: > > Paraphrasing of Cantor's proof: > > Given a function L: N --> [0,1], there > exists r in [0,1], such that > for all n, r != L(n) [i.e. r is not in the list] > > Proof: > 1) Suppose L: N-->R > 2) Define LD: (NxN)-->{0,1,2,3,4,5,6,7,8,9} > such that LD(m,n) = n'th digit of L(m) > 3) Define RD: N-->R > such that RD(m) = [...antidiagonal digit m...] > 4) Then RD determines a real r in [0,1] > 5) Show for all n, r != L(n) from defn. of r above. > > Where in this proof does Cantor require LD(m,n) to be computable? (Answer > = > nowhere.) > > I think maybe you are thinking it must be computable, due to your > misleading > use of the phrase "explicitly given", but actually all Cantor does is > argue > that IF a (any) function L (not necessarily computable) EXISTS mapping N > to > [0,1], the mere existence of L implies the existence of a corresponding > real > r not in the list L. There is nothing requiring real computer programs to > actually compute anything here! It's just a mathematical proof of > existence > of something. > What you are writing above is *not* Cantor's diagonal proof as it appears on a million websites. The whole point of my post was to use Cantor's proof exactly, which alows me to demonstrate that Cantor's proof does *not* in of itself prove the uncounatbility of the Reals. Perhaps if you were to tell me where you think the error in my very simple proof is, then we would be making progress. More generally: you can't write down a list bof all computable Reals, such that the nth digit of the nth term is known. Ant more than you can write dow a list of all Reals, such that the nth digit of the nth term is known. That is what Cantor proves; that is what I prove about computable numbers. But thisw does not mean that the Reals are uncountable, as the computable numbers are countable. (And if you actually want to know why this is so, it is because the set of computable numbers is not recursively enumerable. And nor for that matter is the set of all Reals. This is what Cantor's proof actually shows, and it is *not* the same as being uncountable). > Hmmm, I can see this is where you will be objecting, but I can't see how > to > be more clear. > > OK - it's like the following (admittedly pretty dumb but correct) proof > that > I've just made up that there is no upper bound n_max in N which bounds all > functions from N to N: > > Dumb but correct Proof: > 1) Suppose there is such an n_max. > i.e. for all f,n: f(n) < n_max > 2) Then there is a *least* n with the same property > as n_max: call this n_max_min. > 3) There must be some F and m with > F(m) = n_max_min - 1 > [...details omitted, but otherwise n_max_min - 1 > would contradict the mininum property for n_max_min] > 4) But consider G(n) = F(n)+1 > 5) G is a function mapping N:-->N and > G(m) = F(m)+1 = n_max_min > 6) This contradicts (2) > 7) Hence assumption (1) is false > > There is no assumption in my proof that any of the functions be > "computable". Hopefully you would accept my proof, because it is similar > to > 1000 other proofs along the same lines. > > BUT... your Cantor objection is equivalent to saying that my proof only > works for "computable" functions. Why? Because I have to "explicitly > give > you" the function F in (3), so that step (4) makes sense! How can I "add > 1" > to a function that is not computable? Well, obviously I *can*. Step (4) > is > not to be thought of as a step for someone to write in a computer > program - > it's a mathematical definition of G(m) in terms of other things known to > exist at that point in the proof. Sure, if F were computable, then G > would > be, but nothing in the proof requires F to be! > > So too, it is with Cantor's proof. The "lists" involved are assumed to be > nothing more than maps from N to the target set (e.g. [0,1]) with no > assumption of computability. > > Hope this helps, > Mike. > > > >
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 |