"Virgil" <Virgil@home.esc> wrote in message news:Virgil-4CE082.01003126062010@bignews.usenetmonster.com... > In article <4c259cd4$0$1029$afc38c87@news.optusnet.com.au>, > "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > >> "Virgil" <Virgil@home.esc> wrote in message >> news:Virgil-71EA75.23485925062010@bignews.usenetmonster.com... >> > In article >> > <b3413a4e-567b-4dfb-8037-21f14b826ede@g1g2000prg.googlegroups.com>, >> > Newberry <newberryxy@gmail.com> wrote: >> > >> >> > > No. (3) is not true, as it is based on a false premise (that the >> >> > > computable >> >> > > Reals can be listed). >> > >> > How is countability any different from listability for an infinite set? >> > >> > Does not countability of an infinite set S imply a surjections from N >> > to S? And then does not such a surjection imply a listing? >> >> It implies a listing must exist, but does not provide such a listing. >> >> The computable Reals are countable, but you cannot form them into a list >> of >> all computable Reals (and nothing else) where each item on the list can >> be >> computed. >> >> In order to list a set, it has to be recursively enumerable. Being >> countable >> is not sufficient. > > Both countability and listability appear to be the case if and only if > a listing exists, but neither requires specifying that listing. Is that > not so?
No.
If we take "listable" to mean we can (ummm) make a list of exactly those elements and no other, then this is not correct. A set can be countable but not listable.
AFAIK, "listable" is not a formally defined mathematical term. The formal term in mathematics which is closest to the intuitive idea of being able to explicitly list the members of a set is that it is "recursively enumerable". Not "countable". Being countable is necessary but not sufficient.
This is the problem I have with the standard presentation of Cantor's proof - it starts with a "list", and then proves there is an item missing from the list. Proving that no list can be prepared proves only that the Reals are not recursively enumerable, not the stronger condition they are uncountable.
I have no problem with the very similar proof of Cantor's that the power set has larger cardinality than the set itself, which suffices to prove the Reals are uncountable. It doesn't talk about "lists".
