"Tim Little" <firstname.lastname@example.org> wrote in message news:email@example.com... > On 2010-06-19, Peter Webb <webbfamily@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. >
> 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.