"Virgil" <Virgil@home.esc> wrote in message news:Virgil-6240F4.21454316062010@bignews.usenetmonster.com... > In article <4c1995e5$0$26118$afc38c87@news.optusnet.com.au>, > "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > >> > >> > It is proof that there is no countable set of all real numbers, since >> > any alleged such set is provably and constructably incomplete. >> > >> > Similarly, it is proof that there is no countable set of all >> > constructable numbers, since any alleged such set is provably and >> > constructably incomplete. >> >> I hate to disagree with you, because we are on much the same "side", but >> this is not correct. Cantor's proof shows that you cannot form a list of >> all >> Reals. This is not the same as the Reals being uncountable. > > If the reals were countable they would be listable, since such a list > would be a "counting" of them, so that NOT being listable implies NOT > being countable.
That does not follow, and I have already provided a counter-example. Computable numbers are countable, but cannot be listed.
> > An infinite set is defined to bee countable if and only if there is a > surjection from the set of natural numbers to that set. When such a > function is a bijection, it is commonly called a list. >
Only if the bijection can be explicitly created. There are countable sets which cannot be listed, such as the countable set of computable Reals.
> Since the set of reals is infinite but cannot be listed in this way, it > follows that the reals necessarily are NOT countable.
By this (incorrect) logic, the computable numbers must also be uncountable. But they are not.
>> >> You can use Cantor's diagonal construction to similarly prove that you >> cannot form a list of all computable numbers. However the computable >> numbers >> are in fact countable. You can't simply equate the two concepts; they are >> not exactly the same thing. > > For infinite sets, listability and countability are equivalent.
No. Witness the infinite set of computable numbers. Countable but not listable.
Cantor's proof shows that the set of Real numbers cannot be listed. It does not immediately follow that they are uncountable. Plenty of countably infinite sets cannot be listed. The set of computable numbers is one. The set of halting TMs is another.
