In article <4c1ae37b$0$17178$afc38c87@news.optusnet.com.au>, "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote:
> "Virgil" <Virgil@home.esc> wrote in message > news:Virgil-11576A.01595017062010@bignews.usenetmonster.com... > > 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. > > No. > > Lets imagine you give me a list which is supposed to contain all computable > numbers in [0, 1.0] , and possibly some other Reals. You can even have some > computable Reals appearing multiple times in the list. > > I can use the Cantor diagonal construction to create a Real not on the list, > which means that it is not a computable number. So the list cannot contain > all computable numbers.
How does showing the list does not contains a non-computable number show that it does not contain a computable number? > > That you cannot list some set is not the same as the set in uncountable.
That does not parse.
> Computable numbers are countable but cannot be listed.
The only ways I know to show a set to be countable are: 1: Showing that its elements can be listed (surject N to the set). 2: Showing it to be a subset of a countable set. You have now claimed that neither of these is possible for the set of non-computable numbers.
