"Virgil" <Virgil@home.esc> wrote in message news:Virgil-0266A6.firstname.lastname@example.org... > In article <email@example.com>, > "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > >> "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. >> > >> >> Its not. >> >> > 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. > > Ah! But that "listed by a terminating process" is not the same as merely > "listed"
Explain to me how my requirements for the input list of all computable Reals is different to Cantor's requirements for the input list of all Reals, other than the requirement that every item on the list is computable?
The whole purpose is to make the proof identical, other than limiting it to computable Reals only.
Cantor proved that the Reals cannot be explicitly listed, which is (in more modern terminology) that there is no recursively enumerable mapping from N -> R. That does not in of itself prove the Reals are uncountable; there are situations in which there is no r.e. mapping from N to some set, but that set is still countable. Like the set of all computable Reals. That there is no r.e. mapping from N to computable Reals is proven by a slight modification of Cantor's proof, as I have provided ad-nauseum. That the set of computable Reals is countable is easily proven, but does not seem disputed so I won't bother.