"Tim Little" <tim@little-possums.net> wrote in message news:slrni1qp19.jrj.tim@soprano.little-possums.net... > On 2010-06-19, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >> "Tim Little" <tim@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.
