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 everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Mon Dec 17 2007 - 13:05:15 PST