"Daryl McCullough(" <stevendaryl3016@yahoo.com> wrote in message news:hvic840ge3@drn.newsguy.com... > Peter Webb says... > >>"Tim Little" <tim@little-possums.net> wrote > >>Hmmm. But you cannot provide me with a list of all Computable numbers, can >>you? Which is what Cantor's diagonal proof requires. > > Cantor's proof assumes the *existence* of such a list. It doesn't > assume that you know how to compute it. >
If that is what you believe, then I am happy for the same rules to be applied to the purported list of all computable Reals.
>>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. > > No, it doesn't. If f is any mapping from N to computable numbers, > then antidiag(f) is a new real that is not in the image of f. > It doesn't matter whether f is recursively enumerable or not. > >>That a set cannot be listed is not the same as it is uncountable, > > I would say it this way: That a set is not recursively enumerable > does not imply that it is not enumerable. >
Bingo.
> The set of computable reals is enumerable, but not recursively > enumerable. The set of *all* reals is not enumerable. >
Correct.
>>You cannot give me a list of all Computable numbers, >>because I can use a diagonal construction to form a >>computable Real not on the list. > > If the list is computable, that's correct. If the list > is not computable, then that's not correct. >
Cantor proved that you cannot compute a list of Real numbers. As you point out, this is not the same as being uncountable.
>>Cantor's proof applied to Reals does *not* prove they are >>uncountable; > > It certainly does. If you assume that the set of reals is > countable, then that means that there is a bijection f from > the naturals to the reals. Cantor's proof shows that there > is no such bijection. >
No.
Exactly the same construction can be applied to a purported list of all computable Reals, but these are countable.
>>> If that doesn't answer your question, you'll have to clarify what you >>> mean by it. >>> >> >>What I mean is that Cantor proved you cannot provide a list of all Reals. > > He proved that there is no bijection between the naturals and the reals. > By definition, that means that the reals are uncountable. >
No, he proved that any purported list of all Reals must miss at least one Real.
Which is exactly the same as what I prove for computable Reals.
Yet the computable Reals are countable.
Clearly his proof (in its orginal and common form) does not prove the Reals are uncountable.
