"Daryl McCullough" <firstname.lastname@example.org> wrote in message news:email@example.com... > Peter Webb says... > >>Cantor's diagonal proof does *not* show the Reals are uncountable; it just >>proves the much weaker statement that "the Reals cannot be listed". > > Those two statements mean the *same* thing! > > A "list" of objects is just a function that maps each natural number > to an object. To say that a set is listable is just to say that there > exists a list that contains all objects in the set. And that's exactly > what it means to say that a set is countable. > > -- > Daryl McCullough > Ithaca, NY >
OK. The set of computable Reals. These are countable but cannot be listed. How does your definition handle that situation?
It seems to me that the "problem" with computable Reals is that the set of computable Reals is not recursively enumerable. This means we cannot form a list that includes exactly the computable Reals, or that list would be an enumeration. Even though they are countable.
That, BTW, is my own interpretation of what is happening.
Whether you accept this or not, the simple fact is that Cantor's proof can be applied to any purported list of all computable Reals and used to generate a computable Real not on the list, but this does not prove that the computable Reals are uncountable; they are not.
Similarly, you can't assume that just because you can't form a list of all Reals, they are uncountable. I suspect that Cantor's diagonal proof actually proves the set of Reals is either "not recursively enumerable" or "uncountable"; this would be consistent with the results of applying a diagonal proof to computable Reals.