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: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
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 |