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?
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~---------~--~----~------------~-------~--~----~
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 - 09:22:41 PST