Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Peter Webb on 19 Jun 2010 22:14 "Virgil" <Virgil(a)home.esc> wrote in message news:Virgil-0266A6.00422119062010(a)bignews.usenetmonster.com... > In article <4c1c61ae$0$2162$afc38c87(a)news.optusnet.com.au>, > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > >> "Tim Little" <tim(a)little-possums.net> wrote in message >> news:slrni1ol51.jrj.tim(a)soprano.little-possums.net... >> > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> >> Of course there exists a mapping from N to computable numbers. But >> >> Cantor's proof requires more than that; it requires the mapping to >> >> be recursively enumerable such that we can also explicitly list >> >> them. >> > >> > It does not. If you believe otherwise, feel free to show where in >> > Cantor's proof any requirement for recursive enumerability is stated >> > or implicitly used. >> > >> >> Its not. >> >> > The simple fact is that no such requirement exists. Cantor's diagonal >> > proof applies to *every* mapping from N to R, recursively enumerable >> > or not, showing that no such mapping is surjective. >> >> No. It requires that any listing be provided in advance, so that the >> anti-diagonal can be formed. >> >> >> > >> > Your introduction of recursive enumerability into Cantor's proof is >> > entirely your own fabrication. >> >> Well, I did say it was my interpretation of what was going on. >> >> The simple fact is that if insert the word "computable" in front of every >> reference to "Real" in Cantor's proof that there is no list of all Reals, >> you produce a proof that thye computable Reals cannot be listed either. >> yet >> they are known to be countable. >> >> Cantor's proved that the Reals cannot be listed. It is your incorrect >> assumption that this means they are also uncountable. Some countable sets >> cannot be listed either, such as the set of Computable Reals. This is >> because the set of computable Reals is not recursively enumerable, and >> hence >> cannot be listed by a terminating process. > > Ah! But that "listed by a terminating process" is not the same as merely > "listed" 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? The whole purpose is to make the proof identical, other than limiting it to computable Reals only. Cantor proved that the Reals cannot be explicitly listed, which is (in more modern terminology) that there is no recursively enumerable mapping from N -> R. That does not in of itself prove the Reals are uncountable; there are situations in which there is no r.e. mapping from N to some set, but that set is still countable. Like the set of all computable Reals. That there is no r.e. mapping from N to computable Reals is proven by a slight modification of Cantor's proof, as I have provided ad-nauseum. That the set of computable Reals is countable is easily proven, but does not seem disputed so I won't bother.
From: Peter Webb on 19 Jun 2010 22:29 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1qp19.jrj.tim(a)soprano.little-possums.net... > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> "Tim Little" <tim(a)little-possums.net> wrote in message >>> The simple fact is that no such requirement exists. Cantor's diagonal >>> proof applies to *every* mapping from N to R, recursively enumerable >>> or not, showing that no such mapping is surjective. >> >> No. It requires that any listing be provided in advance, so that the >> anti-diagonal can be formed. > > I did not have you pegged as someone who does not understand the > nature of mathematical proof, but it seems I was mistaken. Cantor's > proof is of the simple form > > P(x) [ Conditional introduction ] > ... [ Bulk of work goes here ] > ~Q(x) > P(x) -> ~Q(x) [ Conditional proof ] > ~Ex (P(x) and Q(x)) > > In this case P(x) is the predicate "x is a function mapping natural > numbers to real numbers". Q(x) is the predicate "x is surjective". > > Note that nowhere does it require any additional properties on x, such > as being recursively enumerable, or your mathematical nonsense term > "provided in advance". Cantor's proof requires the purported list of all Reals to be provided. He then finds a Real not on the list. My proof works exactly the same way. You give me a purported list of all computable Reals, and I find a computable Real not on the list. The stuff about the set being "recursively enumerable" is not part of the proof. It is my explanation of why you cannot form a list of all computable Reals. Its clearly not because the computable Reals are uncountable, because they are known to be countable. > You appear to be ascribing some special > significance to the initial "appearance" of x beyond the simple > conditional introduction. > No idea what you are talking about. Perhaps if you could explain how my proof differs from Cantor's proof, that would be a start. > If I have a proof that there is no greatest real number, and format it > as follows: > > Suppose x is a real number. Then (bunch of stuff using the definition > of real number) there exists x+1 such that x+1 > x. Therefore there > does not exist a greatest real number. > Yes. > This has the same logical form as Cantor's proof, just substituting > real numbers for lists and greatest for complete. Do you insist that > this proof holds only for computable x, because it must be "provided > in advance"? > No it isn't. Its nothing like Cantor's proof. 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. > >> The simple fact is that if insert the word "computable" in front of >> every reference to "Real" in Cantor's proof that there is no list of >> all Reals, you produce a proof that thye computable Reals cannot be >> listed either. > > No, you don't. You get an invalid proof, because although the > antidiagonal can be proven to be real regardless of what function maps > natural numbers to reals, it cannot be proven to be computable. It is extremely easy to compute. Take the nth decimal place of the nth term. We can alsaways do this, because by one definition a computable number can be calculated to any required degree of accuracy. Do the digit substitution. That is clearly computable. Therefore the anti-diagonal can be calculated to any required degree of accuracy, and is therefore computable. > > >> Some countable sets cannot be listed either, such as the set of >> Computable Reals. This is because the set of computable Reals is not >> recursively enumerable, and hence cannot be listed by a terminating >> process. > > Your requirement for "recursively enumerable" and "terminating > process" is completely irrelevant. Irrelevant to the proof, yes. But very relevant to explaining what is happening. My proof does not use the terms "recursively enumerable" or "terminating processes". I introduced these terms to explain why the list of all computable numbers cannot be formed. That such a list cannot be formed is easily proved using the slight modification to Cantor's proof that I provided. I was merely trying to explain the conclusion of the proof - why there can be no list of all computable numbers. Its certainly not because they are uncountable, which is the common misunderstanding of Cantor's original proof. > An infinite list of members of a > set X is exactly a function from N to X. Nothing more or less. Correct. > If > you are interpreting Cantor's proof in any other manner, you are plain > mistaken. > 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. > > - Tim
From: Peter Webb on 19 Jun 2010 22:31 "K_h" <KHolmes(a)SX729.com> wrote in message news:xPOdncxHLvYyw4DRnZ2dnUVZ_tWdnZ2d(a)giganews.com... > > "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. No. Show me where I use this assumption in my proof. > 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. > Cantor's original proof requires the list to be provided in advance, such that the nth digit of the nth item on the list is known. My proof has exactly the same requirements. That is the whole point. > _ > >
From: Tim Little on 19 Jun 2010 22:34 On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > Cantor's proof that Reals cannot be listed requires an explicit > list, such that the nth digit of the nth term can be determined. No, it just requires that the nth digit of the nth term exist. It does not require that the nth digit of the nth term be computable by a finite algotihm. It does not even require that there is a finite mathematical formula defining it. > What Cantor proved (in more modern parlance) is that there is no > recursively enumerable function from N -> R. False on three counts: 1) Recursive enumerability has nothing to do with it. 2) The word you should be using instead of "recursively enumerable" is "surjective". 3) There are plenty of recursively enumerable functions from N -> R. Please, learn how to understand mathematical proofs so that you don't embarrass yourself further in future. - Tim
From: Tim Little on 19 Jun 2010 22:44
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". > 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. > 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. >> 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. 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? - Tim |