"Tim Little" <tim@little-possums.net> wrote in message news:slrni1jng7.jrj.tim@soprano.little-possums.net... > On 2010-06-17, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >> Cantor's proof applied to computable numbers proves you cannot form >> a computable list of computable numbers. > > Cantor's construction applied directly to lists of computable numbers > shows almost nothing. Given any list of computable reals, you can > produce an antidiagonal real not on the list. Unfortunately the > construction says nothing about whether the antidiagonal is computable > or not. >
Of course its computable. It is a trivial programming exercise to form a computable number not on the list, by simply doing digit substitutions. Cantor's proof provides an explicit and simple algorithm to form such a number, and it is extremely easy to compute.
> It takes quite a bit of extra work (not part of Cantor's proof) to > deduce that there is no computable list of all computable reals.
Cantor's proof applied to computable numbers proves it immediately and simply.
> > >> Cantor's proof applied to Reals proves you cannot form a computable >> list of Reals. > > Incorrect, and even WTF-worthy. Cantor's proof *is* applied to reals, > and nothing in it has anything whatsoever to do with computability. >
Correct. I never said otherwise.
> >> The property "that you cannot form a computable list" is not the >> same as the property "is uncountable". For example, computable >> numbers have the first property but not the second. > > I agree. It was Herc's deranged ramblings that brought computability > into this discussion in the first place, when they really are > completely irrelevant to Cantor's proof. >
Well, they are relevant if you try and make the mental jump from "cannot be listed" to "are therefore uncountable". This simply does not follow. The computable Reals cannot be listed either, but they are definitely countable.
> >> Cantor's proof is about what can be expressed in a list, and not >> directly about uncountable sets (which don't even get mentioned in >> the proof). > > "Cannot be expressed in a list" is actually one of many equivalent > definitions for the term "uncountable". Whether Cantor himself used > that specific word is irrelevant - the mathematical content of his > proof was to establish uncountability. >
So, are the computable number uncountable?
A Cantor construction applied to a purported list of all computable Reals will identify a computable Real not on the list. The diagonal is explicitly constructible given the list. Therefore by your rule/definition whatever they are uncountable. But in fact they are countable. How do you explain this?
