Re: Cantor's diagonal proof wrong?

From: Josh Purinton (usenet-noreply.a.jp_at_xoxy.net)
Date: 11/22/04 

Date: Mon, 22 Nov 2004 05:31:55 GMT

In article <I7KCsv.Avv@cwi.nl>, *** T. Winter <***.Winter@cwi.nl> wrote:
>In article <20041120161951.101$VO@newsreader.com> curt@kcwc.com (Curt
>Welch) writes:
> > 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.

The diagonal argument works for any base B >= 2.

To see this, let S be a list of reals in [0,1], and let S_k denote the
kth number in the list. Let S_k(i) denote the ith digit in the base B
expansion of S_k.

Let G be a real in [0,1], and let G(i) be the ith digit of the base B
expansion of G, defined by the rule:

               / 0 if S(i,i) = 1
        G(i) = |
               \ 0 otherwise
        

By definition G(i) =/= S(i,i), and so G differs from S_i for all i.
Therefore S does not contain all the reals in [0,1]. 

-- 
Josh Purinton
Quantcast