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". 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.
