Subject:      Cantor's diagonalisation method and the naturals
Author:       Cattabriga 
Date:         17 Apr 99 08:31:19 -0400 (EDT)

To [email protected]


Nico([email protected])------------------------------------------------

But the problem is the diagonalisation of "all" the reals.
Let me put it this way in a visualisation:

                     1,000000000000.....
                    ..,.................
                  ....,................. 
          100000000000,000000000000.....
      ................,.................          
 100000000000000000000,000000000000.....   
etcetera.

When I see people explainig diagonalisation they take the interval
(0,1).
But Cantor was talking about R.
And that gives in decimal notation [%] an infinite triangle before 
the comma and an infinite square after the comma.
I know the diagonal of a square, but I do not know the diagonal of 
a triangle.
---------------------------------------------------------------------



Paola________________________________________________________________

[%] Too much intuition in your translation from decimal to 
binary notation.


Nevertheless, let me tell you something about the diagonal method,  
in decimal notation which is more familiar to me, and perhaps 
more simple for you too.



The diagonal method is by definition a self-reference method. This
is the main aspect. The geometric representation


--------------
| \          |
|   \        |
|     \      |
|       \    |
|         \  |
--------------


is important but secondary with respect to the self-referring.
The essential point is that diagonal method it is a  self-reference  
procedure which leads to contradiction.



Let me show all that starting with a resume of the method:


                                                    START   ---
 
 
1  <--> |0,1|  1   1   1   1 .....
2  <-->  0,3  |0|  1   0   2 .....
3  <-->  0,4   7  |7|  1   2 .....
4  <-->  0,6   0   2  |0|  5 .....
5  <-->  0,6   9   8   9  |7| .....
.                          .
.                             .
.                                .
----------------------------------
        0,9    1   1   1   1 .....


Supposing there is an enumeration of '^'all'^' the real 
numbers there would be a one-one correspondence with the 
naturals. It is always possible to construct a new decimal 
which defines a real number not included in the list. From 
the digits along the diagonal of this array we construct a 
new real number between 0 and 1 writing as the first decimal 
a 9 if the first digit is 1 otherwise we write 1. We do the 
same for the second digit and so on. Thus the written real 
number differs from '^'all'^' the real numbers included in the 
list in at least one decimal place. This contradicts our 
supposition that the enumeration included '^' all'^' real numbers.  


                                                         END   ---


An enumeration is a function f(0),f(1),f(2),...
which has naturals in the domain and the enumerated set as
the codomain, in this case R, so that we '^' should '^' have
F(0) = R0
F(1) = R1
F(2) = R2
     :
     :
     :
     :
     : 


where each Rx is like 0,6   0   2  0  5 ..... or 
0,3  0  1   0   2 .....  etc.....

Let us define Rx = _,r1r2r3r4........

Let us now define a function

                   rewrite rj as 9 if rj=1 (j=1,2,...)
                 /
            D(Rx)
                 \ rewrite rj as 1 if not rj=1 (j=1,2,...)

so that

D: Rx -> Ry

and 

D: _,r1r2r3r4........ ->  _,d1d2d3d4.........

where Ry =  _,d1d2d3d4.........

Of course D is computable since it is a sound step_by_step algorithm.

But what is 'y' here? Is it, exactly like 'x',  a variable over
0,1,2,3,.... , or is it not?.

We have then two cases: B) Ry is not one of the enumerated reals
A) Ry is one of the enumerated reals.


Hyp B) Ry is not one of the enumerated reals, since
_,d1d2d3d4......... is different from all the R0,R1,R2,R3,....... 

F(0) = R0
F(1) = R1
F(2) = R2
     :
     :
     :
     :
     : 
F(n) = Rn
     :
     :
     :
     :
     : 


for each Rn   D(Rn) is not Rn 

hence 

*) for each Rn   D(Rn) is not F(n)

but

D(Rn)->Rm and Rm is a real number

since Rm is a real number Rm is one of all
all the R0,R1,R2,R3,....... 

hence 

c) F(m)=Rm


and c) contradicts *).

Hyp A) We already supposed that R0,R1,R2,R3,.......  
was the list of '^'all'^' the real numbers, then _,d1d2d3d4.........
is in the list, and Ry is one of the enumerated reals.
Ry is one of R0,R1,R2,R3,.......  

hence

F(y)=Ry

hence

F(y)=D(Rx)

and

F(x)=Rx

and also

F(y)=D(F(x))

but no contradiction here, it is never the case that y=x.


---
As you can easily see, Hyp B is just the classical method which
yields a contradiction with n=m (see above  START   ---  END   ---).

Why there is not a classical case for Hyp A ?

Where is the self-referring?
The self-referring regards D. 
D making reference to '^'all'^' the real numbers
refers to itself.

In simple terms: its domain can map to itself      or
                 there can be identity between some elements
                 of the domain and some elements of the codomain.
                 
 
Is that clear? 
                 

Well,   why    the self-referring, or identity, leads
to contradiction in Hyp B while there is no contradiction
in Hyp A?

D is the same procedure in both A and B !

So, what happens here?

The answer is in the way D refers to '^'all'^'.


Hyp A: _,d1d2d3d4......... in R0,R1,R2,R3,....... 

Hyp B: _,d1d2d3d4......... not in  R0,R1,R2,R3,....... 

Hyp A: Ry in R0,R1,R2,R3,....... 

Hyp B: Ry not in  R0,R1,R2,R3,....... 


In both cases  R0,R1,R2,R3,.......  is the list
of '^'all'^' reals.


Well, as already supposed, in both cases y is a variable 
over 0,1,2,3,......  , we can then have



Hyp A: R0,R1,R2,R3,.......  in   R0,R1,R2,R3,....... 

Hyp B: R0,R1,R2,R3,.......  not in     R0,R1,R2,R3,....... 


An ancient way to understand 'in' (Peano's epsilon) was
to consider it as the grammatical copula, i.e. the verb to be.


Hyp A: Ry is R0,R1,R2,R3,....... 

Hyp B: Ry  is not R0,R1,R2,R3,....... 


Hyp A: R0,R1,R2,R3,.......  are   R0,R1,R2,R3,....... 

Hyp B: R0,R1,R2,R3,.......   are  not   R0,R1,R2,R3,....... 


Do you understand what is Hyp B ? 

In both cases  R0,R1,R2,R3,.......  is the list
of '^'all'^' reals, so we can change one each other,
for example as follows



Hyp B: R0,R1,R2,R3,.....  is not the list of '^'all'^' reals 


Hope this helps

Yours fancy beyond.

______________________________________________________________

http://www.serdata.it/cattabriga/default.html
______________________________________________________________