Bruno Marchal wrote:
> 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.
> 
> 
> 
> Hmmmm.... 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 language L, the set of all (total) computable functions from N 
> to N *is* enumerable, but is not computably enumerable.
> 
> The lesson is that there is a bijection between the set of indexes of 
> the total computable functions from N to N, and N, but that bijection is 
> not a computable function.
> 
> See the preceding "key" post, because you are perhaps confusing 
> effective (computable) enumeration and non effective enumeration.
> I recall that the diagonal argument, when applied on the set of all 
> functions (from N to N) proves that that set is not enumerable, but when 
> the diagonal argument is applied to the (obviously) enumerable set of 
> computable functions (from N to N) it shows that the enumeration (which 
> exists) is not a computable one.
> 
> 
> 
> 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

--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---

Reply via email to