"Virgil" <Virgil@home.esc> wrote in message news:Virgil-8C47CC.23015417062010@bignews.usenetmonster.com... > In article <4c1aea06$0$17174$afc38c87@news.optusnet.com.au>, > "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > >> "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? >> >> > >> > - Tim > > According to every definition I can find, the computability of a > particular number ought not be dependent on the existence of any > particular listing of a countable set of numbers unless the ordering in > that listing is itself computable. >
Too complex/ambiguous for me to understand.
> So that the computability of a number cannot be dependent on any > particular listing unless that listing is itself computable. >
The concept of whether a number is computable does not on the face of it have anything much to do with lists of Real numbers, unless that Real number appears explicitly in the list, in which case it is obviously computable.
> Is there, for example, a computable well ordering of all computable > numbers? >
No. Not without the Axiom of Choice.
And nor can the computable numbers be listed explicitly, as a diagonal argument shows.
You can well-order computable numbers using AxC, but even that won't give you a "list" of computable numbers. (The AxC will allow you to assign each Real to an ordinal, which can be well-ordered, but as some of these ordinals are infinite they aren't a list in the sense of Cantor).
