"Tim Little" <email@example.com> wrote in message news:firstname.lastname@example.org... > 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. >
Works for any n. I just picked 4 as an example.
Indeed, I can explicitly compute the anti-diagonal to any arbitrary degree of accuracy.
> >>> 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.
OK, so the first digit of the anti-diagonal is "1".
What is the second item on your purported list of all computable Reals?
> > 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.
Yes. But you haven't provided a list of your computable Reals; you have just provided a set of possible computable Reals. You haven't told me what the first term is, your second term is, etc.
And BTW your set is missing 0.333.....
> > >> 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. >
OK, I have a list of all Reals. Which real is missing?
> >> 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. >
No, its not precisley defined, you can't tell me its value to arbitrary accuracy.
Specifically you can't tell me the nth digit. You will note Cantor's proof uses the nth digit of the nth item on the list to construct a missing Real. I ask for no more or less.
> 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. >
And every list of computable numbers has an anti-diagonal. Computable numbers are after all Reals. By your own statement, you are saying that a list of computable Reals also has an anti-diagonal. And guess what? Its not on the list.
> >> 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. >
What is nth digit?
You see, Cantor's construction of the anti-diagonal uses the nth digit of the nth item on the list. If I am going to construct the anti-diagonal number, like Cantor did, I need to know the nth digit of the nth item.
> >> 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.
Not sufficient for Cantor's proof. This accepts as input the decimal expansions of every item on the list. You have not provided this.
> > >> 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.
OK, what is the 23rd item on the list?
I really can't tell you what Reals are missing from the list unless you supply the decimal expansion of every item in the list, any more than Cantor can tell you what number is missing from a list without being bold what numbers are on the list.
This shouldn't be a problem; one of the definitions of a computable number is that it can be specified to any required degree of accuracy; I want merely the first n digits in its decimal expansion.
> > >> 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. >
How exactly do you think Cantor would prove there was a real missing from a list if you didn't tell him exactly what was on the list already?
How could he prove Chaitan's constant was missing, unless you told him what the value of Chaitan's constant was?
> >> 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.
Well no. It starts off with a purported list of all Reals, and then shows at least one is missing.
> > 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. > > > - Tim