Re: Cantor's diagonal proof wrong?

From: Manuel Petit (freston_at_freston.org)
Date: 11/14/04 

Date: Sun, 14 Nov 2004 01:27:56 -0800

Curt Welch wrote:

> 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

Well, you have to prove that claim.

> 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.

Ok start with:

        e = 1 + 1/1! + 1/2! + 1/3! + ...

>
> 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.

You fooled yourself. Your are assuming that your table is a table of
reals, but in fact is a table of integers: remember you still have to
prove your mapping is one to one, until then you can only assume you
have a table of integers. Since it is a table of integers, no surprise
the diagonal element 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.

Your (flawed) reasoning went as follows:

        * assume N == R [remember you claimed but did not prove]

        * Cantor's proof says D(infinity) is not in the table

        * Since you assume N == R, you build a table of naturals
          and call it a table of reals.

        * After building such table, you revel in finding
          that D(infinity) is in the table.

        * And you conclude that since D(infinity) is in fact in
          *your* table, Cantor is wrong, and that you have proved
          that N == R.

Again, all your problems start with your table and your (wrong)
assumption that your mapping is one to one and hence you built a table
of reals. Ex falso sequitur quodlibet.

manuel,

Relevant Pages

  • Re: Cantor and the binary tree
    ... >>>List all the infinite binary sequences with a bijection to the integers. ... to be referring to the "proof" of uncountability of the reals. ... By traversing the list diagonally ... the sense that there are as many digits in each number as numbers in the list. ...
    (sci.math)
  • Re: Dial 999 for the real number line
    ... length n as initial strings followed by the expansion of pi after the nth ... long decimal expansion followed by an infinite expansion. ... for producing successive digits of pi without end. ... There are no other reals at the end of or besides this list. ...
    (sci.math)
  • Re: Cantors diagonal proof wrong?
    ... > with an infinite number of procedures that produce .2. ... That is the foundation which math grows out of. ... continue generating all the digits. ... for as long as the real generating processes produces reals to work with. ...
    (sci.math)
  • Re: Math errors in python
    ... > They don't even share three digits beyond the decimal point. ... Uh, "constructive reals", such as those you can find at ... constructively interesting" subset that is _countably_ infinite. ... coefficients fit comfortably in memory (with space left over for some ...
    (comp.lang.python)
  • Re: Cantor and the binary tree
    ... > look at infinite pathes: all pathes which are infinite extensions ... From the diagonal-argument it comes out that they cannot be ... that the infinity of real numbers is greater than the infinity of the digits ... If we say the reals each contain N ...
    (sci.math)