In article <4c274337$0$12922$afc38c87@news.optusnet.com.au>, "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote:
> "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.
Then how can you prove a set to be countable? As far as I am aware there is only one way, by creating, or at least proving the existence of, a list of its members.
I do not consent to your definition of "listable". > > 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".
