Re: Cantor's diagonal proof wrong?

From: *** T. Winter (***.Winter_at_cwi.nl)
Date: 11/22/04 

Date: Mon, 22 Nov 2004 04:36:30 GMT

In article <20041120161951.101$VO@newsreader.com> curt@kcwc.com (Curt Welch) writes:
> Pretend we have a infinite table made up of an infinite strings of 1s and
> 0s on each row. So every row in this table is just an infinite sequence of
> some combination of 1s and 0s.

It is well known that base-2 gives problems.
>
> With this table, we make the argument that it is impossible for every
> combination of 1s and 0s to be listed in the table. We prove this by using
> the diagonal argument.
>
> So we start with the assumption that the table which includes all
> combinations of 1s and 0s does exist.
>
> Then, we build the anti-diagonal value by selecting the numbers from the
> diagonal, and inverting them.
>
> This anti-diagonal value can not be in the table, because every table entry
> will be different by at least one digit.
>
> Therefore, we have created a contradiction with the starting assumption,
> that such a table can exist. Therefore, we have proved that the staring
> assumption is wrong, the table can not contain every possible string of 0's
> and 1's.
>
> This is the exact same logic used in Cantor's diagonal proof, but this
> time, we are not dragging anything about math into it. (change 0 1 to A B
> if you like just to remove numbers from the picture).
>
> The result of this proof is the belief that any mapping function which maps
> table rows to a string, can not include every possible string, because the
> proof has constructed a string (from ANY mapping function) that is not in
> the table.
>
> But, I can specify one special mapping function that works like this. Fill
> the first row with any combination of 1's and 0's you like. Then, fill
> every following row, with a copy of the row above it, with the diagonal
> digit inverted.

Yes, that is why the diagonal argument does not work in base 2.

> Now, what I can show about your diagonal value, is that every diagonal you
> construct is in fact in the table, in row N+1.

But it is very easy to construct a string that is not in that list. Take
the first item and invert only the second digit, or any other digit but
the first. 

-- 
*** t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~***/
Quantcast