In article <firstname.lastname@example.org>, "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote:
> "Virgil" <Virgil@home.esc> wrote in message > news:Virgil-4CE082.email@example.com... > > In article <firstname.lastname@example.org>, > > "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > > > >> "Virgil" <Virgil@home.esc> wrote in message > >> news:Virgil-71EA75.email@example.com... > >> > In article > >> > <firstname.lastname@example.org>, > >> > Newberry <email@example.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".