Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Mike Terry on 20 Jun 2010 13:33 "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message news:4c1e2b53$0$316$afc38c87(a)news.optusnet.com.au... > > "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. Not so - the "very simple algorithm" you are suggesting requires "the input list" in its raw (infinite) form as input. As such, this is not an algorithm that can be implemented on a Turing machine. I.e. the algorithm is not the sort of algorithm that counts as "computable". Maybe you will dispute this, but it's been explained to you several times (including one of my posts), and you can always go away and look up the definition of computable function / Turing Machine etc., but it seems you've not done this. > > > > > 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. There! Was I right, or was I right? :-) There is an infinite amount of data on this "purported list", and you are not allowed to base a computable function on an infinite amount of input data. To do so shows you simply do not understand what computable means. Now IF you could codify all this data somehow into a finite program, so you had a computable function D(m,n) which produced the n'th digit of the m'th number in the list, you would be OK. But you DON'T have such a computable function D. What you DO have, is for each m, a computable function D_m (n) which produces the n'th digit of the m'th number in the list. But how can you use these individual D_m in the definition of the antidiagonal? (You can't...) Do you not see this distinction? Knowing the existence of all the individual D_m is equivalent to knowing that the list (sequence of numbers) consists of computable reals. Knowing the existence of D (which is a single computable function) is equivalent to having a *computable* list of computable reals. Cantor's proofs do not require computable lists, they work with just any old lists... > Then substitute "1" for "2" > blah blah. How is that not a finite algorithm? As explained it is not a finite algorithm because it uses as input an infinite source of data. By your reckoning every single real number is computable, because we can have a TM that just accepts as input an infinite tape with the entire digit sequence encoded on it, and outputs that digit sequence. Surely you must be aware that this is NOT what computability means? Regards, Mike.
From: Mike Terry on 20 Jun 2010 13:43 "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message news:4c1e3743$0$1028$afc38c87(a)news.optusnet.com.au... > >> 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. So you require as input: - the 1st digit to 1 place of accuracy - the 2nd digit to 2 places of accuracy - the 3rd digit to 3 places of accuracy - ... The ... above is the give away! For your algorithm to work its going to require an INFINITE amount of input data. (Remember, you are trying to find a SINGLE stand-alone FINITE algorithm that produces ALL the required digits of the antidiagonal.) So Tim was quite right, and you haven't answered his point correctly yet... Regards, Mike.
From: Mike Terry on 20 Jun 2010 14:10 "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message news:4c1d86f0$0$18229$afc38c87(a)news.optusnet.com.au... > > "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. Well, I claim that it is at least OBVIOUSLY EQUIVALENT to what Cantor is saying. It's true I didn't go to a web site and cut and paste any "official" text from his original document, but in essence my understanding is: 1. Cantor shows that any map from N to R cannot be "onto" R. 2. That my proof above sketches this out: - Cantor equates real numbers with their digit sequences (This is why I go from L to LD) - Cantor shows the existence of a new digit sequence, via the antidiagonal argument (That is what I do in step (3). RD is my new digit sequence.) - Cantor proves that RD is a new digit sequence - and that consequenctly the corresponding real number is not in the original map L. So I think my proof follows Cantor's pretty closely, although it is my own notation. Given the amount of effort I put into trying to help you, I'm disappointed you can't get over some minor notationaly differences to follow what I'm saying. You've also given no indication of in what way you think my proof differs from Cantors! (Well, that would be OK if my proof was "nothing like" Cantor's but that's clearly not the case as I've just explained, so I'm left mystified by your claim...) > > 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. Sure I'll do this. To avoid a further "that's not Cantor's proof" claim from you, please quote exactly what proof of Cantor's you want me to comment on. Regards, Mike.
From: Mike Terry on 20 Jun 2010 14:18 "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message news:4c1d8758$0$14086$afc38c87(a)news.optusnet.com.au... > > "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. Not so - the proof simply needs the n'th digit of the n'th term to EXIST. It is then possible to prove the EXISTENCE of the missing real number (via the antidiagonal argument). His proof should not be read as instructions for a "C" program or some such! :-) It's an existence proof, not really an "algorithm" at all in the sense I would use the word... > 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. No, you require the list itself to be computable, so that given m,n as input you can compute "the n'th digit of the m'th number". That's MUCH more than Cantor requires. > > > > > - Tim >
From: Virgil on 20 Jun 2010 15:55
In article <7d59f93c-4bc8-43e2-9b40-485733a01305(a)z8g2000yqz.googlegroups.com>, WM <mueckenh(a)rz.fh-augsburg.de> wrote: > On 20 Jun., 01:58, Tim Little <t...(a)little-possums.net> wrote: > > On 2010-06-19, Virgil <Vir...(a)home.esc> wrote: > > > > > There is, however, some question in my mind about the existence of a > > > list of all and ONLY computable reals. > > > > Why? �The computable reals can be proven countable, as you already > > know, so there is a bijection between N and the set of countable > > reals. > > That is not true. An exclusive list need not exist. > > The reals in a certain Cantor-list are countable. And if you form the > anti-diagonal of that list and add it (for instance at first position) > to the list, this new list is also countable. Again consttruct the > anti-diagonal and add it to the list. Continue. The situation remains > the same for all anti-diagonals you might want to construct. Therefore > all reals constructed in that way are countable. Nevertheless it is > impossible to put all of them in one list, because there would be > another resulting anti-diagonal. > > Conclusion: It is impossible to obtain a bijection of all these reals > with N although all "these" reals are countable with no doubt. Equal cardinality of two sets requires, by definition, a bijection between them. The naturals are, by definition of COUNTABLE cardinality so that any set of equally countable cardinality must have a bijection with the naturals. Cantor has shown that the set of all reals cannot biject with the naturals, ergo, the set of all reals is NOT of countable cardinality. Actually Cantor's original "diagonal" proof was based on the set of all functions from the naturals to a two element set, but several people have constructed bijections between that set of functions and the set of all reals. I have done it myself. |