Re: Brent's answer to Bruno's puzzle
>> 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 -~--~~~~--~~--~--~---
Re: Cantor's Diagonal
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 th
Re: Cantor's Diagonal
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
