Re: Cantor's diagonal proof wrong?

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

Date: Sun, 21 Nov 2004 14:30:02 +0000 (UTC)

On 20 Nov 2004, Curt Welch wrote:
>trimble1@optonline.net (Todd Trimble) wrote:
>> On 20 Nov 2004, Curt Welch wrote:
>> >"*** T. Winter" <***.Winter@cwi.nl> wrote:
>
>> 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?
>
>I've already explained this about 10 times. But as long as someone is
>interested, I'll keep going.
>
>The problem is here is 100% language issues. What does "constructed" mean?
>How I was using it has a subtle but very important difference from how you
>were hearing it.
>

Well, use it however you want. But I think Dave Seaman's response
was very much to the point: that in a fully formal presentation,
the word "constructed" does not appear. What does appear are
existential quantifiers whose use is governed by very carefully
spelled out rules of first-order logic, and which (as I've pointed
out before) do not assert anything like physical existence or
whatnot.

I've said it before; I'll say it again: your objections are
philosophical, not mathematical. Yes, the problem is *language*;
more exactly, the problem is that you are imbuing technical
terms in mathematics with some extra-mathematical meaning.

>What I say, is that it's perfectly valid to talk about the algorithm for
>constructing the diagonal. The algorithm is trivial, and can be written to
>run on any computer. Just extract the correct digit from a finite location
>of each row, change it, and use that to construct the anti-diagonal.
>
>But, whether a person is using that procedure, or a computer is using the
>procedure, it will NEVER FINISH constructing the anti-diagonal. It will
>always be a work in progress. You can specify the algorithm for
>constructing the anti-diagonal, but you can not built the entire
>anti-diagonal value. And this point, which you choose to ignore in your
>mind, because you have been trained to think like that, is a point which
>changes the argument from valid, to not valid.

You don't know what's in my mind, or how I have been trained to
think. Stick to what you do know.

There are a number of intuitions about what a function "is",
including function-as-algorithm, but these intuitions do not
enter into deciding whether an argument is valid or invalid.
Your declaration as to what a function "is" is a philosophical
one, and as such is vulnerable to issues of language use,
whereas the correctness of Cantor's proof is a purely mathematical
issue which you have yet to master (by your own admission), as
this is tied to the syntax of predicate calculus and the axioms
of set theory.

>
>> Look, you seem to be really confused.
>
>I know you think I'm confused. I was confused at the start of this thread
>about how some important things are formally defined in mathematics. But
>about what I'm talking now, there is no confusion. Everything you read
>some of my words and it doesn't make sense, it's because you don't
>understand my message. Keep looking for a way to interpret my words until
>you find a meaning that does make sense, and then you will be able to see
>what I'm talking about.

Actually, I believe I do know what you're talking about. But
your point is not a mathematical one.

>
>> 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?
>
>Do you realize what you are doing here?

Yup.

>
>Do you understand that it's impossible in this universe to "compose
>functions" without an agent doing the actual work?

<Sigh> Well, that's why we have formal languages in mathematics,
so that such philosophical issues, interesting though they may be,
are beside the point in deciding validity of mathematical arguments.
But to argue in an intelligent and informed manner about this,
one has to understand formal deductions in a logical calculus
(e.g., Gentzen sequent calculus), and I don't believe you've
quite come to grips with this (your great strides in the past
few days notwithstanding).

One can represent relational (and in particular functional)
composition by a first-order formula such as

        Exists_{y} R(x, y) & S(y, z)

and the manipulation of logical formulae according to carefully
spelled out rules of inference is what separates mathematical
language from other forms of language use.

It does require an agent to recognize whether a fully formal
proof is correct, beginning with axioms written in a first-order
language. Fortunately, that is a finitistic procedure.

>
>Do you understand that the language you are using, which makes it easy to
>understand various aspects of math, is blinding you to what you are really
>talking about?

Um, again, stick to the facts -- you don't know what I may or
may not be blind to.

>
>Your functions are algorithms which, if they are to exist, and if they are
>to actually do what you say they do, must be implemented in some type of
>hardware, whether that's computer hardware, or neural brain hardware.

Says you. All I did is write down a formula. I take comfort
in the fact that I know how to perform correct arguments with it.

>
>The language you use to talk about these things hides that fact from you.

Well, you seem to be given to ex cathedra pronouncements on
what functions "are", but I'm not playing that (language) game --
I'm addressing the title of your thread: whether the diagonal
proof is wrong according to the rules of the mathematics game.
It's not.

>It hides it so well, you don't even seem able to grasp what I'm talking
>about.

Huh.

>
>Your function is just a description of how the missing value is
>constructed. And in order for it to be constructed, it must be given every
>digit from the diagonal, and the hardware which follows your function must
>take that digit, and produce the answer. And when you look at the logic of
>the hardware trying to actually construct the diagonal anti-value, it
>becomes clear that the proof which sounds so strong in the normal context,
>is no longer valid.
>
>Because it is not possible to construct the entire anti diagonal, it is not
>valid to say that the value is missing from the table. The value as
>constructed, can always be further down in the table.

Yeah, I hear your line of reasoning, and it always boils down
to saying that infinite things cannot be constructed. But
whoever said mathematicians construct infinite things, or that's
even what they think they are doing? I for one don't think
that's what I'm doing. I'm manipulating finite formulas.

>
>For example, what if I used a mapping function which, for each row,
>generated a new real value based on the same anti-diagonal algorithm you
>use in the proof. It would by definition be generating every value you
>generate, and placing it in the next row. Because it's infinite, your
>anti-diagonal construction algorithm would never be able to catch up to it.
>In this case, every value produced by your algorithm for constructing the
>anti-diagonal is guaranteed to be in the table.

Well, you see, you're not actually following the argument then --
you're presenting some other straw-man argument.

In forming the proof by contradiction, one starts with an
assumption that there exists a bijection X --> 2^X. (Exercise:
write down a first-order formula in Zermelo set theory which
formalizes this.) So that bijection is given to start the
argument. But in your straw-man argument, you don't start
with the function, you "construct" the function concurrently
with the argument so as to always stay one step ahead.

I think this shows that you still don't grasp the structure
of the argument. One supposes *given* a bijection X --> 2^X,
and one works from there toward the contradiction. Not ask
for a little bit of the bijection at a time! (Please, sir,
what is your n-th number? Can I have another? <whack>)

Sheesh. What a big steaming pile.

>
>So, you have an algorithm for constructing the anti-diagonal which says
>it's not in any row, but yet my mapping function is the same algorithm, and
>it's able to guarantee that everything your function constructs _IS_ in the
>table in row N+1. So how is it possible to conclude that the diagonal is
>not in the table, when every number is guaranteed to be in the table and
>this construction never ends?
>
>If it ended, then I wouldn't have an N+1 row to put the next value in, and
>the argument would be valid. But since it doesn't end, it's infinite, my
>mapping function never fails to find a row to put the value in.
>

I'm reminded of a game to see who can name the bigger number.
Who gets to go first?

Todd Trimble