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?

## Advertising

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