>> Lets imagine you give me a list which is supposed to contain all >> computable >> numbers in [0, 1.0] , and possibly some other Reals. You can even have >> some >> computable Reals appearing multiple times in the list. >> >> I can use the Cantor diagonal construction to create a Real not on the >> list, >> which means that it is not a computable number. So the list cannot >> contain >> all computable numbers. > > How does showing the list does not contains a non-computable number show > that it does not contain a computable number?
The diagoinal number is clearly computable. There is a very simple algorithm for generating it, and this algorithm is easily implemented in a Turing Machine.
>> >> That you cannot list some set is not the same as the set in uncountable. > > That does not parse. >
The property "this set cannot be listed without missing some elements" is not the same as the property "this set is uncountable".
Computable numbers cannot be listed without missing some elements, but they are definitely countable.
> >> Computable numbers are countable but cannot be listed. > > > The only ways I know to show a set to be countable are: > 1: Showing that its elements can be listed (surject N to the set). > 2: Showing it to be a subset of a countable set. > You have now claimed that neither of these is possible for the set of > non-computable numbers.
For the set of all computable numbers:
Proposition 1 is not true. You cannot list all computable numbers, as you can use a diagonal argument to generate a computable number not on the list.
Proposition 2 is true. The list of computable numbers is trivially a subset of the Reals that can be generated by TMs (in fact its the same set), and this is a countable set.
So your two ways of determining if a set is countable are clearly not the same. Things can be countable according to (2) but not countable according to (1).
