"Tim Little" <tim@little-possums.net> wrote in message news:slrni1jadp.jrj.tim@soprano.little-possums.net... > On 2010-06-17, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >> I hate to disagree with you, because we are on much the same "side", but >> this is not correct. Cantor's proof shows that you cannot form a list of >> all >> Reals. This is not the same as the Reals being uncountable. > > An infinite list of reals is just a function from N to R. Cantor's > proof shows that no such function is surjective (and so in particular, > not bijective). That is *exactly* the same as the Reals being > uncountable. > > >> You can use Cantor's diagonal construction to similarly prove that you >> cannot form a list of all computable numbers. > > No, you can use something like Cantor's diagonal construction to > similarly prove that you cannot form a *computable* list of all > computable numbers. The qualifier is necessary to the proof. >
Precisely, and that is the error.
Cantor's proof applied to computable numbers proves you cannot form a computable list of computable numbers. Cantor's proof applied to Reals proves you cannot form a computable list of Reals.
The property "that you cannot form a computable list" is not the same as the property "is uncountable". For example, computable numbers have the first property but not the second. Cantor's proof is about what can be expressed in a list, and not directly about uncountable sets (which don't even get mentioned in the proof).
