On 2010-06-20, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > Thus if your list contained say: > > .1111111 > .2222222 > .1111222 > > The antidiagonal is 0.212... > > Notice that I computed this quite easily?
I notice that your algorithm only works for n < 4.
>> You will not be able to fill that hole, because there are >> well-defined functions L for which antidiag(L) is *not* a >> computable real. There are even explicitly-definable such lists, >> and furthermore there are such lists where there are only two >> values in the range: for example, let L(n) = 0 if the n'th digit of >> Omega is 0, L(n) = 1/9 otherwise. > > I am having a bit of trouble computing even the first term of that.
According to one of Chaitin's papers, the first term is 0.
But that's irrelevant: it is either 0 or 1/9 and in *both* cases it is a computable real. You personally might not know what it is, I might not know what it is, but the list entry exists and is a computable real either way.
> I am also wondering how Cantor would have felt about that. I can't > see that he can change a "1" to a "2" etc if he doesn't know what > the value is.
You appear to be laboring under the misapprehension that Cantor had to change any value to anything.
He proved that if *there exists* a list of reals, then *there exists* an antidiagonal real that is not on the list. If we don't know what is on the list, then we won't know what the antidiagonal is - but we still know it has one.
> But you have made an excellent point in your example. When Cantor is > confronted with some digit as poorly defined your Chaitan's number > example
It's not poorly defined at all; it is precisely defined.
But even that is more than required: the proof even works for *undefinable* lists of reals. For every hypothetical mathematical object that is a list of reals, that list has an antidiagonal.
> it can simply say "I don't care what the number actually is". There > is not the same luxury with computable Reals; this act of > arbitrary/random choice can make them uncomputable, as your example > shows.
It is not arbitrary or random at all. Omega has a precise mathematical definition and is a single real value.
> Well, yes, but I am failing to see how you are providing a list of > computable Reals when you won't actually tell me even what is the > first computable Real on the list.
I did tell you with clear mathematical precision.
> Cantor's algorithm requires slightly more than a set of Reals, it > also demands they are ordered for us - there is a mapping from N to > that set.
I provided that mapping. It is precisely defined and mathematically unambiguous, merely difficult to use in practice.
> That's still a nice example, that every item in a list can be > computable but the anti-diagonal is not. But I still don't think you > are really playing fair with this one.
Fairness has nothing to do with it. I already provided far more than Cantor's proof assumes.
> You have to tell me what the first, second, third etc items are on > the list. I mean, that's what a list is after all, a mapping from N, > and that is what Cantor's proof requires as input.
As state before, Cantor's proof does not require any input at all. It proves the single *closed* proposition "there does not exist a complete list of real numbers". No free variables, no input.
It is *not* a schema of theorems "L is not a complete list of real numbers", one for each L. In some fields of mathematics such schemata exist, but Cantor's theorem was not an example of such.
