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.
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.
Since the set of reals is infinite but cannot be listed in this way, it follows that the reals necessarily are NOT countable. > > 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.
