Cantor's diagonal proof wrong?

From: Curt Welch (curt_at_kcwc.com)
Date: 11/14/04 

Date: 14 Nov 2004 06:39:15 GMT

Here's something all of you should have some fun with.

Nath is not something I specialize in (and I don't read this group
normally), but I've been looking at a few things lately and I've decided
that some very big mistakes have been made in math because people started
playing around the concept of infinity without realizing the trouble they
were creating for themselves.

When I was shown Cantor's diagonal proof that the number of reals was not
countable back in college, I thought it was a fascinating proof. It seemed
to uncover some great mystery about the nature of numbers that was not at
first obvious. It sounded very logical and I quickly embraced it as fact.

Lately however, I've come to see things very differently. I now belief the
proof is totally bogus. And the huge body of work built on top of the
concept is likewise, totally bogus.

But, like I said, I'm not a math expert by any means. So I'm posting the
idea here so you experts can have fun laughing at me.

The reason I came to these conclusions is because I've spent a lot of time
trying to uncover the mysteries of AI (artificial intelligence). i.e.,
trying to understand how to build a machine that is just as intelligent as
we are. And as I've worked on that, I've come to some understanding (also
unproven) about what "thinking" is all about. And this led me to question
some fundamental ideas in other fields, like math.

The problem with math, is that when you start playing with ideas like
infinity, you are making some basic assumptions on what an idea is. Yet,
no one knows how we think, or why we think. Yet, that hasn't stopped
mathematicians and philosophers in making endless assumptions in order to
try and understand the very nature of thought (and existence), and how it
applies to their field. However, I think they got a few things very wrong.
And it's my work on AI which caused me to question Cantor's diagonal proof
in the first place. And instead of accepting it as fact, as I did back in
college when it was shown to me, I looked at it again thinking it was
invalid. And when I look at like that, I see that it is.

Let me demonstrate.

I claim that there is only one type of infinity. That there are just as
many integers as there real numbers. (or more accurately, that the concept
of the size of an infinite set is a contradiction in itself).

So, let me create a mapping. I'll start with the mapping from the integers
to the reals in the range 0 to 0.99999....

I R

0 0.0000...
1 0.1000...
2 0.2000...

10 0.0100...

123 0.3210...

So you just reverse the digits in the integer to create the real. I claim
this mapping is one to one and covers all the reals in that range. For any
real you give me, I can easily give you the matching integer. Just reverse
the digits. This includes all the irrationals because in fact, you can't
give me an infinite irrational to work with. You can only give me an
algorthm for creating it. And any algorithm you give me, I can modify to
create the matching integer.

Let's look at this mapping with Cantor's diagonal proof. We construct a
real number by picking digits from the diagonal which is different from
each row in the table. Well, as it happens, the diagonal in this mapping
is all zeros, so we can pick a simple real like 0.1111... as the number
which can not be in the table. I'll call this number D. Cantor's proof
seems to show quite clearly that D is not in the table, because it can not
be located at any row of the table (for what seems to be obvious reasons).

Let me define D(n), as the first N digits of this "constructed" missing
real diagonal. The first N digits are 1, and the rest are 0.

So D(2) is 0.11 and D(5) is 0.11111 etc.

We see that D(5) can not be located in the first 5 rows of the mapping.
But, we also can easily prove that D(5) does show up at row 11111.

So, as we construct D(n), we see that even though it doesn't match any of
the rows up to the point we have reached, it is always further down in the
table. And because the table is infinite, we will always be able to find
it futher down in the table.

So, this proves that D(n) for all values of n, from 0 to infinity, is in
the table.

So, now we have a contradiction. Cantor's proof says that D(infinity) is
not in the table, yet D(n) for all values of n, including infinity, is in
the table from the above logic, which is just as clear and straight forward
as Cantor's. So how can both be true? If they are not both true, which is
one wrong and the other one not?

How can this be? I say, it's because there's a contradiction in Cantor's
proof, and the contradiction is not the one that everyone assumes - that
there are more reals than integers.

As another example, let me show that the number of integers are also
greater than the number of integers, using the logic of Cantor's proof.

Lets create a table of integers like this:

  ...000000
  ...000001
  ...000002

  ...000010

  ...000123

It's just a normal list of integers, but instead of following the normal
convention of leaving off the leading zeros (which we all know are implied
even if we don't write them) I include them in that table.

So lets use Cantor's logic on this table and see if we can construct a
number which is not in the table. We take the numbers from the diagonal,
and construct the number ...111111 just like we did above.

Since we construct this number by changing a digit from every row, we know,
by Cantor's logic, that the resulting number can not be in the table.
Therefore, with the wisdom of Cantor, I've proved that the number of
integers is greater than the number of integers. There are some integers
which are simply not in the list of all integers.

Ok, so if Cantor was wrong, why was he wrong?

The answer is one already well known to mathematicians. They just never
realized how it applied here. You can't use infinity as if it existed. It
doesn't exist. "infinity" is only a name for something which can not
exist.

The contradiction that Cantor put into his assumptions in the diagonal
proof, was that something of infinite size does exist. The number I call
D, the constructed diagonal which can not exist, he declares does it exist.
That's the contradiction in his assumption which causes the final
contradiction.

If you think it's ok to use infinity like it was real, it becomes possible
to prove anything by contradiction. I can easily for example prove that 1
= 0 by making the same mistake by playing with an infinit series of 1 - 1 +
1 - 1 + 1 ..., or by using 1/0 in a proof as if it were a number that
existed.

So, what I'm saying is that infinite sized sets don't exist at all, and
can't exist. And any time you start with an axiom which says "infinite
sized sets do exist", you have introduced an contradiction into your axioms
which guaranties contradictions in your results.

We don't have "the set of all integers". What we have is a counting
algorithm that can generate as many integers as you need for any
application.

It's perfectly valid to talk about what infinite algorithms do as they
approach infinity. But once you start to pretend they reach it, you have
stepped over the line into a world filled with contradiction, and a world
which has nothing to do with the universe we exist in.

This is because "ideas" are not "magic". They are the result of mechanical
computation. And mechanical computation takes time. So any time you talk
about computing an infinite sized set (like the set of all integers) you
have stepped outside the realm of reality and into a fantasy world full of
contradictions which you created by putting the contradiction of the
existence of infinity into your world. If you start an algorithm running
to create your infinite sized set, it will never finish, so any attempt to
talk about what you do after that is invalid. In Cantor's proof, he asked
us to construct an infinite sized real, and then check to see if it was in
one of the rows of the table. And as I showed above, as you construct it,
the number you have will always be in the table. No matter how long you
spend constructing D, the value you have will always be in the table.

If you "pretend" the job of construction does end (the program that can
never halt does halt), then you have put a contradiction into the system
that allows you to prove anything by contradiction. You can prove there
are more reals than integers, or that there are more integers than integers
(as I did above), or that 1 = 0. As long as you can slip that
contradiction in as an axiom (without anyone raising a penalty flag), you
can prove anything you want by contradiction - because you started with a
contradiction.

Much other important work, such as Gödel's, also fell prey to this same
mistake.

Oh, and if you want a mapping from the integers to all the reals, here's
one:

  0 0.0
  1 0.1
 10 1.0
123 2.31

i.e., you take the integer and number the digits like this:

  ... D4 D3 D2 D1 D0

And you construct the real as: ... D3 D1 . D0 D2 D4 ...

You use the even digits to construct the real to the right of the decimal
point, and the odd digits to construct the real to the left of the decimal
point. So your integer which grew to infinity in one direction, now
creates a real which grows to infinity in two directions.

Now, I know most (if not all of you), will tell me I'm crazy. Many
probably won't even read my post. But if you think I'm crazy, tell me
this. How is my proof that the number of integers is greater than the
number of integers, any less valid than Cantor's proof that the number of
reals is greater than the number of integers? If you can't tell me that,
then why would you believe Cantor's proof is valid? If you can, I'd like
to hear about it.

Has any one else put forth this same argument (or others) that Cantor's
proof is invalid? 

-- 
Curt Welch                                            http://CurtWelch.Com/
curt@kcwc.com                                        http://NewsReader.Com/

Relevant Pages

  • Re: Cantors diagonal proof wrong?
    ... > infinity, you are making some basic assumptions on what an idea is. ... > of the size of an infinite set is a contradiction in itself). ... > So you just reverse the digits in the integer to create the real. ... > this mapping is one to one and covers all the reals in that range. ...
    (sci.math)
  • Re: Cantors diagonal proof wrong?
    ... Infinity is not an integer, ... just a string of digits, ... >possible to prove anything by contradiction. ...
    (sci.math)
  • Re: just how many reals are there in aleph_1 ?
    ... >> For two reals to be equal, each of their digits must be equal ... by assuming that R has an impossible property, then use it to prove that R ... > your definition is a contradiction ... whose digits differ from the digits in the diagonal. ...
    (sci.math)
  • Re: just how many reals are there in aleph_1 ?
    ... >> For two reals to be equal, each of their digits must be equal ... by assuming that R has an impossible property, then use it to prove that R ... > your definition is a contradiction ... whose digits differ from the digits in the diagonal. ...
    (sci.logic)
  • Re: Cantor and the binary tree
    ... Terefore some people believe in finished infinity, ... You must rely on the principle. ... Obviously the antidiagonal it is not different from all reals on the ... Its digits are not complete. ...
    (sci.math)