Math Forum / Mathematics / Mathematical Logic / February 2010

Hi all,

I have some difficulty digesting the diagonal argument of Cantor's.

The argument is that the set of all infinite binary sequences cannot
have a bijection to the set of all natural numbers, thereby proving
that the former set is uncountable?

However the argument looks to me to be so designed as to reach to that
goal?

One can look at matters from an alternative way such as to elude
Cantor's conclusion!

Examine the following:

Lets take the infinite binary sequences of the letters O and H

so for example we have the sequence

X = OHOHOH........

in which O is coupled to the even naturals and H coupled to the odd
naturals.

so the sequence above is

X= {<O,i>,<H,j>| i is an even natural, j is an odd natural}

so X is just an example of a infinite binary sequence.

However lets try to see weather we can have a bijection between
the set of all infinite binary sequences and the set w+1
which is {0,1,2,....,w}

so we'll have the following table:

  0  , 1 ,   2  , 3 , ...
0 H , O ,  O , H ,....
1 O , H ,  H , O ,....
2 H , H ,  H , H ,....
3 O ,O ,  H , H ,....
.
.
.
.

w O, O , O, O ,...

Now according to the above arrangement one CANNOT define a diagonal !
since the w_th sequence do not have a w_th entry
to put H or O in it.

So if we can have a diagonal then this would be of the set of all
infinite binary sequences except the w_th one, i.e. of the following

   0  , 1 ,   2  , 3 , ...
0 H , O ,  O , H ,....
1 O , H ,  H , O ,....
2 H , H ,  H , H ,....
3 O ,O ,  H , H ,....
.
.
.
.

Suppose that the diagonal of those was D=HHHHH....
i.e. D={<H,n>| n is a natural number}

Now the counter-diagonal would be D' = OOOO...
i.e. D' = {<O,n>| n is a natural number}

However there is nothing to prevent the w_th infinite binary sequence
from being D' ?

So neither we can have a diagonal of all the infinite binary
sequences, nor the diagonal of a subset of these sequences would yield
a successful diagonal argument such as to conclude that the set of all
infinite binary sequences is uncountable?

Thereby Cantor's argument fail in this situation!

What I am trying to say is that this Diagonal argument seems to be
purposefully designed to reach the goal of concluding that
the set of all infinite binary sequences is uncountable, by merely
selecting a particular bijection with the set {0,1,2,3,....}
in a particular arrangement, such as to make a diagonal possible, such
as to conclude the uncountability of these infinite binary sequences,
While if we make simple re-arrangement like the one posed above then
this argument vanish!

There must be something wrong with the way I had put things here, but
I would rather want to read the full proof of this diagonal argument
in Zermelo's set theory.

Zuhair