Re: Cantor's Diagonal

[Bruno Marchal]

Hi Daniel,

I agree with Barry, but apaprently you have still a problem, so I 
comment your posts.


Le 16-déc.-07, à 10:49, Daniel Grubbs a écrit :

  Hi Folks,

  I joined this list a while ago but I haven't really kept up.  Anyway, 
 I saw the reference to Cantor's Diagonal and thought perhaps someone 
 could help me.

  Consider the set of positive integers: {1,2,3,...}, but rather than 
 write them in this standard notation we'll use what I'll call 'prime 
 notation'. 



OK. That is often used to compare the purely additive and the purely 
multiplicative structures of the natural numbers. Of course the number 
0 is banished in the multiplicative structure (so you have to handle 0 
manualy, but that does not change the enumeration question, ok).




 Here, the number m may be written as
 m = n1,n2,n3,n4,...

 1 = 0,0,0,0,0,...
  2 = 1,0,0,0,0,...
  3 = 0,1,0,0,0,...
  4 = 2,0,0,0,0,...
  5 = 0,0,1,0,0,...
  ...
  28 = 2,0,0,1,0,0,0,...
  ...

 D = 1,1,1,1,1,...


  I can see that one may complain that D is clearly infinite and 
 therefore should not be in the set, ...


Yes. D does not describe a natural number.



 ... but consider the following...

  Let's take the original set and reorder it by exchanging the places 
 of the i'th prime number with that of the number in the i'th 
 position.  (i.e. First switch the number 2 with the number 1 to move 
 it to the first position. Then switch 3 with the number -- now 1 -- in 
 the 2nd position. Then 5 with the 1 which is now in the 3rd position. 
 Etc...) Because we are just trading the positions of the numbers, all 
 the same numbers will be in the set afterwards.

  The set is now:
 2  = 1,0,0,0,0,...
  3  = 0,1,0,0,0,...
  5  = 0,0,1,0,0,...
  7  = 0,0,0,1,0,...
  11= 0,0,0,0,1,...
  ...


What does ... mean here? It seems to me you are just enumerating the 
prime numbers. At which step will you put the numbers 1, 4, 6, etc.
If you do have a way to add, in the limit,  those numbers in the set, 
then you are just constructing an order type (ordinal) bigger than 
omega on the set of positive integers. But such constructive) ordinal 
are all enumerable.

You could have said directly: let us consider the following order: it 
is the usual order except that we decide that all even numbers are 
bigger than the odd numbers, so we have the order:

1, 3, 5, 7, 9,   2, 4, 6, 8, 10, 

This is an example of order type OMEGA+OMEGA

So what? We can easily enumerate it by zigzagging between the even and 
odd numbers.




 D = 0,0,0,0,...


  I would suggest that the diagonal method does not find a number which 
 is different from all the members of a set, but rather finds a number 
 which is infinitely far out in the ordered set.


Like I say. Your construction put a bigger, but still enumerable, order 
on N. Actually we have already used diagonalization for building 
constructive ordinal, or order type on the set of computable growing 
functions. But those produce enumerable sets.



  If anyone can find where I've gone wrong, please let me know.


Cantor showed that ALL tentative enumeration of some set S fails. This 
is what makes that set S non enumerable. You are just showing that the 
diagonal method can also work on some precise enumeration on N. This 
does not make N non enumerable, it makes only your precise enumeration 
incomplete (or extendible in the constructive ordinal, but that does 
not change anything).
A set is non enumerable if ALL attempts to enumerate it fail, not if 
some particular attempt fails. That is why we do a proof by a reductio 
ad absurdo.

In you next post you say (to Barry):


  Let me see if I am clear about Cantor's  method.  Given a set S, and 
 some enumeration of that set


Well S is fixed. It is the set we want to show being NOT enumerable. 
Then you take not some enumeration, but ANY enumeration.


 (i.e., a no one-one onto map from Z^+ to S) we can use the 
 diagonalization  method to find an D which is a valid element of S but 
 is different from any particular indexed element in the enumeration.


... is different from any particular indexed element, for any arbitrary 
enumeration. You have to be sure that the diagonal will work whatever 
enumeration is proposed.


  Cantor's argument then goes on to say (and here is where I disagree 
 with it) that therefore D is not included in the enumeration and the 
 enumeration is incomplete.

  I, on the other hand, would posit that the enumeration may include 
 elements whose index is not well defined.


H In Cantor's proof of the non enumerability of 2^N (the set of 
infinite binary sequences), the indexes are all perfectly well defined 
even if it is in Platonia or in the mind of God, so your remark does 
not apply.

But now, curiously enough, a remark similar to your's can be done about 
the proof that the (total) computable functions from N to N are not 
*computably* enumerable.
In that case, if we assume Church thesis, and thus the existence of a 
universal 

Re: Brent's answer to Bruno's puzzle

[Barry Brent]

 Exercise:
 What is wrong with the following argument. (I recall that by  
 definition
 a function from N to N is defined on all natural numbers).

 (false) theorem: the set of computable functions from N to N is not
 enumerable.
 (erroneous) proof: let us suppose (by absurdum) that the set of
 computable functions from N to N is enumerable. Thus there exist an
 enumeration f_1, f_2, f_3, ... f_i,  of the computable functions
 from N to N. But then I can define the following computable  
 function g,
 from N to N, by:

 g(n) = f_n(n) + 1

 g is computable: to compute it just search in the enumeration the
 function f_n, which is computable, and then apply it on n, and  
 then add 1.
 But then g has to be in that enumeration f_i of the computable  
 function.
 Thus there is a k such that g = f_k. In particular g(k) = f_k(k). But
 g(k) = f_k(k) + 1, by definition of g. Thus f_k(k) = f_k(k)+1. And  
 the
 f_i are computable functions, so f_k(k) is a well defined number,  
 which
 I can subtract on the left and the right side of f_k(k) = f_k(k)+1,
 giving 0 = 1. Contradiction. So the set of computable functions  
 from N
 to N is not enumerable.

 What is wrong? We know that the set of computable function has to be
 enumerable, because computable means we can describe how to compute
 the function in a finite expression in some language, and the set  
 of all
 finite expressions has been shown enumerable. So what happens?

 If you tried to compute g(k) and g was in the list, i.e. some f_k,  
 then when
 you searched a for g, when you came to f_k it would start with the
 prescription ...just search in the enumeration... and you would  
 be in a
 infinite loop.

 Brent Meeker

Brent, I don't think this is enough.  There may be a different  
algorithm for f_k that escapes your infinite loop.  If this  
alternative algoritm doesn't exist, I think you need to show that it  
doesn't exist.

I suspect that the error in Bruno's erroneous proof has to do with   
formal languages.  Say a function f is computable with regard to a  
formal language L when there exists an algorithm written in L  to  
compute f. The f_n are computable with regard to some particular  
formal language.  Functions computable with regard to one language  
may or may not be computable with regard to another language.  (If  
this is false, Bruno needs to prove it's false.)  Thus when Bruno  
argues that the set of computable functions is enumerable, he must  
mean for any fixed language L, the functions computable with regard  
to L is enumerable.  Now the procedure Bruno described for computing  
g is not written in a formal language--it's written in English.  The  
fact that this English language description is finite doesn't prove  
that g is computable with regard to L, ie, doesn't prove that  g is  
one of the f_n.

I'm an amateur at this--this solution is really just a question for  
Bruno...


Barry  (Barry Brent, not Brent Meeker!)


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en
-~--~~~~--~~--~--~---