Re: Cantor's diagonal proof wrong?

From: Todd Trimble (trimble1_at_optonline.net)
Date: 11/20/04 

Date: Sat, 20 Nov 2004 13:55:15 +0000 (UTC)

On 20 Nov 2004, Curt Welch wrote:
>"*** T. Winter" <***.Winter@cwi.nl> wrote:
>> In article <20041119191132.166$3I@newsreader.com> curt@kcwc.com (Curt
>> Welch) writes: ...
>> > I can write Sum(n=1 oo | 3/(10^n)) and I can replace those words with
>> > 1/3 in any equation, and not change the value, the meaning, or the
>> > truth, of that equation.
>> ...
>> > So, for any concept which translates to a processes which never ends,
>> > we know that the process can't actually exist, but it can still be
>> > useful to talk, and think, as if it did.
>>
>> But in mathematics it is *not* thought that the actual process of adding
>> infinitely many numbers together does exist.
>
>Yes, and I have no issue with infinite series. I never said I did. I just
>said the infinite processes doesn't actually exist because it doesn't and
>can't complete (and that confused some people as to what my point was
>probably because they haven't read all my posts in this rather out of
>control thread). We simply use the logic of limits to determine, and
>define, what numbers each series is equivalent to. And that's great,
>valid, and useful.
>
>But in some places, like Cantor's diagonal proof, the idea of an infinite
>sized set of natural numbers gets treated in a logical argument as if it
>were a finite sized set, as if it did exist and as if were possible to
>actually construct the entire diagonal anti-value. If you look at that
>argument about the infinite set of natural numbers like people look at
>limits, you would not be so quick to assume that the application of proof
>by contraction in the form used there is valid - as I tried to demonstrate
>by showing how invalid the logic looks if you think of both the
>construction of the mapping table and the construction of the diagonal
>anti-value was done by a process which can never complete.
>
>If you were given a description of the process which mapped the natural
>numbers to the reals, say by a function such as f(n) = r, then you can
>analyze what it will do without having to actually run the processes to
>completion - as is commonly done with infinite series and which is the
>foundation of calculus.
>
>But in Cantor's argument, the actual mapping function is not given. It's
>only assumed to exist. Then they argue that the diagonal anti-value can be
>constructed for any mapping function provided - which is still a valid
>idea.

OK, stop right there. You said "the diagonal anti-value can be
constructed for any mapping function provided, *which is still a
valid idea*. There, you said it: the construction is valid.

>But then they make a conclusion that is invalid. They assume that
>since the anti-diagonal value being constructed doesn't match any single
>row, that it's valid to say that it doesn't match all the rows. And as
>valid and as logical as that sounds as that sounds, it's not at all valid
>when you are constructing infinite sized real values in a infinite sized
>table. This is because it's impossible to construct the entire
>anti-diagonal value,

Whoa, whoa, whoa. Now you say you can't construct the entire
anti-diagonal value. How come the construction was valid only
a paragraph ago?

Look, you seem to be really confused. The construction is simply
a matter of composing functions. One assumes (as part of the proof
by contradiction) that one has a table which can be presented as
a function
                   F
            N x N --> {0, 1, 2, ..., 9}

and one then forms a composite function

      diag F s
    N ----> N x N --> {0, 1, 2, ..., 9} --> {0, 1, 2, ..., 9}

where diag is defined by diag(n) = (n, n), and s is a
certain function with no fixed point (e.g., s(i) = i+1
if i < 9; s(9) = 8).

The "anti-value" as you call it is this composite function.
No "infinite process" is involved in composing finitely many
functions. In fact, it's really easy: g(n) = s(F(n, n)).

As an engineer with an interest in AI (and presumably in
computer science), you probably compose functions all the
time, perhaps without realizing it. Did you realize that's
all you're doing here?

Todd Trimble

Quantcast