"Virgil" <Virgil@home.esc> wrote in message news:Virgil-D224DB.13324818062010@bignews.usenetmonster.com... > In article <4c1b2c8e$0$1025$afc38c87@news.optusnet.com.au>, > "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > >> "Tim Little" <tim@little-possums.net> wrote in message >> news:slrni1m63n.jrj.tim@soprano.little-possums.net... >> > On 2010-06-18, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >> >> I made no premise. >> > >> > Sure you did: you assumed that no list of computable numbers can >> > exist. You also assumed an incorrect definition of "computable". >> > >> >> No, I assumed that a list of all computable numbers can exist. Then I >> gave a >> simple algorithm which forms a computable number which is not on the >> list. I >> therefore proved that no list of all computable numbers can exist. >> >> It is *exactly* the same as Cantor's proof that the Reals cannot be >> listed. >> >> It is of interest because it is known that the computable numbers are >> countable. Therefore the property "cannot be listed" is *not* the same as >> the property "is uncountable". >> >> Cantor's diagonal proof does *not* show the Reals are uncountable; it >> just >> proves the much weaker statement that "the Reals cannot be listed". > > Given the axiom of choice, as in ZFC, any countable set must be, at > least theoretically, listable, though such a listing need not be > computable.
No. The AxC will allow you to always pick another Real to add to your list, but not to biject the Reals with N which is what a list requires. You can AxC a countably infinite number of times to form a countable list, but it will not include all Reals.
> > And if countable, for infinite sets, does not mean bijectable with N > (or listable), what does it mean?
Bijectable with N and "listable" are not the same. To be "listable" the set must be countable and recursively enumerable.
