"Virgil" <Virgil@home.esc> wrote in message news:Virgil-6672C4.email@example.com... > In article <firstname.lastname@example.org>, > "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > >> > >> > Since by definition, "listability" = "countability", Cantor's proof of >> > unlistability proves uncountability. >> >> Really? Where did you get that from? >> >> The computable Reals cannot be listed. >> >> Therefore according to you they are uncountable. >> >> But they aren't. >> >> Maybe your definition needs a little work? > > Consider the set of computable numbers, S. > > According to http://en.wikipedia.org/wiki/Countable_set, > one definition of such a set, S, being countable is that there is a > injective function from S to N, which is equivalent to there being a > surjective function from N to S. > > Since you object to there being any bijection from N to any superset of > S, you must equally be rejecting any surjection from N to S and > rejecting any injection from S to N, since from any such bijection such > a surjection is easily derived. > > So in what sense do you claim that the the set S of computable numbers > is countable? >
"Although the set of real numbers is uncountable, the set of computable numbers is countable".
Easily proved. All computable numbers can be generated by a finite TM (by definition), and there are only countable finite TMs (as these can easily be enumerated).
> It is certainly not in any sense that I am aware of.
That a set of Real numbers cannot be listed is *not* the same thing as the set is uncountable. Cantor's proof does *not* demonstrate that Reals are uncountable, it just proves there can be no explicit enumeration of them. This is easily seen by comparison with a diagonal proof that all computable Reals cannot be listed - this doesn't immediately mean they are uncountable, as they aren't.