Why can no one in sci.math understand my simple point?
in [Logic]
|
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. _
From: Tim Little on 19 Jun 2010 20:43 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". You appear to be ascribing some special significance to the initial "appearance" of x beyond the simple conditional introduction. 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. 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"? > 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. > 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. An infinite list of members of a set X is exactly a function from N to X. Nothing more or less. If you are interpreting Cantor's proof in any other manner, you are plain mistaken. - Tim
From: Tim Little on 19 Jun 2010 20:57 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? 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"? > 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. > 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. 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". > 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. > 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. - Tim
From: Tim Little on 19 Jun 2010 21:04 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)." You can continue the proof from here if you like. - Tim
From: Tim Little on 19 Jun 2010 21:13
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. > 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. > 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*. > 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. > 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. - Tim |