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: Tim Little on 19 Jun 2010 19:58 On 2010-06-19, Virgil <Virgil(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. > For countability of a set it is certainly sufficient to have a list > containing all its members even if that list is allowed to contain > other things as well. That is true. It is also true that the existence of a surjection from N to X implies the existence of a bijection from N to X, even without the Axiom of Choice. (It is not necessarily true without AC if you replace N with an arbitrary set) - Tim
From: Mike Terry on 19 Jun 2010 20:04 "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. 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: Tim Little on 19 Jun 2010 20:10 On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > Well, there are lots of definitions of a computable Real, I will use > Wikipedia's most intuitive definition: "computable reals, are the > real numbers that can be computed to within any desired precision by > a finite, terminating algorithm." Most intuitive, and also least mathematically useful. However, we can work with that. The input to the algorithm is the desired precision and the output is a suitable approximant, correct? > 1. Given a list of computable Reals, we can identify the nth > computable Real on the list by simply counting down to the nth > entry. 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. The rest of your argument depends upon this non-algorithmic step, and so is snipped. However, it occurs to me that your misunderstanding may be deeper than I expected. Let's consider a simpler case: "lists" of length 1. Suppose x is a real number, say Chaitin's Omega. Is x+1 computable? If so, why? If not, how does this differ from "suppose L is a list of real numbers. Is antidiag(L) computable?" - Tim
From: K_h on 19 Jun 2010 20:20 "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message news:4c1c65f4$0$2162$afc38c87(a)news.optusnet.com.au... > >>>>> Perhaps if you could point out to me why you believe >>>>> Cantor's proof that not all Reals can be listed (as it >>>>> appears you do) but you don't believe my proof that >>>>> not all computable Reals can be listed. They appear >>>>> identical to me. >>>> >>>> All computable reals can be listed, but there is no >>>> finite algorithm for doing so. An "infinite algorithm" >>>> could list every computable real. An anti-diagonal, >>>> then, could be generated from this list but the >>>> algorithm creating the anti-diagonal is implicitly >>>> relying on the "infinite algorithm" underlying the >>>> list. In that sense the anti-diagonal is not >>>> computable. >>> >>> Agreed. >>> >>>> The set of all reals are a different story. Even with >>>> an "infinite algorithm" generating a list of reals, >>>> there is no way such a list could contain every real. >>>> For a proof, do a google search on Cantor's theorem. >>>> >>> >>> No, Cantor's diagonal construction does not prove this, >>> and nor is any of this machinery part of his proof. >>> >>> Cantor's proof applied to computable Reals proves that >>> the computable Reals cannot be listed. >> >> You have contradicted yourself. I wrote "All computable >> reals can be listed,..." and your reply was "Agreed". > > Typo, sorry. > > My whole argument is that they cannot be listed in their > entirety, or we could use a Cantor construction to produce > a computable Real not on the list. You are wrongly assuming that only computable sets exist. That leaves out many sets. For example, if A is a subset of N, with |A|>1, most of the functions from N to A don't exist by your thinking. Because of your wrong assumption you falsely conclude that your anti-diagonal produces a computable real from the non-computable list containing all computable reals. _
From: K_h on 19 Jun 2010 20:19
"Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message news:4c1c65f4$0$2162$afc38c87(a)news.optusnet.com.au... > >>>>> Perhaps if you could point out to me why you believe >>>>> Cantor's proof that not all Reals can be listed (as it >>>>> appears you do) but you don't believe my proof that >>>>> not all computable Reals can be listed. They appear >>>>> identical to me. >>>> >>>> All computable reals can be listed, but there is no >>>> finite algorithm for doing so. An "infinite algorithm" >>>> could list every computable real. An anti-diagonal, >>>> then, could be generated from this list but the >>>> algorithm creating the anti-diagonal is implicitly >>>> relying on the "infinite algorithm" underlying the >>>> list. In that sense the anti-diagonal is not >>>> computable. >>> >>> Agreed. >>> >>>> The set of all reals are a different story. Even with >>>> an "infinite algorithm" generating a list of reals, >>>> there is no way such a list could contain every real. >>>> For a proof, do a google search on Cantor's theorem. >>>> >>> >>> No, Cantor's diagonal construction does not prove this, >>> and nor is any of this machinery part of his proof. >>> >>> Cantor's proof applied to computable Reals proves that >>> the computable Reals cannot be listed. >> >> You have contradicted yourself. I wrote "All computable >> reals can be listed,..." and your reply was "Agreed". > > Typo, sorry. > > My whole argument is that they cannot be listed in their > entirety, or we could use a Cantor construction to produce > a computable Real not on the list. You are wrongly assuming that only computable sets exist. That leaves out many sets. For example, if A is a subset of N, with |A|>1, most of the functions from N to A don't exist by your thinking. Because of your wrong assumption you falsely conclude that your anti-diagonal produces a computable real from the non-computable list containing all computable reals. _ |