In article <4c19cef9$0$17178$afc38c87@news.optusnet.com.au>, "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote:
> "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.
One can create lists which contain all of the computable numbers , (or all of the halting TMs) but which, of necessity, list some other things as well.
