Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Peter Webb on 19 Jun 2010 22:45 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1qpqr.jrj.tim(a)soprano.little-possums.net... > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> Umm ... they can be listed, but the list is not computable? > > Correct. Is that difficult for you to understand? > > >> 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? > > There is no single *algorithm* that computes them all. There is > however a clear mathematical definition of such a list. > > >> In Cantor's diagonal proof, the list of Reals is provided in >> advance, such that the nth digit of the nth item is known. > > Where is the phrase "provided in advance" used in the proof? Because Cantor's proof requires us to know the nth digit of the nth item on the list. Indeed Cantor's proof starts with a list, and then proves there is a Real not on the list. If you don't what is on the list already, you cannot possibly prove that some Real is missing. My proof is *exactly* the same, except for inserting the word "computable" in front of Real. > You > appear to be mistaking a simple form of conditional introduction in > the proof for some completely unfounded computability assumption. > > Suppose I say "suppose x is a real number. Therefore (x has some > property)". Do you take this to mean that x must be a *computable* > number, since it is "provided in advance"? > No. > > >> 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. > > Known? To whom? All is required is that it exists. That is, that > the list is a function from N to R and not some other type of > mathematical object. > No. Cantor's proof requires that the nth digit of the nth term is known. Otherwise the diagonal number cannot be constructed. > >> 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. > > You are reading a great deal of things into Cantor's proof that simply > are not there. I have now three times provided an explicitly defined > mapping from N to the set of computable reals. That is entirely > sufficient for Cantor's proof. No you haven't. If you have an explicit list, you could post it. In fact, just like Cantor, I only need to know the nth digit of the nth term for all n, so you can just post that if you like. > > However, even that much is unnecessary! Cantor's proof starts with a > conditional introduction and then discharges that conditional later in > the proof, so that *nothing* need be provided "in advance". > Incorrect. He says "if you give me any purported list of all Reals, I will produce a Real not on the list". Exactly as I do for computable numbers, in fact. > >> Given the list, its trivially easy to explicitly compute the >> anti-diagonal. Cantor provides an explicit construction. > > Given the digits of Chaitin's Omega, it's trivially easy to explicitly > compute Omega+1. That does not make Omega+1 computable. > But you can't give me all the digits of Chaitan's Omega, can you? Its not computable. So? > >> You cannot give me a list of all computable numbers. >> >> Try, if you like. > > Already done 3 times now. You have completely ignored it each time. > Give me a list of all computable numbers in the same form as Cantor's proof requires a purported list of all Reals, ie a list where the nth digit of the nth term is known. Surely this cannot be too hard? After all, a definition of a "computable Real" is that it can be determined to any required degree of accuracy, which is equivalent to the statement its decimal expansion can be determined. So by definition if the list contains only computable Reals, we know the nth digit of each term. > > - Tim
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. > > > > |