In article <4c1b5407$0$17174$afc38c87@news.optusnet.com.au>, "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote:
> "Tim Little" <tim@little-possums.net> wrote in message > news:slrni1mcki.jrj.tim@soprano.little-possums.net... > > On 2010-06-18, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > >> Of course this number is computable; there > >> is a simple algorithm to compute it. > > > > I see you still haven't consulted a definition of "computable number". > > Umm, yes I have. > > > No worries, let me know when you have. > > > > > > - Tim > > There can be no list of all computable numbers. > > The proof is quite simple. Lets imagine that you have such a list of all > computable numbers. > > Lets say it starts off ... > > .111111... > .141592 ... > .71828 ... > > Take the 1st digit of the first number. If it is a "1", then make the first > digit of the diagonal number "2", otherwise make it a "1". Well, the first > digit of the first number is a "1", so the first digit of the diagonal > number is a "2". > > Now take the second digit of the second number and do the same substitution. > Its a "4", so the second digit of the diagonal number is "1". > > Now take the 3rd digit of the 3rd number ... its a "8", so the third digit > of the diagonal number is a "1". > > Continue in this fashion. > > The number that is produced is clearly "computable", because we have > computed it. Its also clearly not on the list. Therefore the list cannot > have contained all computable numbers. > > Exactly the same as Cantor's proof that the Reals cannot be listed. > > However, this does *not* mean that there are an uncountable number of them. > The computable numbers are countable. > > And similarly Cantor's proof does not show that there are an uncountable > number of Reals. It proves exactly what Cantor claimed it did, which is that > you cannot list all Reals.
At least one definition of "countability" for infinite sets is "listability", i.e., existence of a surjection from N to the set in question.
By what definition of countability is an infinite set which cannot be listed still regarded as countable?
